平衡树：修订间差异

以互动方式浏览历史

←上一版本

删除的内容添加的内容

可视化wikitext

行内

2022年3月12日 (六) 06:53的最新版本

平衡树是计算机科学中的一类数据结构，为改进的二叉查找树。一般的二叉查找树的查询复杂度取决于目标结点到树根的距离（即深度），因此当结点的深度普遍较大时，查询的均摊复杂度会上升^[1]。为了实现更高效的查询，产生了平衡树。

在这里，平衡指所有叶子的深度趋于平衡，更广义的是指在树上所有可能查找的均摊复杂度偏低。

基本操作[编辑]

旋转（rotate）：几乎所有平衡树的操作都基于树旋转操作（也有部分基于重构，如替罪羊树），通过旋转操作可以使得树趋于平衡。对一棵查找树（search tree）进行查询、新增、删除等动作，所花的时间与树的高度h成比例，并不与树的容量n成比例。如果可以让树维持平衡，也就是让h维持在 $O(\log {n})$ 的左右，就可以在 $O(\log {n})$ 的复杂度内完成各种基本操作^[1]。

插入（insert）：在树中插入一个新值。

删除（delete）：在树中删除一个值。

查询前驱（predecessor）：前驱定义为小于x，且最大的数。

查询后继（successor）：后继定义为大于x，且最小的数。

在维护节点大小（size）后，可以支持以下操作：

查询排名（rank）：排名定义为比x小的数的个数加一。

查询第k大：即排名为k的数。

各种平衡树[编辑]

AVL树：是最早被发明的自平衡二叉查找树。在AVL树中，任一节点对应的两棵子树的最大高度差为1，因此它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的时间复杂度都是 $O(\log {n})$ 。增加和删除元素的操作则可能需要借由一次或多次树旋转，以实现树的重新平衡。AVL树得名于它的发明者G. M. Adelson-Velsky和Evgenii Landis，他们在1962年的论文An algorithm for the organization of information 中公开了这一数据结构。节点的平衡因子是它的左子树的高度减去它的右子树的高度（有时相反）。带有平衡因子1、0或 -1的节点被认为是平衡的。带有平衡因子 -2或2的节点被认为是不平衡的，并需要重新平衡这个树。平衡因子可以直接存储在每个节点中，或从可能存储在节点中的子树高度计算出来。
树堆（Treap）：是有一个随机附加域满足堆的性质的二叉搜索树，其结构相当于以随机数据插入的二叉搜索树。其基本操作的期望时间复杂度为 $O(\log {n})$ 。相对于其他的平衡二叉搜索树，Treap的特点是实现简单，且能基本实现随机平衡的结构。
伸展树（Splay tree）：能在均摊 $O(\log {n})$ 的时间内完成基于伸展（Splay）操作的插入、查找、修改和删除操作。它是由丹尼尔·斯立特（Daniel Sleator）和罗伯特·塔扬在1985年发明的。在伸展树上的一般操作都基于伸展操作：假设想要对一个二叉查找树执行一系列的查找操作，为了使整个查找时间更小，被查频率高的那些条目就应当经常处于靠近树根的位置。于是想到设计一个简单方法，在每次查找之后对树进行调整，把被查找的条目搬移到离树根近一些的地方。伸展树应运而生。伸展树是一种自调整形式的二叉查找树，它会沿着从某个节点到树根之间的路径，通过一系列的旋转把这个节点搬移到树根去。它的优势在于不需要记录用于平衡树的冗余信息。
红黑树（Red–black tree）：在1972年由鲁道夫·贝尔发明，被称为"对称二叉B树"，它现代的名字源于Leo J. Guibas和Robert Sedgewick于1978年写的一篇论文。红黑树的结构复杂，但它的操作有着良好的最坏情况运行时间，并且在实践中高效：它可以在 $O(\log {n})$ 时间内完成查找，插入和删除，这里的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）乘以自身大小的结点，重建整个子树。这样就得到了替罪羊树，而被重建的子树的原来的根就被称为替罪羊节点。

其他类型[编辑]

以下数据结构支持平衡树大多数操作，但实现有根本不同:

跳表
有序向量
值域线段树
数字搜索树（DigitalSearchTree）

应用[编辑]

用于表示有序的线性数据结构，如优先队列、关联数组、键(key)-值(value)的映射等。自平衡的二叉查找树与哈希表的相比，各有优缺。平衡树在按序遍历所有键值时是量级最优的，哈希表不能。自平衡二叉查找树在查找一个键值时，最坏情况下时间复杂度优于哈希表， $O(\log n)$ 对比 $O(n)$ ；但平均时间复杂度逊于hash表， $O(\log n)$ 对比 $O(1)$ 。

平衡树的排序方法，虽然在平均时间复杂度上也是 $O(n\log n)$ ，但由于cache性能、树的调整操作等，性能上不如快速排序、堆排序、归并排序等同为 $O(n\log n)$ 复杂度的排序。

参考文献[编辑]

^ ^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

[knuth-1] 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.

[1]

@@ 第1行： / 第1行： @@
+{{Refimprove|time=2019-7-8}}
-'''平衡树'''是[[计算机科学]]中的一类数据结构。
-[[平衡树]]是计算机科学中的一类改进的[[二叉查找树]]。一般的二叉查找树的查询复杂度是跟目标结点到树根的距离（即深度）有关，因此当结点的深度普遍较大时，查询的均摊复杂度会上升，为了更高效的查询，'''平衡树'''应运而生了。
+{{noteTA
-[[File:Unbalanced_binary_tree.svg|thumb|240px|不平衡的[[树_(数据结构)|树结构]]]]
+| G1 = IT|zh-cn:编程范型; zh-tw:程式設計法;|zh-cn:编程;zh-hk:編程;zh-tw:程式設計;
+}}
+'''平衡树'''是[[计算机科学]]中的一类数据结构，为改进的[[二叉查找树]]。一般的二叉查找树的查询复杂度取决于目标结点到树根的距离（即深度），因此当结点的深度普遍较大时，查询的均摊复杂度会上升<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|不平衡的[[树_(数据结构)|树结构]]]]
 在这里，平衡指所有叶子的深度趋于平衡，更广义的是指在树上所有可能查找的均摊复杂度偏低。
@@ 第9行： / 第14行： @@
 ==基本操作==
-几乎所有平衡树的操作都基于[[树旋转]]操作，通过旋转操作可以使得树趋于平衡。
+旋转（rotate）：几乎所有平衡树的操作都基于[[树旋转]]操作（也有部分基于重构，如[[替罪羊树]]），通过旋转操作可以使得树趋于平衡。对一棵查找树（search tree）进行查询、新增、删除等动作，所花的时间与树的高度h成比例，并不与树的容量n成比例。如果可以让树维持平衡，也就是让h维持在<math>O(\log{n})</math>的左右，就可以在<math>O(\log{n})</math>的复杂度内完成各种基本操作<ref name="knuth" />。
-对一棵查找树（search tree）进行查询/新增/删除 等动作, 所花的时间与树的高度h 成比例, 并不与树的容量 n 成比例。如果可以让树维持矮矮胖胖的好身材, 也就是让h维持在O(lg n)左右, 完成上述工作就很省时间。能够一直维持好身材, 不因新增删除而长歪的搜寻树, 叫做balanced search tree（平衡树）。
-旋转Rotate —— 不破坏左小右大特性的小手术
-平衡树有很多种, 其中有几类树维持平衡的方法, 都是靠整形小手术:
+插入（insert）：在树中插入一个新值。
-图中 x 与 y 为 nodes; A, B, C 为一整串的 subtrees。 试想: 如果 x 原来是 y 的 left child; 现在想将 x 变成 parent, 则树的其它部分应如何变化? y 必须变成 right child, 这样才能维持 BST 的特性 -- 左小右大。 至于 x 与 y 以下的其它部分, 可以整串 subtree 一起处理: x 原来的 left subtree (A), 调整后还是 x 的 left subtree; y 原来的 right subtree (C), 调整后还是 y 的 right subtree; 而 x 原来的 right subtree (B), 调整后很自然只有一个地方可以放: 变成 y 的 left subtree。 这些规则都不需要记, 因为如果你希望调整后还维持 BST 左小右大的特性, 这是唯一的答案。 把 x,y 两个值及 A,B,C 三棵 subtrees 内的三串值画在数在线看更清楚:
---------- x --------- y ---------
+删除（delete）：在树中删除一个值。
-A B C
-这个动作, 称为 right rotation 向右旋转, 或称为顺时针旋转 (clockwise)。 原来的 parent (y) 叫做 pivot, 原来的 child (x) 叫做 rotator。
+查询前驱（predecessor）：前驱定义为小于''x''，且最大的数。
-把上图反过来看, 如果原来的树长得像右图, 想将它改成左图, 则称为 left rotation 向左旋转, 或称为逆时针旋转 (counter-clockwise)。 原来的 parent (x) 叫做 pivot, 原来的 child (y) 叫做 rotator。
+查询后继（successor）：后继定义为大于''x''，且最小的数。
+在维护节点大小（size）后，可以支持以下操作：
+查询排名（rank）：排名定义为比x小的数的个数加一。
+查询第k大：即排名为''k''的数。
 ==各种平衡树==
+*[[AVL树]]：是最早被发明的[[自平衡二叉查找树]]。在AVL树中，任一节点对应的两棵子树的最大高度差为1，因此它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的[[时间复杂度]]都是<math>O(\log{n})</math>。增加和删除元素的操作则可能需要借由一次或多次[[树旋转]]，以实现树的重新平衡。AVL树得名于它的发明者[[格奥尔吉·阿杰尔松-韦利斯基|G. M. Adelson-Velsky]]和Evgenii Landis，他们在1962年的论文''An algorithm for the organization of information'' 中公开了这一数据结构。 节点的平衡因子是它的左子树的高度减去它的右子树的高度（有时相反）。带有平衡因子1、0或 -1的节点被认为是平衡的。带有平衡因子 -2或2的节点被认为是不平衡的，并需要重新平衡这个树。平衡因子可以直接存储在每个节点中，或从可能存储在节点中的子树高度计算出来。
-*[[AVL树]]，经典平衡树, 所有操作的最坏复杂度都是<math>O(\log{n})</math>的。
+*[[树堆]]（Treap）：是有一个随机附加域满足[[堆]]的性质的[[二叉搜索树]]，其结构相当于以随机数据插入的[[二叉搜索树]]。其基本操作的期望[[时间复杂度]]为<math>O(\log{n})</math>。相对于其他的[[平衡二叉搜索樹|平衡二叉搜索树]]，Treap的特点是实现简单，且能基本实现随机平衡的结构。
-*[[Treap]]，利用随机[[堆]]的期望深度来优化树的深度，达到较优的期望复杂度。
+*[[伸展树]]（Splay tree）：能在均摊<math>O(\log{n})</math>的时间内完成基于伸展（Splay）操作的插入、查找、修改和删除操作。它是由丹尼尔·斯立特（Daniel Sleator）和[[羅伯特·塔揚|罗伯特·塔扬]]在1985年发明的。在伸展树上的一般操作都基于伸展操作：假设想要对一个二叉查找树执行一系列的查找操作，为了使整个查找时间更小，被查频率高的那些条目就应当经常处于靠近树根的位置。于是想到设计一个简单方法，在每次查找之后对树进行调整，把被查找的条目搬移到离树根近一些的地方。伸展树应运而生。伸展树是一种自调整形式的二叉查找树，它会沿着从某个节点到树根之间的路径，通过一系列的旋转把这个节点搬移到树根去。 它的优势在于不需要记录用于平衡树的冗余信息。
-*[[伸展树]]，使得经常查找的结点深度较小，从而降低均摊复杂度。
+*[[红黑树]] （Red–black tree）：在1972年由[[鲁道夫·贝尔]]发明，被称为"'''对称二叉B树'''"，它现代的名字源于Leo J. Guibas和[[Robert Sedgewick]]于[[1978年]]写的一篇论文。红黑树的结构复杂，但它的操作有着良好的最坏情况[[算法分析|运行时间]]，并且在实践中高效：它可以在<math>O(\log{n})</math>时间内完成查找，插入和删除，这里的n是树中元素的数目。
-*[[红黑树]]。
+*[[加权平衡树]]（Weight balanced tree）：加权平衡树的每个结点储存这个结点下子树的大小，可以用来实现[[顺序统计树]]操作。优势在于占用空间相对较小。
-*[[加权平衡树]]。
+*[[2-3树]]：其内部节点（存在子节点的节点）要么有2个孩子和1个数据元素，要么有3个孩子和2个数据元素，叶子节点没有孩子，并且有1个或2个数据元素。2–3树和[[AA树]]是[[等距同构]]的，换句话说，对于每个2–3树，都至少有1个AA树和它的元素排列是相同的。
-*[[2-3树]]
+*[[AA树]]：AA树是[[紅黑樹|红黑树]]的一种变种，是Arne Andersson教授在1993年年在他的论文"Balanced search trees made simple"中介绍，设计的目的是减少[[紅黑樹|红黑树]]考虑的不同情况，区别于红黑树的是，AA树的红节点只能作为右叶子，从而大大简化了维护[[2-3树]]的模拟。
-*[[AA树]]
+*[[替罪羊树|替罪羊樹]]：其平衡基于部分重建，在非平衡的[[二叉搜索树]]中，每次操作以后检查操作路径，找到最高的满足左右子树大小大于平衡因子（alpha）乘以自身大小的结点，重建整个子树。这样就得到了替罪羊树，而被重建的子树的原来的根就被称为替罪羊节点。
-*[[替罪羊樹]]
-*[[节点大小平衡树]]
 ==其他类型==
-*[[跳表]]，一种支持平衡树大多数操作的数据结构
+以下数据结构支持平衡树大多数操作，但实现有根本不同:
+*[[跳表]]
+*有序[[Vector (STL)|向量]]
+*值域[[线段树]]
+*[[Trie|数字搜索树]]（DigitalSearchTree）
 ==应用==
-用于表示有序的线性数据结构，如[[优先队列]]、[[关联数组]]、键-值的[[映射]]等。自平衡的二叉查找树的实现与其竞争对手hash表的实现，各具有优缺点。自平衡二叉查找树在按序遍历所有键值时是量级最优的，hash表不能。自平衡二叉查找树在查找一个键值时，最坏情况下时间复杂度优于hash表， O(log n)对比O(n)；但平均时间复杂度逊于hash表，O(log n)对比O(1)。
+用于表示有序的线性数据结构，如[[优先队列]]、[[关联数组]]、键(key)-值(value)的[[映射]]等。自平衡的二叉查找树与哈希表的相比，各有优缺。平衡树在按序遍历所有键值时是量级最优的，哈希表不能。自平衡二叉查找树在查找一个键值时，最坏情况下时间复杂度优于哈希表， <math>O(\log n)</math>对比<math>O(n)</math>；但平均时间复杂度逊于hash表，<math>O(\log n)</math>对比<math>O(1)</math>。
-自平衡二叉查找树的排序方法，虽然在平均时间复杂度上也是O(n log n)，但由于cache性能、树的调整操作等，性能上不如快速排序、堆排序、合并排序。
+平衡树的排序方法，虽然在平均时间复杂度上也是<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:树结构]]