LinkedList和二叉搜索树之间的区别
ash*_*lal 37 language-agnostic linked-list binary-search-tree data-structures
链接列表和BinarySearchTree之间的主要区别是什么？BST只是维护LinkedList的一种方式吗？我的导师谈到了LinkedList,然后讨论了BST,但没有比较它们或者没有说何时更喜欢一个而不是另一个.这可能是一个愚蠢的问题,但我真的很困惑.如果有人能够以简单的方式澄清这一点,我将不胜感激.
Too*_*the 78
链接列表:
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
------ ------ ------
- 你的图表看起来棒极了。你是如何生成它们的？ (3认同)
CMS*_*CMS 16
甲二叉搜索树是一个二叉树,其中,每个内部节点X存储元件,例如,存储在的左子树的元素X是小于或等于X和存储在右子树的元素X是大于或等于x.
现在,链接列表由一系列节点组成,每个节点包含任意值以及指向下一个和/或前一个节点的一个或两个引用.
Vin*_*nie 13
在计算机科学中,二叉搜索树(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).
它们确实有相似之处，但主要区别在于二叉搜索树旨在支持有效搜索元素或“键”。
二叉搜索树，就像双向链表一样，指向结构中的另外两个元素。然而，当向结构添加元素时，而不是仅仅将它们附加到列表的末尾，二叉树被重新组织，以便链接到“左”节点的元素小于当前节点而链接到“右”节点的元素节点大于当前节点。
在一个简单的实现中，新元素与结构的第一个元素（树的根）进行比较。如果小于，则采用“左”分支，否则检查“右”分支。这对每个节点继续进行，直到发现一个分支是空的；新元素填补了那个位置。
使用这种简单的方法，如果按顺序添加元素，您最终会得到一个链表（具有相同的性能）。通过重新排列节点，存在不同的算法来保持树中的某种平衡度量。例如，AVL 树会尽最大努力使树尽可能保持平衡，从而提供最佳搜索时间。红黑树不能保持树的平衡，导致搜索速度稍慢，但在插入或删除键时平均做的工作较少。
- +1 为什么这个（正确）答案被低估，而原始（奇怪）问题被高票？我不明白... (2认同)