logo标签列表

链表和二叉搜索树的区别

data-structureslinked-listlanguage-agnosticbinary-search-tree
43

链表和二叉搜索树之间的主要区别是什么？BST是否只是维护链表的一种方式？我的讲师讲解了链表和BST，但没有进行比较或说明何时应该优先选择其中之一。这可能是一个愚蠢的问题，但我真的很困惑。如果有人能简单地澄清这一点，我将不胜感激。

13个回答
88

链表：

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
------ ------ ------
3
你的图表看起来很棒。你是如何生成它们的？ - Flimtix
你能否也解释一下时间复杂度的区别？ - ismail pervez
@ismailpervez 这大致上是关于时间复杂度的问题。 - Toon Krijthe
16

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

alt text

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

链表

14
在计算机科学中，二叉搜索树（BST）是一种二叉树数据结构，具有以下特性：
  • 每个节点（树中的项）都有唯一的值；
  • 左右子树都必须是二叉搜索树；
  • 节点的左子树仅包含小于节点值的值；
  • 节点的右子树仅包含大于等于节点值的值。
在计算机科学中，链表是基本数据结构之一，可以用来实现其他数据结构。
因此，二叉搜索树是一个抽象概念，可以使用链表或数组来实现。而链表是一种基本的数据结构。
二叉搜索树不仅仅是抽象的概念。在我的算法和数据结构课程中，我必须实现一个二叉搜索树。在实现过程中，我没有使用链表或数组。 - Harper Shelby
Harper Shelby，请透露一些关于你的实现方面的更多细节？ - VarunGupta
1
@VarunGupta - 这已经过去了几年，我怀疑我现在能否挖出源代码，但我创建了一个简单的节点结构，其中包含数据指针、左（子树）指针和右（子树）指针。整个二叉搜索树只是一个头节点指针。我编写了插入/删除等函数。 - Harper Shelby
11

我认为主要的区别在于二叉搜索树是有序的。当您插入二叉搜索树时，元素存储在内存中的位置取决于它们的值。而链表则不管元素的值是什么，都会将其盲目添加到列表中。

显然，这里存在一些权衡： 链表保留插入顺序，并且插入操作更加便宜； 二叉搜索树通常比较快速地进行搜索。

7
他们有相似之处，但主要区别在于二叉搜索树旨在支持对元素或“键”的高效搜索。
二叉搜索树与双向链表类似，指向结构中的两个其他元素。然而，在向结构添加元素时，二叉树不仅将它们附加到列表末尾，而且重新组织结构，使链接到“左”节点的元素小于当前节点，并且链接到“右”节点的元素大于当前节点。
在简单的实现中，将新元素与结构的第一个元素（树的根）进行比较。如果它小于该元素，则采用“左”分支，否则检查“右”分支。这将继续每个节点，直到找到一个分支为空;新元素填充该位置。
使用这种简单方法，如果按顺序添加元素，则会得到一个链接列表（具有相同的性能）。不同的算法存在于通过重新排列节点来维护树的某些平衡度量。例如，AVL树做最多的工作来保持树尽可能平衡，从而获得最佳搜索时间。红黑树不保持树的平衡，导致稍微较慢的搜索，但在插入或删除键时平均工作量较少。
2
为什么这个（正确的）回答被下投票而原始（奇怪的）问题却被上投票了？？我不明白... - TT_ stands with Russia
@TT_ 谢谢！我一直对这个回答被踩感到有点难过。 - erickson
1
请再接受一枚赞——我认为这个解释比被采纳的答案好多了。我认为原始问题显然是关于多重链接列表的（二叉树和单向链表之间的区别是显而易见的）。 - Adelmar
7

链表是一系列相互链接的“节点”，即：

public class LinkedListNode
{
     Object Data;
     LinkedListNode NextNode;
}

二叉搜索树使用类似的节点结构，但是它不是链接到下一个节点，而是链接到两个子节点：

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

通过遵循特定规则将新节点添加到二叉搜索树中，可以创建一个非常快速的遍历数据结构。其他答案已经详细介绍了这些规则，我只想在代码级别上展示节点类之间的区别。
需要注意的是，如果您将排序数据插入到BST中，最终会得到一个链表，您将失去使用树的优势。
因此，LinkedList是一种O(N)遍历数据结构，而BST在最坏情况下是O(N)遍历数据结构，在最好情况下是O(log N)。
6
Linked lists和BSTs实际上没有太多共同点，除了它们都是作为容器的数据结构。链表基本上允许您在列表中的任何位置高效地插入和删除元素，同时保持列表的排序。该列表使用从一个元素到下一个元素（通常还包括前一个元素）的指针来实现。
另一方面，二叉搜索树是一种更高抽象层次的数据结构（即未指定内部如何实现），它允许有效的搜索（即为了找到特定元素，您不必查看所有元素）。
请注意，可以将链表视为退化的二叉树，即所有节点仅有一个子节点。
如果一个“愚蠢”的树退化成为一个列表，那么列表不就是一个“愚蠢”的树，因此与树有更多的共同点，这比你最初想象的要多吗？ - ChiefTwoPencils
@ChiefTwoPencils 当然可以，但是这种关系存在于所有数据结构之间，并且并没有特别有意义。 - Konrad Rudolph
4
这其实很简单。链表就是一堆项目无序地链在一起。你可以把它想象成一棵非常瘦的树，从不分支：
1 -> 2 -> 5 -> 3 -> 9 -> 12 -> |i. (最后一个ascii图形试图表示终止空值)
二叉查找树有两个不同之处：二叉意味着每个节点有两个孩子，而不是一个孩子；搜索意味着这些孩子被排列以加速搜索——只有较小的项在左侧，只有较大的项在右侧。
    5
   / \
  3   9
 / \   \
1   2   12

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

明白吗？

对于大多数“查找”类的用途，二叉搜索树更好。但对于只是“保留一些东西以便稍后处理先进先出或后进先出”的事情，链表可能很好地发挥作用。

二叉树在添加时应该有一个成本。瘦树加1分，哈哈。 - nawfal
3
一个链表就是一个列表。它是线性的，每个节点都有指向下一个节点的引用（如果你谈论的是双向链表，则还有指向上一个节点的引用）。树分支——每个节点都有指向各种子节点的引用。二叉树是一种特殊情况，每个节点只有两个子节点。因此，在链表中，每个节点都有前一个节点和后一个节点，在二叉树中，一个节点有左孩子、右孩子和父节点。
这些关系可以是双向的或单向的，具体取决于您需要如何遍历结构。
3
使用链表的问题在于对其进行搜索（无论是为了检索还是插入）。
对于单向链表，必须从头开始顺序搜索以找到所需元素。为了避免需要扫描整个列表，您需要对列表中的节点进行附加引用，在这种情况下，它不再是简单的链表。
二叉树通过固有的排序和可导航性实现更快速的搜索和插入。
我过去成功使用的一种替代方法是SkipList。这类似于链表，但具有额外的引用，可使搜索性能与二叉树相当。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接