LinkedList和二叉搜索树之间的区别

链接列表和BinarySearchTree之间的主要区别是什么？BST只是维护LinkedList的一种方式吗？我的导师谈到了LinkedList,然后讨论了BST,但没有比较它们或者没有说何时更喜欢一个而不是另一个.这可能是一个愚蠢的问题,但我真的很困惑.如果有人能够以简单的方式澄清这一点,我将不胜感激.

链接列表:

Item(1) -> Item(2) -> Item(3) -> Item(4) -> Item(5) -> Item(6) -> Item(7)

二叉树:

                 Node(1)
                /
            Node(2)
           /    \
          /      Node(3)
  RootNode(4)
          \      Node(5)
           \    /
            Node(6)
                \
                 Node(7)

在链接列表中,项目通过单个下一个指针链接在一起.在二叉树中,每个节点可以有0,1或2个子节点,其中(在二叉搜索树的情况下)左节点的密钥小于节点的密钥,右节点的密钥大于节点.只要树是平衡的,每个项目的搜索路径比链接列表中的搜索路径短得多.

搜索路径中:

------ ------ ------
key    List   Tree
------ ------ ------
1      1      3
2      2      2
3      3      3
4      4      1
5      5      3
6      6      2
7      7      3
------ ------ ------
avg    4      2.43
------ ------ ------

通过更大的结构,平均搜索路径变得更小:

------ ------ ------
items  List   Tree
------ ------ ------
     1      1   1
     3      2   1.67
     7      4   2.43
    15      8   3.29
    31     16   4.16
    63     32   5.09
------ ------ ------

甲二叉搜索树是一个二叉树,其中,每个内部节点X存储元件,例如,存储在的左子树的元素X是小于或等于X和存储在右子树的元素X是大于或等于x.

现在,链接列表由一系列节点组成,每个节点包含任意值以及指向下一个和/或前一个节点的一个或两个引用.

在计算机科学中,二叉搜索树(BST)是二叉树数据结构,具有以下属性:

每个节点(树中的项)具有不同的值;

左右子树也必须是二叉搜索树;

节点的左子树只包含小于节点值的值;

节点的右子树仅包含大于或等于节点值的值.

在计算机科学中,链表是基本数据结构之一,可用于实现其他数据结构.

因此二进制搜索树是一个抽象概念,可以用链表或数组实现.而链表是基本数据结构.

我会说MAIN的区别在于二叉搜索树是排序的.当您插入二进制搜索树时,这些元素最终存储在内存中是其值的函数.使用链表,无论元素的价值如何,都会盲目地将元素添加到列表中.

您可以立即进行一些权衡:链接列表保留插入顺序,插入更便宜二进制搜索树通常更快搜索

链表是彼此链接的连续数量的"节点",即:

public class LinkedListNode
{
     Object Data;
     LinkedListNode NextNode;
}

二进制搜索树使用类似的节点结构,但它不链接到下一个节点,而是链接到两个子节点:

public class BSTNode
{
    Object Data
    BSTNode LeftNode;
    BSTNode RightNode;
} 

通过在向BST添加新节点时遵循特定规则,您可以创建一个非常快速遍历的数据结构.这里的其他答案详细说明了这些规则,我只是想在代码级别显示节点类之间的区别.

重要的是要注意,如果您将已排序的数据插入到BST中,您最终会得到一个链表,并且您将失去使用树的优势.

因此,linkedList是O(N)遍历数据结构,而BST在最坏的情况下是O(N)遍历数据结构,在最好的情况下是O(log N).

链接列表和BST实际上并没有太多共同之处,只是它们都是充当容器的数据结构.链接列表基本上允许您在列表中的任何位置有效地插入和删除元素,同时保持列表的顺序.此列表使用从一个元素到下一个元素(通常是前一个元素)的指针实现.

一个二叉搜索树,另一方面是更高的抽象的数据结构(即它没有规定如何这是内部实现的),可实现有效的搜索(即,为了找到一个特定的元素,你不必在所有看要素.

请注意,链接列表可以被视为退化二叉树,即所有节点只有一个子节点的树.