建设网站需要准备哪些内容,网站接入银联支付怎么做,适合手机上做的兼职,wordpress首页文章摘要本章的代码实现基于上一篇BST与优先队列的基类进行平衡二叉树#xff0c;即AVL树。 文章目录 AVL的概念AVL查询效率AVL的插入1.插入节点2.更新平衡因子BF3.旋转调整树的结构3.1 LL 右旋3.2 RR 左旋3.3 LR 左右双旋3.4 RL 右左双旋 4 插入总结 AVL的删除1.寻找删除节点2.更新平…本章的代码实现基于上一篇BST与优先队列的基类进行平衡二叉树即AVL树。 文章目录 AVL的概念AVL查询效率AVL的插入1.插入节点2.更新平衡因子BF3.旋转调整树的结构3.1 LL 右旋3.2 RR 左旋3.3 LR 左右双旋3.4 RL 右左双旋 4 插入总结 AVL的删除1.寻找删除节点2.更新平衡因子BF 旋转3.实际删除节点4.删除总结 总结 AVL的概念
总所周知BST在插入数据随机的情况下其搜索能达到O(logn)的性能但如果插入数据有序或是经过若干次的插入与删除BST将会退化甚至变为线性的链表这不利于搜索。如何保持BST的优秀查找性质同时又不至于过分的维护成本例如完全二叉树AVL树就是其中一个答案。AVL树通过维护左右子树高度差从而保证了搜索的效率AVL的定义如下
AVL树要么是空树那么满足以下两个条件AVL树的左右子树也是AVL树AVL节点的平衡因子绝对值不超过1平衡因子(balance factor)定义左右子树高度差左子树高度-右子树高度
AVL查询效率
AVL树的查询效率同样为O(logn)具体证明如下:使用数学归纳法假设高度为h的AVL树其所能容纳的最少节点数为N(h)(即容纳N个节点时AVL最大即最糟糕的高度)可以发现满足以下情况
h1时N(h)1h2时N(h)2当h3时最糟糕的树必然根节点BF不为0(因为BF0时左右子树都高h-1容纳节点必然多与1个h-2子树1个h-1子树)那么此时最糟糕的树 1个根节点 1个h-1的子树 1个h-2的子树即N(h) 1 N(h-1) N(h-2)令G(h)N(h)1,则G(h)F(h2)F为斐波那契数列而随着i的增大斐波那契数列有一个性质 F i F i − 1 → 5 1 2 Φ \frac{F_i}{F_{i-1}}→\frac{\sqrt{5}1}{2}\Phi Fi−1Fi→25 1Φ可以估算i较大时 F i ≈ Φ i 5 F_i\approx\frac{\Phi^i}{\sqrt{5}} Fi≈5 Φi N h F h 2 − 1 Φ h 2 5 − 1 N_hF_{h2}-1\frac{\Phi^{h2}}{\sqrt{5}}-1 NhFh2−15 Φh2−1 h l o g N h 1 − 2 l o g Φ 1 2 l o g 5 l o g Φ ≈ 1.44 l o g N h C h\frac{logN_h1-2log\Phi\frac{1}{2}log5}{log\Phi}\approx1.44logN_hC hlogΦlogNh1−2logΦ21log5≈1.44logNhC故得证AVL的搜索效率为O(logn)在最糟糕的情况下其搜索效率仅为完全二叉树的1.44倍退化性能不多。
AVL的插入
AVL的查找与BST完全一致因此无需赘述较为困难的是AVL的插入与删除因为必须维护AVL的平衡因子因此涉及BF的更新与树的旋转。再进一步之前我们需要意识到以下几点
AVL是递归定义的AVL的左右子树都是AVL树上一条性质意味着如果一个节点失衡只会影响局部而不一定是整体。那么通过调整局部的子树可以达到整体的平衡树的旋转前后如果不改变树的高度那么子树平衡的同时不影响父节点的BF说明调整完毕否则需要继续递归向上调整
1.插入节点
插入节点与BST一致唯一的区别在于AVL树我们使用了三叉链和bF需要注意parent节点的连接与bF的默认置零。
void insert(int key)
{TreeNode* cur this-root;TreeNode* pre cur;TreeNode* node new TreeNode(key);//利用pre和cur找到插入的位置while (cur){pre cur;if (key cur-val)cur cur-left;elsecur cur-right;}//根节点if (this-root nullptr){this-root node;return;}//在左边if (key pre-val)pre-left node;//右边elsepre-right node;node-parent pre;cur node;//.......
}2.更新平衡因子BF
当我们插入一个新的节点时必然会影响父节点的BF值如果改变了父节点的高度则会影响组父节点的BF因此我们必须向上溯源更新BF值更新原则如下
若插入的值key 溯源节点pre说明新节点位于pre的左子树左子树高度增大pre-bF若插入的值key 溯源节点pre说明新节点位于pre的右子树右子树高度增大pre-bF–
现在我们考虑更新后的pre的平衡因子bF从而判断是否继续向上溯源分析如下
首先明确根据AVL的定义更新前pre的bF可能取值为-1,0,1若更新后bF为0说明更新前为-1或1且新节点插入了较低的子树插入较低子树意味着pre的高度不变无需继续溯源插入完成跳出循环若更新后bF为-1或1说明更新前为0两子树高度一致在插入新节点后其中一颗子树高度增大因此pre的高度发生变化需要继续溯源prepre-parent,直到根节点为止。若更新后bF为-2或2说明更新前为-1或1且新节点插入了较高的子树此时pre失衡且pre为失衡的最小子树需要进行旋转调整因为insert造成的失衡可以通过1次旋转完成调整并且使pre的BF0因此跳出循环进入旋转模块。
void insert(int key)
{//......//上接插入节点bool unbanlance false;//更新bF值while (pre){//沿着搜索路径向上回溯修改bFif (key pre-val)pre-bF;else--pre-bF;//平衡if (pre-bF 0)return;//pre处失衡else if (pre-bF 2 || pre-bF -2){unbanlance true;break;}//继续向上调整else{cur pre;pre pre-parent;}}//......
}3.旋转调整树的结构
调整树的结构我们可以对失衡情况进行分类共有以下4类。
3.1 LL 右旋
如图所示 LL代表着这样一种情况
插入前P节点的BF为1L节点的BF为0必然是这种情况不可能P为1且L为1否则P不是最先找到节点代表着P的左子树比后子树高1L的左右子树一致插入后L和P的左子树高度增加1P节点的BF为2L节点的BF为1。此时P节点失衡我们采用右旋下降P节点上升L节点。右转后L和P节点的BF值都归0
//a为失衡节点b为a的左节点
void LL(TreeNode* a, TreeNode* b)
{a-left b-right;if (b-right ! nullptr)b-right-parent a;b-right a;b-parent a-parent;a-parent b;a-bF 0;b-bF 0;if (b-parentnullptr)this-root b;else if (b-val b-parent-val)b-parent-left b;elseb-parent-right b;
}3.2 RR 左旋
如图所示RR对应着LL的对称情况不必多说。
//a为失衡节点b为a的右节点
void RR(TreeNode* a, TreeNode* b)
{bool isRoot a-parent nullptr;a-right b-left;if (b-left ! nullptr)b-left-parent a;b-left a;b-parent a-parent;a-parent b;a-bF 0;b-bF 0;if (b-parent nullptr)this-root b;else if (b-val b-parent-val)b-parent-left b;elseb-parent-right b;
}3.3 LR 左右双旋
如图所示LR对应着这一种情况
插入前与LL的情况一致。插入后L的右子树高度增加1而P的左子树高度增加1P节点的BF为2L节点的BF为-1所需要进行的调整较为复杂但可以拆分为两步进行。首先对L、LR进行一次左旋下降L上升LR。之后对P、LR进行一次右旋下降P上升LR。左右双旋后LR的BF0而L和P的BF则需要根据插入节点所位于LR的位置进行判断也可根据LR之前的BF进行判断如果插入在LR的左子树则L-BF0,P-BF-1插在LR的右子树则L-BF1,P-BF0
//a为失衡节点b为a的左节点
void LR(TreeNode* a, TreeNode* b)
{TreeNode* c b-right;b-right c-left;a-left c-right;if (c-left ! nullptr)c-left-parent b;if (c-right ! nullptr)c-right-parent a;c-left b;c-right a;c-parent a-parent;b-parent c;a-parent c;//c就是插入节点if (c-bF 0){a-bF 0;b-bF 0;}//插入节点在c的左子树else if (c-bF 1){b-bF 0;a-bF -1;}else{b-bF 1;a-bF 0;}c-bF 0;if (c-parent nullptr)this-root c;else if (c-val c-parent-val)c-parent-left c;elsec-parent-right c;
}3.4 RL 右左双旋
如图所示RL对应着LR的对称情况不必多说。
//a为失衡节点b为a的右节点
void RL(TreeNode* a, TreeNode* b)
{TreeNode* c b-left;b-left c-right;a-right c-left;if (c-right ! nullptr)c-right-parent b;if (c-left ! nullptr)c-left-parent a;c-left a;c-right b;c-parent a-parent;a-parent c;b-parent c;if (c-bF 0){a-bF 0;b-bF 0;}else if (c-bF 1){a-bF 0;b-bF -1;}else{a-bF 1;b-bF 0;}c-bF 0;if (c-parent nullptr)this-root c;else if (c-val c-parent-val)c-parent-left c;elsec-parent-right c;
}4 插入总结
最后我们对插入做一个总结具体过程如下
首先从根节点出发找到新插入节点的位置空节点和其父节点插入节点从插入节点的父节点开始向上回溯更新BF若是更新后的BF1或-1则继续更新直到根节点为止若是更新后的BF0则插入结束返回若是更新后的BF2或-2则找到了最小的失衡AVL子树跳出循环修复该子树。若是失衡则根据失衡节点a和插入节点所在分支的子节点b的BF值判断是LL/RR/LR/RL中哪种情况并进行相应的旋转操作。
完整代码如下:
//插入
void insert(int key)
{TreeNode* cur this-root;TreeNode* pre cur;TreeNode* node new TreeNode(key);//利用pre和cur找到插入的位置while (cur){pre cur;if (key cur-val)cur cur-left;elsecur cur-right;}//根节点if (this-root nullptr){this-root node;return;}//在左边if (key pre-val)pre-left node;//右边elsepre-right node;node-parent pre;cur node;bool unbanlance false;//更新bF值while (pre){//沿着搜索路径向上回溯修改bFif (key pre-val)pre-bF;else--pre-bF;//平衡if (pre-bF 0)return;//pre处失衡else if (pre-bF 2 || pre-bF -2){unbanlance true;break;}//继续向上调整else{cur pre;pre pre-parent;}}//失衡状态需要调整if (unbanlance){//LL型if (pre-bF 2 cur-bF 1)LL(pre, cur);else if (pre-bF 2 cur-bF -1)LR(pre, cur);else if (pre-bF -2 cur-bF -1)RR(pre, cur);elseRL(pre, cur);}return;
}AVL的删除
相比于插入AVL的删除实际上可能更加困难正如BST的删除也比插入更难。与BST一致我们依然是从叶节点、单边节点和双边节点开始考虑。
1.寻找删除节点
我们删除节点的流程应为找到并记录删除节点-更新BF值-调整树结构-实际删除节点。
无删除节点返回叶节点记录下该节点和父节点单边节点记录下该节点和父节点双边节点采用替换删除法采用前驱左子树最大值或后继右子树最小值替换该删除节点的值实际删除节点为前驱或后继节点本程序采用后继记录下后继节点和父节点。删除节点是叶节点或单边节点同时是根节点的情况需要特殊处理。(双边节点实际上删的是后继节点所以不需要单独处理)
void remove(int key)
{TreeNode* cur this-root;TreeNode* pre nullptr;TreeNode* deleteNode nullptr;TreeNode* deleteParent nullptr;while (cur){if (key cur-val){pre cur;cur cur-right;}else if (key cur-val){pre cur;cur cur-left;}//找到了需要删除的节点else{//需要删除节点的左子树为空if (cur-left nullptr){//若是根节点将右子树作为新的根节点即可//根节点没有父节点无需更新bFif (cur-parent nullptr){root cur-right;if (root)root-parent nullptr;delete(cur);return;}else{//记录信息deleteNode cur;deleteParent pre;}}else if (cur-right nullptr){if (cur-parent nullptr){root cur-left;if (root)root-parent nullptr;delete(cur);return;}else{deleteNode cur;deleteParent pre;}}else{//左右子树都非空进行替换并且更新需要删除的位置//利用rightMin进行更新TreeNode* minRight cur-right;while (minRight-left)minRight minRight-left;//替换cur-val minRight-val;//标记删除节点deleteNode minRight;deleteParent minRight-parent;}break;}}//没有需要删除的节点if (deleteParent nullptr)return;//.......
}2.更新平衡因子BF 旋转
不同于插入在删除之中旋转可能会改变树的高度因此更新BF和旋转必须在一个循环中反复进行不能拆分进行。 毫无疑问我们依然需要确立更新原则更新原则如下
若删除的节点 溯源节点deleteParent说明删除节点位于deleteParent的左子树左子树高度减小deleteParent-bF–若删除的节点 溯源节点deleteParent说明删除节点位于deleteParent的右子树右子树高度增孝deleteParent-bF
现在我们考虑更新后的deleteParent的平衡因子bF从而判断是否继续向上溯源分析如下
依然明确根据AVL的定义更新前deleteParent的bF可能取值为-1,0,1若更新后bF为0说明更新前为-1或1删除了较高子树的节点继续向上回溯。若更新后bF为-1或1说明更新前为0两子树高度一致删除其中一棵子树的节点树的高度没有发生变化至此插入结束。若更新后bF为-2或2说明更新前为-1或1且删除了较低子树的节点此时deleteParent失衡需要进行旋转调整旋转调整分为6种情况其中4种情况会改变树的高度需要继续向上回溯。
以下为失衡时的6种情况以及对应的处理方法
当deleteParent的平衡因子BF为2deleteParent的左孩子平衡因子为1时即降低了R节点的树高与插入时的LL情况一致采用右旋旋转前的子树路径为P-L-L的左子树高度为11h旋转后的子树路径为L-L的左子树高度为1h右子树为L-P-(L右子树h-1)或(P右子树h-1)高度由h2→h1必须继续回溯。当deleteParent的平衡因子BF为2deleteParent的左孩子平衡因子为-1时即降低了R节点的树高与插入时的LR情况一致采用左右双旋同上进行分析高度h2→h1继续回溯。当deleteParent的平衡因子BF为2deleteParent的左孩子平衡因子为0时此时情况较为特殊降低了R的树高但是L的两个子树高度一致这是插入中没有的情况我们采用右旋改变平衡因子调整方法的方法进行右旋后将L-BF-1,P-BF1旋转前后的高度h2→h1高度没有变化不需要继续回溯当deleteParent的平衡因子BF为-2deleteParent的左孩子平衡因子为-1时第1种情况的对称情况左旋继续回溯。当deleteParent的平衡因子BF为-2deleteParent的左孩子平衡因子为1时第2种情况的对称情况右左双旋继续回溯当deleteParent的平衡因子BF为-2deleteParent的左孩子平衡因子为0时第3种情况的对称情况左旋改变平衡因子调整方法将R-BF1,P-BF-1不需要继续回溯。
void remove(int key)
{//.....//上接寻找删除节点//备份TreeNode* delP deleteParent;TreeNode* del deleteNode;//更新bFwhile (deleteParent){//删除左子树if (deleteNode-val deleteParent-val)--deleteParent-bF;elsedeleteParent-bF;//根据bF进一步判断//bF0说明原来为-1 或者 1此时改变了树的高度需要继续向上更新if (deleteParent-bF 0){deleteNode deleteParent;deleteParent deleteParent-parent;}//bF1 / -1说明原来为0此时没有修改树的高度高度由最高的子树决定不需要继续更新else if (deleteParent-bF 1 || deleteParent-bF -1){break;}//bF2 / -2失衡需要进行旋转else{//左边子树高if (deleteParent-bF 2){//LL情况if (deleteParent-left-bF 1)LL(deleteParent, deleteParent-left);//LRelse if (deleteParent-left-bF -1)LR(deleteParent, deleteParent-left);else{//由于右子树的降低而导致的失衡左节点的两个子树高度一致//可以采用LL进行处理但需要重新调整bFLL(deleteParent, deleteParent-left);//调整deleteNode和左子节点如今的位置deleteParent deleteParent-parent;//旋转前左子树1节点2个节点的子树AB高h 高h1右子树1个子树C高h-1 高h-1//旋转后左子树子树A 高h右子树原来根节点 左子树B高h右子树C高h-1 高h1//因此新的根节点左子树低于右子树右节点的子树则是左子树高于右子树deleteParent-bF -1;deleteNode-right-bF 1;//此时树的高度没有发生变化不需要继续向上更新故breakbreak;}}else{//RRif (deleteParent-right-bF -1)RR(deleteParent, deleteParent-right);//RLelse if (deleteParent-right-bF 1)RL(deleteParent, deleteParent-right);else{RR(deleteParent, deleteParent-right);deleteParent deleteParent-parent;deleteParent-bF 1;deleteParent-left-bF -1;break;}}//旋转会调整树的高度需要继续更新不需要更新的情况已经break了deleteNode deleteParent;deleteParent deleteParent-parent;}}//......
}3.实际删除节点
利用备份好的删除节点信息考虑单边节点和删除节点所位于的子树情况进行删除。
void remove(int key)
{//.....//上接bf调整和旋转//删除节点必然有一颗子树为空//删除节点的左子树为空if (del-left nullptr){//删除节点位于左子树if (del-val delP-val)delP-left del-right;elsedelP-right del-right;if (del-right ! nullptr)del-right-parent delP;}//右子树为空else{if (del-val delP-val)delP-left del-left;elsedelP-right del-left;//此时delteNode-left必然不为nullptr这种情况已经讨论过del-left-parent delP;}delete(del);return;
}4.删除总结
相比于插入删除需要注意的情况更多且存在旋转改变高度上层父节点也需要旋转的可能。在此就不再列删除流程而是记录一些关键点
对于删除的节点种类的选择叶节点、单边节点、双边节点双边采用替换删除法转为叶节点或单边节点更新BF和旋转树需要同时在循环内进行循环停止条件为不改变树高度或到达根节点不改变树高度分为删除本身不改变和旋转后恢复删除前高度两种情况后者只在父节点的BF2或-2且子节点BF0时出现
总体代码如下
void remove(int key)
{TreeNode* cur this-root;TreeNode* pre nullptr;TreeNode* deleteNode nullptr;TreeNode* deleteParent nullptr;while (cur){if (key cur-val){pre cur;cur cur-right;}else if (key cur-val){pre cur;cur cur-left;}//找到了需要删除的节点else{//需要删除节点的左子树为空if (cur-left nullptr){//若是根节点将右子树作为新的根节点即可//根节点没有父节点无需更新bFif (cur-parent nullptr){root cur-right;if (root)root-parent nullptr;delete(cur);return;}else{//记录信息deleteNode cur;deleteParent pre;}}else if (cur-right nullptr){if (cur-parent nullptr){root cur-left;if (root)root-parent nullptr;delete(cur);return;}else{deleteNode cur;deleteParent pre;}}else{//左右子树都非空进行替换并且更新需要删除的位置//利用rightMin进行更新TreeNode* minRight cur-right;while (minRight-left)minRight minRight-left;//替换cur-val minRight-val;//标记删除节点deleteNode minRight;deleteParent minRight-parent;}break;}}//没有需要删除的节点if (deleteParent nullptr)return;//备份TreeNode* delP deleteParent;TreeNode* del deleteNode;//更新bFwhile (deleteParent){//删除左子树if (deleteNode-val deleteParent-val)--deleteParent-bF;elsedeleteParent-bF;//根据bF进一步判断//bF0说明原来为-1 或者 1此时改变了树的高度需要继续向上更新if (deleteParent-bF 0){deleteNode deleteParent;deleteParent deleteParent-parent;}//bF1 / -1说明原来为0此时没有修改树的高度高度由最高的子树决定不需要继续更新else if (deleteParent-bF 1 || deleteParent-bF -1){break;}//bF2 / -2失衡需要进行旋转else{//左边子树高if (deleteParent-bF 2){//LL情况if (deleteParent-left-bF 1)LL(deleteParent, deleteParent-left);//LRelse if (deleteParent-left-bF -1)LR(deleteParent, deleteParent-left);else{//由于右子树的降低而导致的失衡左节点的两个子树高度一致//可以采用LL进行处理但需要重新调整bFLL(deleteParent, deleteParent-left);//调整deleteNode和左子节点如今的位置deleteParent deleteParent-parent;//旋转前左子树1节点2个节点的子树AB高h 高h1右子树1个子树C高h-1 高h-1//旋转后左子树子树A 高h右子树原来根节点 左子树B高h右子树C高h-1 高h1//因此新的根节点左子树低于右子树右节点的子树则是左子树高于右子树deleteParent-bF -1;deleteNode-right-bF 1;//此时树的高度没有发生变化不需要继续向上更新故breakbreak;}}else{//RRif (deleteParent-right-bF -1)RR(deleteParent, deleteParent-right);//RLelse if (deleteParent-right-bF 1)RL(deleteParent, deleteParent-right);else{RR(deleteParent, deleteParent-right);deleteParent deleteParent-parent;deleteParent-bF 1;deleteParent-left-bF -1;break;}}//旋转会调整树的高度需要继续更新不需要更新的情况已经break了deleteNode deleteParent;deleteParent deleteParent-parent;}}//删除节点必然有一颗子树为空//删除节点的左子树为空if (del-left nullptr){//删除节点位于左子树if (del-val delP-val)delP-left del-right;elsedelP-right del-right;if (del-right ! nullptr)del-right-parent delP;}//右子树为空else{if (del-val delP-val)delP-left del-left;elsedelP-right del-left;//此时delteNode-left必然不为nullptr这种情况已经讨论过del-left-parent delP;}delete(del);return;
}总结
总算把AVL树的博客写完了我发现大量的博客确实缺少了对于AVL删除的叙述有些可惜。之后的红黑树、B树、B树、哈夫曼树估计不会自己实现而是记录一下思路和细节也没有必要再费劲地去处理红黑树N多种情况。——2023.5.17
