平衡树:修订间差异
外观
删除的内容 添加的内容
小 →基本操作 |
Ruiyi Qian(留言 | 贡献) 小 统一格式 |
||
(未显示3个用户的11个中间版本) | |||
第5行: | 第5行: | ||
}} |
}} |
||
'''平衡树'''是[[计算机科学]]中的一类数据结构,为改进的[[二叉查找树]]。一般的二叉查找树的查询复杂度取决于目标结点到树根的距离(即深度),因此当结点的深度普遍较大时,查询的均摊复杂度会上升 |
'''平衡树'''是[[计算机科学]]中的一类数据结构,为改进的[[二叉查找树]]。一般的二叉查找树的查询复杂度取决于目标结点到树根的距离(即深度),因此当结点的深度普遍较大时,查询的均摊复杂度会上升<ref name="knuth"> |
||
[[高德纳|Donald Knuth]]. ''[[计算机程序设计艺术|The Art of Computer Programming]]'', Volume 3: ''Sorting and Searching'', Second Edition. Addison-Wesley, 1998. {{ISBN|0-201-89685-0}}. Section 6.2.3: Balanced Trees, pp.458–481. |
|||
</ref>。为了实现更高效的查询,产生了'''平衡树'''。[[File:Unbalanced_binary_tree.svg|thumb|240px|不平衡的[[树_(数据结构)|树结构]]]] |
|||
在这里,平衡指所有叶子的深度趋于平衡,更广义的是指在树上所有可能查找的均摊复杂度偏低。 |
在这里,平衡指所有叶子的深度趋于平衡,更广义的是指在树上所有可能查找的均摊复杂度偏低。 |
||
第12行: | 第14行: | ||
==基本操作== |
==基本操作== |
||
旋转 |
旋转(rotate):几乎所有平衡树的操作都基于[[树旋转]]操作(也有部分基于重构,如[[替罪羊树]]),通过旋转操作可以使得树趋于平衡。对一棵查找树(search tree)进行查询、新增、删除等动作,所花的时间与树的高度h成比例,并不与树的容量n成比例。如果可以让树维持平衡,也就是让h维持在<math>O(\log{n})</math>的左右,就可以在<math>O(\log{n})</math>的复杂度内完成各种基本操作<ref name="knuth" />。 |
||
插入(insert):在树中插入一个新值。 |
插入(insert):在树中插入一个新值。 |
||
第35行: | 第37行: | ||
*[[加权平衡树]](Weight balanced tree):加权平衡树的每个结点储存这个结点下子树的大小,可以用来实现[[顺序统计树]]操作。优势在于占用空间相对较小。 |
*[[加权平衡树]](Weight balanced tree):加权平衡树的每个结点储存这个结点下子树的大小,可以用来实现[[顺序统计树]]操作。优势在于占用空间相对较小。 |
||
*[[2-3树]]:其内部节点(存在子节点的节点)要么有2个孩子和1个数据元素,要么有3个孩子和2个数据元素,叶子节点没有孩子,并且有1个或2个数据元素。2–3树和[[AA树]]是[[等距同构]]的,换句话说,对于每个2–3树,都至少有1个AA树和它的元素排列是相同的。 |
*[[2-3树]]:其内部节点(存在子节点的节点)要么有2个孩子和1个数据元素,要么有3个孩子和2个数据元素,叶子节点没有孩子,并且有1个或2个数据元素。2–3树和[[AA树]]是[[等距同构]]的,换句话说,对于每个2–3树,都至少有1个AA树和它的元素排列是相同的。 |
||
*[[AA树]]:AA树是[[紅黑樹|红黑树]]的一种变种,是Arne Andersson教授在1993年年在他的论文"Balanced search trees made simple"中介绍,设计的目的是减少[[紅黑樹|红黑树]]考虑的不同情况,区别于红黑树的是,AA树的红节点只能作为右叶子 |
*[[AA树]]:AA树是[[紅黑樹|红黑树]]的一种变种,是Arne Andersson教授在1993年年在他的论文"Balanced search trees made simple"中介绍,设计的目的是减少[[紅黑樹|红黑树]]考虑的不同情况,区别于红黑树的是,AA树的红节点只能作为右叶子,从而大大简化了维护[[2-3树]]的模拟。 |
||
*[[替罪羊树|替罪羊樹]]:其平衡基于部分重建,在非平衡的[[二叉搜索树]]中,每次操作以后检查操作路径,找到最高的满足左右子树大小大于平衡因子(alpha)乘以自身大小的结点,重建整个子树。这样就得到了替罪羊树,而被重建的子树的原来的根就被称为替罪羊节点。 |
*[[替罪羊树|替罪羊樹]]:其平衡基于部分重建,在非平衡的[[二叉搜索树]]中,每次操作以后检查操作路径,找到最高的满足左右子树大小大于平衡因子(alpha)乘以自身大小的结点,重建整个子树。这样就得到了替罪羊树,而被重建的子树的原来的根就被称为替罪羊节点。 |
||
第43行: | 第45行: | ||
*[[跳表]] |
*[[跳表]] |
||
*有序[[Vector (STL)|向量]] |
*有序[[Vector (STL)|向量]] |
||
*值域 |
*值域[[线段树]] |
||
*数字搜索树(DigitalSearchTree) |
*[[Trie|数字搜索树]](DigitalSearchTree) |
||
==应用== |
==应用== |
||
第50行: | 第52行: | ||
平衡树的排序方法,虽然在平均时间复杂度上也是<math> O(n\log n) </math>,但由于cache性能、树的调整操作等,性能上不如[[快速排序]]、[[堆排序]]、[[归并排序]]等同为<math> O(n\log n) </math>复杂度的排序。 |
平衡树的排序方法,虽然在平均时间复杂度上也是<math> O(n\log n) </math>,但由于cache性能、树的调整操作等,性能上不如[[快速排序]]、[[堆排序]]、[[归并排序]]等同为<math> O(n\log n) </math>复杂度的排序。 |
||
==参考文献== |
|||
{{reflist}} |
|||
==外部链接== |
|||
* [https://xlinux.nist.gov/dads/HTML/heightBalancedTree.html Dictionary of Algorithms and Data Structures: Height-balanced binary search tree] {{Wayback|url=https://xlinux.nist.gov/dads/HTML/heightBalancedTree.html |date=20181013023402 }} |
|||
* [http://adtinfo.org/ GNU libavl] {{Wayback|url=http://adtinfo.org/ |date=20090516003720 }}, a LGPL-licensed library of binary tree implementations in C, with documentation |
|||
{{计算机科学中的树}} |
{{计算机科学中的树}} |
||
{{Data structures}} |
|||
[[Category:数据结构]] |
[[Category:数据结构]] |
||
[[Category:树结构]] |
[[Category:树结构]] |
2022年3月12日 (六) 06:53的最新版本
此條目需要补充更多来源。 (2019年7月8日) |
平衡树是计算机科学中的一类数据结构,为改进的二叉查找树。一般的二叉查找树的查询复杂度取决于目标结点到树根的距离(即深度),因此当结点的深度普遍较大时,查询的均摊复杂度会上升[1]。为了实现更高效的查询,产生了平衡树。
在这里,平衡指所有叶子的深度趋于平衡,更广义的是指在树上所有可能查找的均摊复杂度偏低。
基本操作[编辑]
旋转(rotate):几乎所有平衡树的操作都基于树旋转操作(也有部分基于重构,如替罪羊树),通过旋转操作可以使得树趋于平衡。对一棵查找树(search tree)进行查询、新增、删除等动作,所花的时间与树的高度h成比例,并不与树的容量n成比例。如果可以让树维持平衡,也就是让h维持在的左右,就可以在的复杂度内完成各种基本操作[1]。
插入(insert):在树中插入一个新值。
删除(delete):在树中删除一个值。
查询前驱(predecessor):前驱定义为小于x,且最大的数。
查询后继(successor):后继定义为大于x,且最小的数。
在维护节点大小(size)后,可以支持以下操作:
查询排名(rank):排名定义为比x小的数的个数加一。
查询第k大:即排名为k的数。
各种平衡树[编辑]
- AVL树:是最早被发明的自平衡二叉查找树。在AVL树中,任一节点对应的两棵子树的最大高度差为1,因此它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的时间复杂度都是。增加和删除元素的操作则可能需要借由一次或多次树旋转,以实现树的重新平衡。AVL树得名于它的发明者G. M. Adelson-Velsky和Evgenii Landis,他们在1962年的论文An algorithm for the organization of information 中公开了这一数据结构。 节点的平衡因子是它的左子树的高度减去它的右子树的高度(有时相反)。带有平衡因子1、0或 -1的节点被认为是平衡的。带有平衡因子 -2或2的节点被认为是不平衡的,并需要重新平衡这个树。平衡因子可以直接存储在每个节点中,或从可能存储在节点中的子树高度计算出来。
- 树堆(Treap):是有一个随机附加域满足堆的性质的二叉搜索树,其结构相当于以随机数据插入的二叉搜索树。其基本操作的期望时间复杂度为。相对于其他的平衡二叉搜索树,Treap的特点是实现简单,且能基本实现随机平衡的结构。
- 伸展树(Splay tree):能在均摊的时间内完成基于伸展(Splay)操作的插入、查找、修改和删除操作。它是由丹尼尔·斯立特(Daniel Sleator)和罗伯特·塔扬在1985年发明的。在伸展树上的一般操作都基于伸展操作:假设想要对一个二叉查找树执行一系列的查找操作,为了使整个查找时间更小,被查频率高的那些条目就应当经常处于靠近树根的位置。于是想到设计一个简单方法,在每次查找之后对树进行调整,把被查找的条目搬移到离树根近一些的地方。伸展树应运而生。伸展树是一种自调整形式的二叉查找树,它会沿着从某个节点到树根之间的路径,通过一系列的旋转把这个节点搬移到树根去。 它的优势在于不需要记录用于平衡树的冗余信息。
- 红黑树 (Red–black tree):在1972年由鲁道夫·贝尔发明,被称为"对称二叉B树",它现代的名字源于Leo J. Guibas和Robert Sedgewick于1978年写的一篇论文。红黑树的结构复杂,但它的操作有着良好的最坏情况运行时间,并且在实践中高效:它可以在时间内完成查找,插入和删除,这里的n是树中元素的数目。
- 加权平衡树(Weight balanced tree):加权平衡树的每个结点储存这个结点下子树的大小,可以用来实现顺序统计树操作。优势在于占用空间相对较小。
- 2-3树:其内部节点(存在子节点的节点)要么有2个孩子和1个数据元素,要么有3个孩子和2个数据元素,叶子节点没有孩子,并且有1个或2个数据元素。2–3树和AA树是等距同构的,换句话说,对于每个2–3树,都至少有1个AA树和它的元素排列是相同的。
- AA树:AA树是红黑树的一种变种,是Arne Andersson教授在1993年年在他的论文"Balanced search trees made simple"中介绍,设计的目的是减少红黑树考虑的不同情况,区别于红黑树的是,AA树的红节点只能作为右叶子,从而大大简化了维护2-3树的模拟。
- 替罪羊樹:其平衡基于部分重建,在非平衡的二叉搜索树中,每次操作以后检查操作路径,找到最高的满足左右子树大小大于平衡因子(alpha)乘以自身大小的结点,重建整个子树。这样就得到了替罪羊树,而被重建的子树的原来的根就被称为替罪羊节点。
其他类型[编辑]
以下数据结构支持平衡树大多数操作,但实现有根本不同:
应用[编辑]
用于表示有序的线性数据结构,如优先队列、关联数组、键(key)-值(value)的映射等。自平衡的二叉查找树与哈希表的相比,各有优缺。平衡树在按序遍历所有键值时是量级最优的,哈希表不能。自平衡二叉查找树在查找一个键值时,最坏情况下时间复杂度优于哈希表, 对比;但平均时间复杂度逊于hash表,对比。
平衡树的排序方法,虽然在平均时间复杂度上也是,但由于cache性能、树的调整操作等,性能上不如快速排序、堆排序、归并排序等同为复杂度的排序。
参考文献[编辑]
- ^ 1.0 1.1 Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Second Edition. Addison-Wesley, 1998. ISBN 0-201-89685-0. Section 6.2.3: Balanced Trees, pp.458–481.
外部链接[编辑]
- Dictionary of Algorithms and Data Structures: Height-balanced binary search tree (页面存档备份,存于互联网档案馆)
- GNU libavl (页面存档备份,存于互联网档案馆), a LGPL-licensed library of binary tree implementations in C, with documentation
|
|