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类在此作为基类,其他未提到的细节见程序与注释。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 | # 基于高度值height的AVL树 class Node: def __init__(self, key): self.key = key self.parent = None self.left = None self.right = None class BinarySearchTree: def __init__(self): self.root = None def find(self, k): root = self.root while root: if k == root.key: return root elif k < root.key: root = root.left else: root = root.right return None def insert(self, k): if not self.root: self.root = Node(k) return self.root root = self.root while root: if k < root.key: if not root.left: root.left = Node(k) root.left.parent = root return root.left root = root.left else: if not root.right: root.right = Node(k) root.right.parent = root return root.right root = root.right def remove(self, k): node = self.find(k) if not node: return False if not node.left and not node.right: if not node.parent: self.root = None elif node is node.parent.left: node.parent.left = None else: node.parent.right = None return node elif not node.left or not node.right: nchild = node.left if node.left else node.right if not node.parent: self.root = nchild nchild.parent = None elif node is node.parent.left: node.parent.left = nchild nchild.parent = node.parent else: node.parent.right = nchild nchild.parent = node.parent return node else: mostRight = node.left while mostRight.right: mostRight = mostRight.right if mostRight is mostRight.parent.left: mostRight.parent.left = mostRight.left if mostRight.left: mostRight.left.parent = mostRight.parent else: mostRight.parent.right = mostRight.left if mostRight.left: mostRight.left.parent = mostRight.parent node.key = mostRight.key return mostRight def _rightRotate(self, n): m = n.left n.left = m.right m.right = n if not n.parent: self.root = m elif n.parent.left is n: n.parent.left = m else: n.parent.right = m m.parent = n.parent n.parent = m if n.left: n.left.parent = n def _leftRotate(self, n): m = n.right n.right = m.left m.left = n if not n.parent: self.root = m elif n.parent.left is n: n.parent.left = m else: n.parent.right = m m.parent = n.parent n.parent = m if n.right: n.right.parent = n class AVLTree(BinarySearchTree): # 若n的孩子的height正确,可得到n的正确平衡因子 @staticmethod def _recursiveBFactor(n): return (n.left.height if n.left else 0) - (n.right.height if n.right else 0) # 若n的孩子的height正确,可得到n的正确高度 @staticmethod def _recursiveHeight(n): return 1 + max(n.left.height if n.left else 0, n.right.height if n.right else 0) # 最终返回rotate前后的高度变化 def _rotate(self, n): if self._recursiveBFactor(n) == -2: b = self._recursiveBFactor(n.right) if b == 1: self._rightRotate(n.right) self._leftRotate(n) else: b = self._recursiveBFactor(n.left) if b == -1: self._leftRotate(n.left) self._rightRotate(n) newRoot = n.parent if newRoot.left: newRoot.left.height = self._recursiveHeight(newRoot.left) if newRoot.right: newRoot.right.height = self._recursiveHeight(newRoot.right) newRoot.height = self._recursiveHeight(newRoot) return 0 if b == 0 else -1 def insert(self, k): node = super().insert(k) node.height = 1 # 初始化高度 n = node.parent while n: if abs(self._recursiveBFactor(n)) < 2: h = self._recursiveHeight(n) if h == n.height: break else: n.height = h n = n.parent else: self._rotate(n) break return node def remove(self, k): node = super().remove(k) if not node: return node n = node.parent while n: if abs(self._recursiveBFactor(n)) < 2: h = self._recursiveHeight(n) if h == n.height: break else: n.height = h n = n.parent else: if self._rotate(n) == 0: break else: newRoot = n.parent n = newRoot.parent return node |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 | # 基于平衡因子bfactor的AVL树 class Node: def __init__(self, key): self.key = key self.parent = None self.left = None self.right = None class BinarySearchTree: def __init__(self): self.root = None def find(self, k): root = self.root while root: if k == root.key: return root elif k < root.key: root = root.left else: root = root.right return None def insert(self, k): if not self.root: self.root = Node(k) return self.root root = self.root while root: if k < root.key: if not root.left: root.left = Node(k) root.left.parent = root return root.left root = root.left else: if not root.right: root.right = Node(k) root.right.parent = root return root.right root = root.right def remove(self, k): node = self.find(k) if not node: return False if not node.left and not node.right: if not node.parent: self.root = None elif node is node.parent.left: node.parent.left = None else: node.parent.right = None return node elif not node.left or not node.right: nchild = node.left if node.left else node.right if not node.parent: self.root = nchild nchild.parent = None elif node is node.parent.left: node.parent.left = nchild nchild.parent = node.parent else: node.parent.right = nchild nchild.parent = node.parent return node else: mostRight = node.left while mostRight.right: mostRight = mostRight.right if mostRight is mostRight.parent.left: mostRight.parent.left = mostRight.left if mostRight.left: mostRight.left.parent = mostRight.parent else: mostRight.parent.right = mostRight.left if mostRight.left: mostRight.left.parent = mostRight.parent node.key = mostRight.key return mostRight def _rightRotate(self, n): m = n.left n.left = m.right m.right = n if not n.parent: self.root = m elif n.parent.left is n: n.parent.left = m else: n.parent.right = m m.parent = n.parent n.parent = m if n.left: n.left.parent = n def _leftRotate(self, n): m = n.right n.right = m.left m.left = n if not n.parent: self.root = m elif n.parent.left is n: n.parent.left = m else: n.parent.right = m m.parent = n.parent n.parent = m if n.right: n.right.parent = n class AVLTree(BinarySearchTree): # 最终返回rotate前后的高度变化 def _rotate(self, x): if x.bfactor == -2: y, b = x.right, x.right.bfactor if b != 1: self._leftRotate(x) x.bfactor = 0 if b == -1 else -1 y.bfactor = 0 if b == -1 else 1 else: z, c = y.left, y.left.bfactor self._rightRotate(y) self._leftRotate(x) x.bfactor = 1 if c == -1 else 0 y.bfactor = -1 if c == 1 else 0 z.bfactor = 0 else: y, b = x.left, x.left.bfactor if b != -1: self._rightRotate(x) x.bfactor = 0 if b == 1 else 1 y.bfactor = 0 if b == 1 else -1 else: z, c = y.right, y.right.bfactor self._leftRotate(y) self._rightRotate(x) x.bfactor = -1 if c == 1 else 0 y.bfactor = 1 if c == -1 else 0 z.bfactor = 0 return 0 if b == 0 else -1 def insert(self, k): node = super().insert(k) node.bfactor = 0 # 初始化平衡因子 if not node.parent: return node node.parent.bfactor += 1 if node is node.parent.left else -1 n = node.parent while True: if abs(n.bfactor) < 2: if n.bfactor == 0: break else: if n.parent: n.parent.bfactor += 1 if n is n.parent.left else -1 n = n.parent else: break else: self._rotate(n) break return node def remove(self, k): node = super().remove(k) if not node or not node.parent: return node if node.left or node.right: node.parent.bfactor += -1 if node.parent.left is (node.left or node.right) else 1 elif node.parent.left or node.parent.right: node.parent.bfactor += -1 if node.parent.right else 1 else: node.parent.bfactor += -1 if node.parent.bfactor == 1 else 1 n = node.parent while True: if abs(n.bfactor) < 2: if abs(n.bfactor) == 1: break else: if n.parent: n.parent.bfactor += -1 if n is n.parent.left else 1 n = n.parent else: break else: if self._rotate(n) == 0: break else: newRoot = n.parent if newRoot.parent: newRoot.parent.bfactor += -1 if newRoot is newRoot.parent.left else 1 n = newRoot.parent else: break return node |