差之间的一个链表和一个二元的搜索树

https://stackoverflow.com/questions/270080

06-07-2019
|

题

有哪些主要差异之间的联系清单和一个BinarySearchTree?是BST只是一种方式保持一个链表?我的老师谈过链表，然后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实际上并没有太多共同之处，只是它们都是充当容器的数据结构。 链接列表 基本上允许您在任何位置有效插入和删除元素在列表中，同时保持列表的顺序。此列表使用从一个元素到下一个元素（通常是前一个元素）的指针实现。

另一方面， 二进制搜索树 是一个数据更高抽象的结构（即未指定如何在内部实现）允许有效搜索（即，为了找到您不必查看所有元素的特定元素。

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

实际上非常简单。链表只是一堆链接在一起的项目，没有特别的顺序。你可以把它想象成一个从不分支的真树：

1 - ＆gt; 2 - ＆gt; 5 - ＆gt; 3 - ＆gt; 9 - ＆gt; 12 - ＆gt; | i。（最后是对终止空的ascii-art尝试）

二进制搜索树有两种不同之处：二进制部分意味着每个节点都有 2 子节点，而不是一个节点，搜索部分意味着这些子节点被安排来加速搜索 - 仅左侧较小的项目，右侧只有较大的项目：

9没有左孩子，1,2和12是“叶子”。 - 他们没有分支。

有意义吗？

对于大多数“查找”而言各种用途，BST更好。但是，仅仅为了“保留一系列事情来处理后来的先进先出或后进先出”各种各样的事情，链表可能会很好。

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

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

二叉树通过固有的排序和导航，可以更快速地进行搜索和插入。

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

链表就是......列表。它是线性的;每个节点都有一个对下一个节点的引用（如果您正在谈论一个双向链表，则为前一个节点）。树枝---每个节点都有对各种子节点的引用。二叉树是一种特殊情况，其中每个节点只有两个子节点。因此，在链表中，每个节点都有一个前一个节点和一个下一个节点，而在二叉树中，一个节点有一个左子节点，右子节点和父节点。

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

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

二元搜索树，如双向链表，指向结构中的另外两个元素。然而，当向结构添加元素时，不是仅仅将它们附加到列表的末尾，而是重新组织二进制树，以便链接到“左”的元素。节点小于当前节点，并且元素链接到“右”节点。节点大于当前节点。

在一个简单的实现中，将新元素与结构的第一个元素（树的根）进行比较。如果它更少，则“左”表示“左”。采取分支，否则采用“正确”的分支。检查分支。这将继续每个节点，直到发现一个分支为空;新元素填补了这个位置。

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

链接列表是直线数据，相邻节点彼此连接，例如A-＆GT; B-＆℃。你可以把它当作直篱笆。

BST是一种分层结构，就像一棵树，主干连接到分支，而那些分支又连接到其他分支，依此类推。 “二元”是指“二元”。这里的单词表示每个分支最多连接两个分支。

您使用链接列表仅表示直接数据，每个项目最多连接一个项目;而您可以使用BST将项目连接到两个项目。您可以使用BST来表示家庭树等数据，但这将成为n-ary搜索树，因为每个人可以有两个以上的孩子。

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

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

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

来自维基百科的链接列表，以及二进制搜索树，也来自维基百科。

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

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

二叉搜索树是完全不同的东西。它有一个根节点，根节点最多有两个子节点，每个子节点最多可以有两个子注释等。这是一个非常聪明的数据结构，但在这里解释起来有点单调乏味。查看维基百科artcle 。

许可以下： CC-BY-SA 和归因

不隶属于 StackOverflow