data-structures - LinkedList 和二叉搜索树的区别

Question

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

score 84 · Accepted Answer

链表：

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)

在链表中，项目通过单个 next 指针链接在一起。在二叉树中，每个节点可以有 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
------ ------ ------

score 16 · Accepted Answer

二叉搜索树是一棵二叉树，其中每个内部节点x存储一个元素，使得 x 的左子树中存储的元素小于或等于x并且x的右子树中存储的元素大于或等于x。

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

score 13 · Accepted Answer

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

每个节点（树中的项目）都有一个不同的值；
左右子树也必须是二叉搜索树；
节点的左子树只包含小于节点值的值；
节点的右子树只包含大于或等于节点值的值。

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

所以二叉搜索树是一个抽象概念，可以用链表或数组来实现。而链表是一种基本的数据结构。

score 9 · Accepted Answer

我想说的主要区别是对二叉搜索树进行了排序。当您插入二叉搜索树时，这些元素最终存储在内存中的位置是其值的函数。使用链表，元素被盲目地添加到列表中，而不管它们的值如何。

您可以立即进行一些权衡：链表保留插入顺序并且插入成本更低二叉搜索树通常搜索速度更快

score 7 · Accepted Answer

链表是相互链接的连续数量的“节点”，即：

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)。

score 6 · Accepted Answer

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

另一方面，二叉搜索树是一种更高抽象的数据结构（即它没有指定如何在内部实现），它允许有效的搜索（即为了找到一个特定的元素，你根本不需要查看要素。

请注意，链表可以被认为是退化的二叉树，即所有节点只有一个孩子的树。

score 6 · Accepted Answer

它们确实有相似之处，但主要区别在于二叉搜索树旨在支持对元素或“键”的有效搜索。

二叉搜索树，就像一个双向链表，指向结构中的另外两个元素。然而，当向结构中添加元素时，而不是仅仅将它们附加到列表的末尾，二叉树被重新组织，使得链接到“左”节点的元素小于当前节点，而链接到“右”节点的元素节点大于当前节点。

在一个简单的实现中，将新元素与结构的第一个元素（树的根）进行比较。如果小于，则采用“左”分支，否则检查“右”分支。这对每个节点都继续，直到发现一个分支是空的；新元素填充该位置。

使用这种简单的方法，如果按顺序添加元素，您最终会得到一个链表（具有相同的性能）。通过重新排列节点，存在不同的算法来维持树中的某种平衡度量。例如，AVL 树做最多的工作是尽可能保持树的平衡，从而提供最佳搜索时间。红黑树不能保持树的平衡，导致搜索速度稍慢，但在插入或删除键时平均做的工作较少。

score 4 · Accepted Answer

其实很简单。链表只是一堆链接在一起的项目，没有特定的顺序。你可以把它想象成一棵从不分枝的非常瘦的树：

1 -> 2 -> 5 -> 3 -> 9 -> 12 -> |i. （最后是终止 null 的 ascii-art 尝试）

二叉搜索树在两个方面有所不同：二叉部分意味着每个节点有2个子节点，而不是一个，而搜索部分意味着这些子节点被排列以加快搜索速度——只有较小的项目在左边，只有较大的项目向右：

9 没有左孩子，1、2 和 12 是“叶子”——它们没有分支。

有道理？

对于大多数“查找”用途，BST 更好。但是对于仅“保留一个列表以处理以后的先进先出或后进先出”类型的事情，链接列表可能会很好用。

score 3 · Accepted Answer

链表就是……一个列表。它是线性的；每个节点都有对下一个节点的引用（如果您说的是双向链表，也是前一个节点）。树的分支---每个节点都有对各种子节点的引用。二叉树是一种特殊情况，其中每个节点只有两个孩子。因此，在链表中，每个节点都有一个前一个节点和一个下一个节点，而在二叉树中，一个节点有一个左孩子、右孩子和父母。

这些关系可能是双向的或单向的，这取决于您需要如何遍历结构。

score 3 · Accepted Answer

链表的问题是在其中搜索（无论是检索还是插入）。

对于单链表，您必须从头部开始并按顺序搜索以找到所需的元素。为了避免扫描整个列表，您需要对列表中的节点进行额外的引用，在这种情况下，它不再是一个简单的链表。

二叉树通过固有的排序和可导航性允许更快速的搜索和插入。

我过去成功使用的另一种方法是 SkipList。这提供了类似于链表的东西，但具有额外的引用以允许与二叉树相当的搜索性能。

score 2 · Accepted Answer

链表是直线数据，相邻节点相互连接，例如 A->B->C。您可以将其视为直栅栏。

BST 是一种层次结构，就像一棵树，主干连接到分支，而这些分支又连接到其他分支，依此类推。这里的“二进制”一词意味着每个分支最多连接到两个分支。

您使用链表仅表示直接数据，每个项目最多连接一个项目；而您可以使用 BST 将一个项目连接到两个项目。您可以使用 BST 来表示诸如家谱之类的数据，但这将成为 n 元搜索树，因为每个人可能有两个以上的孩子。

score 1 · Accepted Answer

二叉搜索树可以以任何方式实现，它不需要使用链表。

链表只是一个结构，它包含节点和指向节点内其他节点的指针/引用。给定列表的头节点，您可以浏览到链表中的任何其他节点。双向链表有两个指针/引用：对下一个节点的正常引用，以及对前一个节点的引用。如果双向链表中的最后一个节点引用列表中的第一个节点作为下一个节点，并且第一个节点引用最后一个节点作为它的前一个节点，则称它为循环链表。

二叉搜索树是一棵基于二叉搜索比较算法将其输入分成大致相等的两半的树。因此，它只需要很少的搜索就可以找到一个元素。例如，如果你有一棵 1-10 的树并且你需要搜索三个，首先会检查顶部的元素，可能是 5 或 6。三个会小于那个，所以只有前半部分然后将检查树。如果下一个值为 3，则您拥有它，否则，将进行比较，等等，直到找不到它或返回其数据。因此，树的查找速度很快，但插入或删除的速度并不快。这些是非常粗略的描述。

来自维基百科的链表和二叉搜索树，也来自维基百科。

score 1 · Accepted Answer

它们是完全不同的数据结构。

链表是一个元素序列，其中每个元素都链接到下一个元素，如果是双向链表，则链接到前一个元素。

二叉搜索树是完全不同的东西。它有一个根节点，根节点最多有两个子节点，每个子节点最多可以有两个子笔记等。这是一个非常聪明的数据结构，但在这里解释起来有点乏味。查看有关它的Wikipedia 文章。

data-structures - LinkedList 和二叉搜索树的区别

13 回答 13

Related

Reference