二元搜尋樹和平衡树

快捷方式: 差异，相似，杰卡德相似系数，参考。

二元搜尋樹和平衡树之间的区别

二元搜尋樹 vs. 平衡树

二叉查找树（Binary Search Tree），也--有序二叉树（ordered binary tree）或排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树：. 平衡树是计算机科学中的一类数据结构。 平衡树是计算机科学中的一类改进的二叉查找树。一般的二叉查找树的查询复杂度是跟目标结点到树根的距离（即深度）有关，因此当结点的深度普遍较大时，查询的均摊复杂度会上升，为了更高效的查询，平衡树应运而生了。 在这里，平衡指所有叶子的深度趋于平衡，更广义的是指在树上所有可能查找的均摊复杂度偏低。.

加权平衡树

在计算机科学里面，加权平衡树（WBTs）是一种可以用来实现集合、字典（映射）和序列的平衡树。这些树结构在20世纪70年代被Nievergelt和Reingold作为有界限的自平衡树或BB树提出。让这些结构普及的是高德纳。 就像其他自平衡树一样，加权平衡树储存的账簿信息可以在树结构被插入和删除操作打乱时，通过平衡结点和操作树旋转来使树结构重新达到平衡。特别的地方是，加权平衡树的每个结点储存这个结点下子树的大小，并且这个结点左右子树的大小保持着某种内在联系。不同于AVL树（储存子树的高度）和红黑树（储存虚构的“颜色”位），加权平衡树储存记账信息的方式是对应用真正有用的属性：一棵树下元素的数量等于它的根的大小，然而这个根的大小是一个用来实现顺序统计树操作的有用数据，也就是说，可以得到一个大小为的集合下的最大元素或者决定一个顺序结构下一个元素的索引。 加权平衡树在函数程式语言社区下面非常受欢迎以及被用来实现MIT Scheme的集合和映射结构还有Haskell语言的实现。.

二元搜尋樹和加权平衡树 · 加权平衡树和平衡树 · 查看更多 »

AVL树

在计算机科学中，AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为1，所以它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的時間複雜度都是O(\log)。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。AVL树得名于它的发明者G. M. Adelson-Velsky和，他们在1962年的论文《An algorithm for the organization of information》中发表了它。 节点的平衡因子是它的左子树的高度减去它的右子树的高度（有時相反）。带有平衡因子1、0或 -1的节点被认为是平衡的。带有平衡因子 -2或2的节点被认为是不平衡的，并需要重新平衡这个树。平衡因子可以直接存储在每个节点中，或从可能存储在节点中的子树高度计算出来。.

AVL树和二元搜尋樹 · AVL树和平衡树 · 查看更多 »

关联数组

在计算机科学中，关联数组（），又称映射（）、字典（）是一个抽象的数据结构，它包含着类似于（键，值）的有序对。一个关联数组中的有序对可以重复（如C++中的multimap）也可以不重复（如C++中的map）。 这种数据结构包含以下几种常见的操作：.

二元搜尋樹和关联数组 · 关联数组和平衡树 · 查看更多 »

红黑树

红黑树（Red–black tree）是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。它是在1972年由鲁道夫·贝尔发明的，他称之为"对称二叉B树"，它现代的名字是在Leo J. Guibas和Robert Sedgewick于1978年写的一篇论文中获得的。它是复杂的，但它的操作有着良好的最坏情况运行时间，并且在实践中是高效的：它可以在\textO(\log n)时间内做查找，插入和删除，这里的n是树中元素的数目。.

二元搜尋樹和红黑树 · 平衡树和红黑树 · 查看更多 »

跳跃列表

在计算机科学领域，跳跃链表是一种数据结构，允许快速查询一个有序连续元素的数据链表。快速查询是通过维护一个多层次的链表，且每一层链表中的元素是前一层链表元素的子集（见右边的示意图）。一开始时，算法在最稀疏的层次进行搜索，直至需要查找的元素在该层两个相邻的元素中间。这时，算法将跳转到下一个层次，重复刚才的搜索，直到找到需要查找的元素为止。被挑过的元素可能被随机性地选择或确定性地选择，其中前者更为常见。.

二元搜尋樹和跳跃列表 · 平衡树和跳跃列表 · 查看更多 »

Treap

#重定向 树堆.

Treap和二元搜尋樹 · Treap和平衡树 · 查看更多 »