AVL树

AVL树(高度平衡二叉树)

1962年苏联学者G. M. Adelson-Velsky和E. M. Landis提出AVL树，是计算机史上第一种自平衡二叉树。AVL树通常也被称为高度平衡二叉树，因为AVL树的形态受左右子树高度的约束。下面给出AVL树的定义：

1) AVL树：AVL树首先是BST，其要么是空树，要么左右子树都是AVL树且两者的高度差小于2；

通常称AVL树中任意节点\(x\)的左子树高度减右子树高度的差值为\(x\)的平衡因子(balance factor)。那么对于任何非空的AVL树，其树根的平衡因子只能取-1,0,1。下面给出AVL树的简单性质，其也可看作AVL树的非递归定义：

a1) 一个BST是AVL树 \(\Leftrightarrow\) 该BST所有节点的左右子树高度差都小于2；

上图是AVL树形态的特例，其所有非叶子节点的平衡因子都为-1，直观上看其左右子树的规模差距并不太大。一般的自平衡二叉树仅仅是为了让BST运算的代价更低，故本文对其运算的定义和前文对BST运算的定义一致，但要额外保证每次运算前后二叉树是AVL树，且运算代价和BST运算一样以树高为上界，否则构造AVL树就失去意义。另外可发现BST的\(find\)不会改变树结构，符合AVL树运算的要求，故之后只需讨论另外2种运算的实现。下述性质将保证AVL树是自平衡二叉树：

a2) 包含\(n\geq 0\)个节点的AVL树的高度以\(1.441\log_2{(n+2)}-0.3277\)为上界，且这个界足够准确；

证明：设\(N_h\)是高度为\(h\geq 0\)的AVL树所需的最小节点数。则\(N_0=0,N_1=1\)。由\(N_h\)的定义容易用反证法验证\(N\)严格单调递增，于是有\(N_h=N_{h-1}+N_{h-2}+1\)(\(h\geq 2\))。设\(S_h=N_h+1\)以去掉常数，则\(S_h=S_{h-1}+S_{h-2}\)，设\(F_n\)(\(n\geq 1\))是斐波那契数列，观察并验证\(S_h\)首项有\(N_h+1=S_h=F_{h+2}\)(\(h\geq 0\))，结合\(F\)的通项\(N_h=\frac{1}{\sqrt{5}}\big((\frac{1+\sqrt{5}}{2})^{h+2}-(\frac{1-\sqrt{5}}{2})^{h+2}\big)-1\)，括号中第二项小于1可放缩为\(N_h > \frac{1}{\sqrt{5}}(\frac{1+\sqrt{5}}{2})^{h+2}-2\)，移项后取对数有\(h < \log_{(1+\sqrt{5})/2}\big(\sqrt5(N_h+2)\big)-2\)。为方便其他文章对照，换底为2并用数值表示常数有\(h <\frac{\log_2{(N_h+2)}}{\log_2{((1+\sqrt{5})/2)}} + \frac{\log_2{\sqrt{5}}}{\log_2{((1+\sqrt{5})/2)}}-2< 1.441\log_2{(N_h+2)}-0.3277\)。设含\(n\geq 0\)个节点的AVL树的最大高度为\(H(n)\)，则\(H(n) < 1.441\log_2{(N_{H(n)}+2)}-0.3277 \leq 1.441\log_2{(n+2)}-0.3277\)。整个过程对不等式的放缩程度很小，所以\(N_{H(n)} = n\)时可认为\(1.441\log_2{(n+2)}-0.3277\)是准确的。

上述性质说明AVL树比完全二叉树“更高”，因为前者的\(\log_2{(x)}\)函数的系数约为1.441，后者的则为1。

AVL树的旋转

AVL树使用的旋转与之前讨论BST的文章中的一致，但AVL树会根据一定的前提和流程执行旋转，故这里预先打包并讨论这部分内容，首先用\(rotate\)运算表示执行旋转的流程，\(rotate(x)\)的功能是使\(x\)子树符合AVL树定义(执行后子树根不再是\(x\))，其执行的前提是\(x\)的左右子树都是AVL树且两者的高度差等于2。下面给出\(rotate\)的步骤并在其中做出关键说明：

1) \(rotate(x)\)：设\(a\)为\(x\)此时的平衡因子，然后分情况处理：

1.1) \(a=-2\)：设\(y=x.right\)，显然此时\(y\)非空。设\(b\)为\(y\)此时的平衡因子，下面分情况讨论：

1.1.1) \(b=-1\)：左旋转\(x\)(上图第1张)。此时新树根为\(y\)且高度降低1；

1.1.2) \(b=0\)：左旋转\(x\)(上图第1张)。此时新树根为\(y\)且高度无变化；

1.1.3) \(b=1\)：设\(z=y.left\)，显然此时\(z\)非空。右旋转\(y\)然后左旋转\(x\)(上图第2张)。此时新树根为\(z\)且高度降低1；

1.2) \(a=2\)：设\(y=x.left\)，显然此时\(y\)非空。设\(b\)为\(y\)此时的平衡因子，下面分情况讨论：

1.2.1) \(b=1\)：右旋转\(x\)(上图第3张)。此时新树根为\(y\)且高度降低1；

1.2.2) \(b=0\)：右旋转\(x\)(上图第3张)。此时新树根为\(y\)且高度无变化；

1.2.3) \(b=-1\)：设\(z=y.right\)，显然此时\(z\)非空。左旋转\(y\)然后右旋转\(x\)(上图第4张)。此时新树根为\(z\)且高度降低1；

通常可按实际旋转步骤将\(rotate\)分为左旋、右左旋、右旋、左右旋这4种情况。但本文按\(a,b\)分出6种情况，原因是\(b=0\)的情况较特殊，其不改变高度且仅在\(remove\)中可能出现。另外在\(rotate(x)\)执行完时，不难发现新子树根总是此时的\(x.parent\)。最后为方便之后讨论，要求\(rotate\)必须返回执行前后的高度变化(即0或-1)。

AVL树的插入运算

先直接给出AVL树上的\(insert(k)\)运算的步骤如下：

1) 在AVL树上执行BST的\(insert(k)\)运算(按之前讨论BST的文章中的步骤)，执行完时将新增的节点计为\(x\)；

2) 将\(x\)的所有祖先由近到远计为\(x_1…x_n\)并迭代它们，计每轮迭代的当前节点为\(x_i\)，每轮迭代的步骤分情况如下：

2.1) 此时\(x_i\)的左右子树高度差小于2且\(x_i\)的高度等于BST插入前\(x_i\)的高度：退出迭代；

2.2) 此时\(x_i\)的左右子树高度差小于2且\(x_i\)的高度不等于BST插入前\(x_i\)的高度：继续迭代；

2.3) 此时\(x_i\)的左右子树高度差大于等于2：执行\(rotate(x_i)\)，退出迭代；

这里讨论上述步骤是如何构造的。首先若\(x_1…x_n\)为空，则BST插入后整个二叉树仅包含节点\(x\)，显然符合AVL树定义，故之后认为\(x_1…x_n\)非空。然后考虑通过一种迭代\(x_1…x_n\)的过程来使整个二叉树成为AVL树，要求每轮迭代都检查\(x_i\)子树是否是AVL树，若不是则调整\(x_i\)子树的内部结构使其成为AVL树(子树根可能不再是\(x_i\))。注意在BST插入完成时\(x_1\)的左右子树都是AVL树(包括空树)，因为其一个子树不受BST插入影响，另一子树仅含节点\(x\)，于是这个迭代过程不仅能保证整个二叉树是AVL树，还能保证每轮迭代开始时当前节点\(x_i\)的左右子树都是AVL树，可利用这一点构造迭代步骤本身。

然后注意到在上述迭代框架下，若某轮迭代结束时原\(x_i\)子树(子树根可能不再是\(x_i\))的高度和BST插入前相同，则此时可确定整个二叉树是AVL树，因为若\(x_{i+1}\)存在，则\(x_{i+1}\)的左右子树都是AVL树且两者的高度与BST插入前相同，于是\(x_{i+1}\)是AVL树且高度与BST插入前相同……进而\(x_{i+1}…x_n\)都是AVL树，说明这时能停止后续的迭代。于是可进一步要求整个迭代过程在每轮迭代都检查\(x_i\)是否是AVL树，若不是则调整\(x_i\)子树的内部结构使其成为AVL树(子树根可能不再是\(x_i\))，并且在该轮迭代结束时若原\(x_i\)子树(子树根可能不再是\(x_i\))的高度和BST插入前相同则退出迭代，否则继续迭代。注意在BST插入完成时\(x_1\)的左或右子树(\(x\)所在的子树)的高度相比BST插入前+1，因为\(x\)取代了原本的空子树，于是这个迭代过程能保证每轮迭代开始时当前节点\(x_i\)的左右子树都是AVL树且其中\(x\)所在子树的高度和BST插入前不同，可利用这一点构造迭代步骤本身。

最后实现“调整\(x_i\)子树的内部结构使其成为AVL树”的步骤。设上述迭代过程在第\(k\)轮首次遇到当前节点\(x_{k}\)不是AVL树的情况，首先若这种情况不存在，则整个迭代结束时，整个二叉树显然是AVL树。根据上述迭代框架，该轮迭代开始时\(x_{k}\)的左右子树都是AVL树并且其中\(x\)所在子树的高度和BST插入前不同，由于该轮迭代前的迭代过程不改变二叉树结构且\(x\)的加入只能使其祖先高度不变或+1，故此时\(x\)所在子树的高度等于BST插入前该子树的高度+1，且\(x_{k}\)不是AVL树只能因为其左右子树高度差大于1，那么\(x_{k}\)的左右子树高度差只能由BST插入前的1变为2，而这又使\(x_{k}\)的高度相比BST插入前+1。显然此时符合执行\(rotate(x_{k})\)的前提，根据\(rotate\)的步骤执行后原\(x_{k}\)子树成为AVL树且高度相比BST插入前不变或+1，根据上述迭代框架，若高度不变则可退出迭代，而高度+1的情况并不会出现，该情况说明\(rotate\)执行前\(x_k\)如上图的A节点(\(b=0\)的\(rotate\))，图中三角表示子树并标注了高度，由于B只有1个子树受BST插入影响，故BST插入前B的高度与此时相同，这说明A在BST插入前已不是AVL树，导致矛盾。结合上述讨论，整个迭代过程可在每轮迭代都检查\(x_i\)是否是AVL树，若\(x_i\)是AVL树且高度和BST插入前相同则退出迭代，若\(x_i\)是AVL树且高度和BST插入前不同则退出迭代，若\(x_i\)不是AVL树则执行\(rotate(x_i)\)后退出迭代。并且该迭代过程在每轮迭代开始时当前节点\(x_i\)的左右子树都是AVL树且其中\(x\)所在子树的高度等于BST插入前+1。最后根据上述迭代框架，每轮迭代开始时\(x_i\)是AVL树的充要条件是\(x_i\)的左右子树高度差小于2，故该迭代过程与上述\(insert\)步骤等价。

AVL树的删除运算

先直接给出AVL树上的\(remove(k)\)运算的步骤如下：

1) 在AVL树上执行BST的\(remove(k)\)运算(按之前讨论BST的文章中的步骤)，执行完时将失去的节点计为\(x\)；

2) 将\(x\)原本的所有祖先由近到远计为\(x_1…x_n\)并迭代它们，计每轮迭代的当前节点为\(x_i\)，每轮迭代的步骤分情况如下：

2.1) 此时\(x_i\)的左右子树高度差小于2且\(x_i\)的高度等于BST删除前\(x_i\)的高度：退出迭代；

2.2) 此时\(x_i\)的左右子树高度差小于2且\(x_i\)的高度不等于BST删除前\(x_i\)的高度：继续迭代；

2.3) 此时\(x_i\)的左右子树高度差大于等于2：执行\(\Delta{h}=rotate(x_i)\)，若\(\Delta{h}=0\)则退出迭代，否则继续迭代；

首先注意到\(remove\)最坏需执行二叉树高度\(O(h)\)次\(rotate\)，而\(insert\)至多执行1次\(rotate\)。上图是最坏情况的例子，其中虚线节点是BST删除去掉的节点，该节点原本的所有祖先都会被执行\(rotate\)，这使得AVL树的删除性能不如一些其他的自平衡二叉树。然后讨论上述步骤是如何构造的。首先若\(x_1…x_n\)为空，则BST删除后整个二叉树是空树或原二叉树中的某个子树，显然符合AVL树定义，故之后认为\(x_1…x_n\)非空。然后考虑通过一种迭代\(x_1…x_n\)的过程来使整个二叉树成为AVL树，要求每轮迭代都检查\(x_i\)子树是否是AVL树，若不是则调整\(x_i\)子树的内部结构使其成为AVL树(子树根可能不再是\(x_i\))。注意在BST删除完成时\(x_1\)的左右子树都是AVL树(包括空树)，因为两者是空树或原二叉树中的某个子树，于是这个迭代过程不仅能保证整个二叉树是AVL树，还能保证每轮迭代开始时当前节点\(x_i\)的左右子树都是AVL树，可利用这一点构造迭代步骤本身。

然后注意到在上述迭代框架下，若某轮迭代结束时原\(x_i\)子树(子树根可能不再是\(x_i\))的高度和BST删除前相同，则此时可确定整个二叉树是AVL树，因为若\(x_{i+1}\)存在，则\(x_{i+1}\)的左右子树都是AVL树且两者的高度与BST删除前相同，于是\(x_{i+1}\)是AVL树且高度与BST删除前相同……进而\(x_{i+1}…x_n\)都是AVL树，说明这时能停止后续的迭代。于是可进一步要求整个迭代过程在每轮迭代都检查\(x_i\)是否是AVL树，若不是则调整\(x_i\)子树的内部结构使其成为AVL树(子树根可能不再是\(x_i\))，并且在该轮迭代结束时若原\(x_i\)子树(子树根可能不再是\(x_i\))的高度和BST删除前相同则退出迭代，否则继续迭代。注意在BST删除完成时\(x_1\)的左或右子树(BST删除前\(x\)所在的子树)的高度相比BST删除前-1，这点根据BST删除的步骤不难验证，于是这个迭代过程能保证每轮迭代开始时当前节点\(x_i\)的左右子树都是AVL树且其中BST删除前\(x\)所在子树的高度与此时不同，可利用这一点构造迭代步骤本身。

最后实现“调整\(x_i\)子树的内部结构使其成为AVL树”的步骤。设上述迭代过程在第\(k_1\)轮首次遇到当前节点\(x_{k_1}\)不是AVL树的情况，首先若这种情况不存在，则整个迭代结束时，整个二叉树显然是AVL树。根据上述迭代框架，该轮迭代开始时\(x_{k_1}\)的左右子树都是AVL树并且其中BST删除前\(x\)所在子树的高度与此时不同，由于该轮迭代前的迭代过程不改变二叉树结构且节点\(x\)被删除只能使其原祖先的高度不变或-1，故BST删除前\(x\)所在子树的高度等于其此时的高度+1，且\(x_{k_1}\)不是AVL树只能因为其左右子树高度差大于1，那么\(x_{k_1}\)的左右子树高度差只能由BST删除前的1变为2，而这又使\(x_{k_1}\)的高度和BST删除前一致。此时符合\(rotate(x_{k_1})\)的前提，根据\(rotate\)的步骤执行后原\(x_{k_1}\)子树成为AVL树且高度相比BST删除前不变或-1，根据上述迭代框架，高度不变则可退出迭代，否则需继续迭代，这时设之后的迭代过程在第\(k_2\)轮首次遇到当前节点\(x_{k_2}\)不是AVL树的情况，若这种情况不存在，则整个迭代结束时，整个二叉树显然是AVL树。根据上述迭代框架，该轮迭代开始时\(x_{k_2}\)的左右子树都是AVL树并且其中BST删除前\(x\)所在子树的高度与此时不同，同理BST删除前\(x\)所在子树的高度等于其此时的高度+1，\(x_{k_2}\)的左右子树高度差为2，\(x_{k_2}\)的高度和BST删除前相同。此时符合\(rotate(x_{k_2})\)的前提，根据\(rotate\)的步骤执行后原\(x_{k_2}\)子树成为AVL树且高度相比BST删除前不变或-1，根据上述迭代框架，如果高度不变则可退出迭代，否则需继续迭代……结合上述讨论，整个迭代过程可在每轮迭代都检查\(x_i\)是否是AVL树，若\(x_i\)是AVL树且高度和BST删除前相同则退出迭代，若\(x_i\)是AVL树且高度和BST删除前不同则退出迭代，若\(x_i\)不是AVL树则先执行\(rotate(x_i)\)，并且若执行前后不改变原\(x_i\)子树的高度则退出迭代，否则继续迭代。并且该迭代过程在每轮迭代开始时当前节点\(x_i\)的左右子树都是AVL树，其中BST删除前\(x\)所在子树的高度等于该子树此时的高度+1。最后根据上述迭代框架，每轮迭代开始时\(x_i\)是AVL树的充要条件是\(x_i\)的左右子树高度差小于2，故该迭代过程与上述\(remove\)步骤等价。

总结与实现

上文给出了AVL树的运算步骤，但未说明每轮迭代如何获取当前节点在BST插入/删除前后的高度，及其左右子树在BST插入/删除后的高度差。首先可排除通过实时的递归来计算高度信息，因为这所带来的额外代价甚至超过了总节点数\(O(n)\)，所以一般会考虑用额外空间来维护这些高度信息，其中最为常见的是如下2种方案：

1) 在每个节点额外存储高度值\(height\)，并要求每次运算前后所有节点的\(height\)都正确。该方案也是大部分教材中的方案，其优点是\(height\)更易维护和利用，缺点是节点数越大，节点的平均\(height\)就越大，占的空间就越大；

2) 在每个节点额外存储平衡因子\(bfactor\)，并要求每次运算前后所有节点的\(bfactor\)都正确。其优点是任何节点的\(bfactor\)占的空间都是常数，缺点是\(bfactor\)的维护和利用相对更加繁琐，因为要根据\(bfactor\)推导高度信息；

在第一种方案下，需对上述AVL树的运算实现按如下方式进行补充和修改：

1) \(rotate(n)\)：额外要求执行前\(n\)左右子树所有节点的\(height\)正确，执行后原\(n\)子树(子树根已不是\(n\))所有节点的\(height\)正确。如果执行前满足该要求，那么在执行后设原\(n\)子树的新树根为\(r\)，此时只可能有\(r,r.left,r.right\)的\(height\)不正确(如果这些节点存在)，这一点根据\(rotate\)的步骤不难验证，于是直接利用它们的孩子来更新其自身的\(height\)即可；

2) \(insert\)：先在BST插入刚完成时初始化\(x.height=1\)。然后额外要求每轮迭代开始时\(x_i.height\)等于BST插入前\(x_i\)的高度值且其左右子树所有节点的\(height\)正确，结束时原\(x_i\)子树(子树根可能不再是\(x_i\))所有节点的\(height\)正确。首轮迭代开始时显然符合该要求，若某轮迭代开始时符合该要求，该轮迭代开始时可利用\(x_i\)的孩子得到此时\(x_i\)的正确高度(计为\(h\))和其左右子树的高度差，于是现在有足够的信息来判断进入(2.1)(2.2)(2.3)中的哪个子步骤，若进入(2.1)则无需额外步骤，若进入(2.2)则该轮迭代结束时需额外置\(x_i.height=h\)，若进入(2.3)则无需额外步骤，因为\(rotate\)已包含额外步骤。这样处理后，显然该轮迭代结束时原\(x_i\)子树所有节点的\(height\)正确，并且如果下轮迭代存在，则下轮迭代开始时显然满足上述要求；

3) \(remove\)：与\(insert\)同理，注意\(remove\)的(2.3)同样无需额外步骤，因为\(rotate\)已包含额外步骤；

在第二种方案下，需对上述AVL树的运算实现按如下方式进行补充和修改：

1) \(rotate(n)\)：额外要求执行前后原\(n\)子树(执行后子树根已不再是\(n\))所有节点的\(bfactor\)正确。实现该要求的逻辑本身不算很复杂，但其步骤描述起来较繁琐，故这里不展开，具体可根据上述\(rotate\)的图片进行分析，也可参考后文的具体程序；

2) \(insert\)：在BST插入完成时初始化\(x.bfactor=0\)，若\(x_1\)存在则根据\(x\)是左或右孩子将\(x_1.bfactor\)更新为此时的正确值。然后额外要求每轮迭代开始和结束时原\(x_i\)子树(子树根可能不再是\(x_i\))所有节点的\(bfactor\)正确。首轮迭代开始时显然符合该要求，若某轮迭代开始时符合该要求，根据上述讨论，此时\(x_i\)的左或右子树(\(x\)所在子树)的高度相比BST插入前一定+1，于是此时若\(x_i.bfactor=0\)则可反推出BST插入前\(x_i.bfactor\)等于-1或1，说明此时\(x_i\)的高度与BST插入前相等，若\(|x_i.bfactor|=1\)则可反推出BST插入前\(x_i.bfactor=0\)，说明此时\(x_i\)的高度等于BST插入前的高度+1，这样就有足够的信息判断进入(2.1)(2.2)(2.3)中的哪个子步骤，若进入(2.1)则无需额外步骤，若进入(2.2)则该轮迭代结束时如果\(x_{i+1}\)存在则将\(x_{i+1}.bfactor\)更新为此时的正确值，若进入(2.3)则无需额外步骤，因为\(rotate\)已包含额外步骤。这样处理后，显然该轮迭代结束时原\(x_i\)子树所有节点的\(bfactor\)都正确，并且如果下轮迭代存在，则下轮迭代开始时显然也满足上述要求；

3) \(remove\)：在BST删除完成时，若\(x_1\)存在则可根据\(x\)曾是左或右孩子来更新\(x_1.bfactor\)为正确值，注意到此时\(x\)不在二叉树上，确定\(x\)曾是左或右节点会稍麻烦(当然如果在BST删除时就额外记录该信息就很简单，但为能让\(remove\)运算与BST删除运算解耦，这里不采用这种方案)。根据之前文章的BST删除步骤，此时\(x\)的3个指针都与BST删除前一致且\(x\)在BST删除前至多有1个孩子，结合这点可给出更新\(x_{1}.bfactor\)的步骤。若\(x.left\)或\(x.right\)存在，则说明BST删除前\(x\)有唯一孩子\(y\)，删除后\(y\)取代\(x\)的位置，此时根据\(y\)是\(x_1\)的左或右孩子即可更新\(x_1.bfactor\)。否则若\(x_1.left\)或\(x_1.right\)存在，则BST删除前\(x\)无孩子且此时\(x_1\)仅有1个孩子，其空孩子显然就是原\(x\)的位置，进而可更新\(x_1.bfactor\)。否则说明BST删除前\(x\)无孩子且此时\(x_1\)无孩子，于是BST删除前\(x_1\)仅有1个孩子\(x\)，此时\(x_1.bfactor\)是BST删除前\(x_1\)的平衡因子且等于-1或1，可利用其判断\(x\)曾是左或右孩子，进而更新\(x_1.bfactor\)。之后与\(insert\)同理，注意\(remove\)的(2.3)同样无需额外步骤，因为\(rotate\)已包含额外步骤；

至此已经完整的按“自底向上”的思路构造了AVL树的运算(除了\(rotate\)的步骤是预先给出的)，并给出了2种AVL树的实现，这些运算的代价显然都以二叉树的高度\(O(h)\)为上界。AVL树整体上是符合直觉的，基于\(height\)的AVL树运算步骤也不复杂。但想要“自底向上”的构造运算则比较复杂，从空间上要考虑到祖先与后代的高度关系，从时间上要考虑到同个子树在BST运算前、BST运算后、\(rotate\)后的3个时刻的高度关系。事实上我在写本文时基本只参考了\(rotate\)的4种情况的图片，其他步骤确实是按上述思路自己构造的，如果只是给出运算步骤并证明其正确性，则可大幅度缩减篇幅。最后给出这2种AVL树的程序，这里采用面向对象的程序设计，之前讨论BST的文章中的BST类在此作为基类，其他未提到的细节见程序与注释。