平衡へいこう树

平衡へいこう树是これ计算机つくえ科学かがく中なか的てき一类数据结构，为改进的二叉查找树。一般いっぱん的てき二叉查找树的查询复杂度取决于目标结点到树根的距离（即そく深度しんど），因いん此当结点的てき深度しんど普遍ふへん较大时，查询的てき均ひとし摊复杂度会かい上じょう升ます。为了实现更さら高だか效こう的てき查询，产生了りょう平衡へいこう树。

不ふ平衡へいこう的てき树结构

在ざい这里，平衡へいこう指ゆび所有しょゆう叶かのう子こ的てき深度しんど趋于平衡へいこう，更さら广义的てき是ぜ指ゆび在ざい树上所有しょゆう可能かのう查找的てき均ひとし摊复杂度偏へん低ひく。

平衡へいこう的てき树结构

基本きほん操作そうさ

旋转（rotate）：几乎所有しょゆう平衡へいこう树的操作そうさ都と基もと于树旋转操作そうさ（也有やゆう部分ぶぶん基もと于重构，如替がえ罪ざい羊ひつじ树），通つう过旋转操作そうさ可か以使得とく树趋于平衡へいこう。对一棵查找树（search tree）进行查询、新しん增ぞう、删除等とう动作，所しょ花はな的てき时间与树的高度こうどh成なり比例ひれい，并不与あずか树的容量ようりょうn成なり比例ひれい。如果可か以让树维持じ平衡へいこう，也就是ぜ让h维持在ざい$O(\log {n})$的てき左右さゆう，就可以在$O(\log {n})$的てき复杂度ど内ない完成かんせい各かく种基本きほん操作そうさ。

插入そうにゅう（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)$复杂度ど的てき排はい序じょ。

外部がいぶ链接

• 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