企业官网建设流程全解析

回顾：上一篇我们结束了 map&set的使用，接下来这篇文章让我们进入到 AVLTree 的学习，体会新的设计思路吧~

一 AVL树的概念

1. AVL树是一棵高度平衡二叉查找树，左右子树高度差的绝对值不超过1。
2. 每个结点有一个平衡因子（balance factor），这不是必须的。
3. 有些情况下，高度差不为0。

二 实现

2.1 AVLTreeNode

template<classK,classV>structAVLTreeNode{pair<K,V>_kv;AVLTreeNode<K,V>*_left;AVLTreeNode<K,V>*_right;AVLTreeNode<K,V>*_parent;int_bf;// balance factorAVLTreeNode(constpair<K,V>&kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0){}};

1. 这里的Node存储的是一个pair（键值对），应用场景更广一些。
2. 需要额外记录每个Node的_parent，后面要用到。
3. 实现的是带平衡因子（后面都简称bf）的AVL树。

2.2 AVLTree

template<classK,classV>classAVLTree{typedefAVLTreeNode<K,V>Node;public:// ...private:Node*_root=nullptr;};

搭个框架。

2.3 Insert

2.3.1 插入流程

（1）新增结点

• 按二叉搜索树规则来。
• 具体在这篇博客 C++ | 二叉搜索树 第三大块。
  代码：

boolInsert(constpair<K,V>&kv){if(_root==nullptr){_root=newNode(kv);returntrue;}Node*parent=nullptr;Node*cur=_root;while(cur){if(cur->_kv.first<kv.first){parent=cur;cur=cur->_right;}elseif(cur->_kv.first>kv.first){parent=cur;cur=cur->_left;}else{returnfalse;}}cur=newNode(kv);if(parent->_kv.first>kv.first){parent->_left=cur;}else{parent->_right=cur;}cur->_parent=parent;// ...}

（2）更新平衡因子

• 新增结点，更新 新增节点 - 根节点 路径上的bf。
• 具体后面展开讲。

（3）旋转

• 更新bf的过程中出现不平衡（左右子树高度差的绝对值超过1），需要旋转不平衡子树。
• 平衡后就不用继续往上更新bf了，完毕。

2.3.2 平衡因子更新

（1）更新原则

1. 平衡因子 = 右子树高度 - 左子树高度
2. 子树高度变化影响当前结点平衡因子。
3. 插入结点parent更新（新结点在左–，在右++）
4. 若parent的bf不为零则往上更新。

（2）停止更新条件

1. 更新后parent的bf为 零，表示parent所在子树高度不变。则parent的parent结点的bf不会受到影响，更新结束。
2. 更新后parent的bf为 1 或 -1，表示parent所在子树原先平衡，更新后高度改变。则parent的parent结点的bf也会受到影响，往上继续更新。
3. 更新后parent的bf为 2 或 -2，表示parent所在子树已经不平衡了，需要旋转处理。
4. 不断更新到root，bf为 1 或 -1 停止。

（3）代码实现

1. 先套一个框架：新增节点 的 parent 存在时，进入循环体。

while(parent){//...}

2. 更新 parent 的 bf：

if(parent->_kv.first>kv.first){parent->_bf--;}else{parent->_bf++;}

3. 判断 parent 的 bf 是否为零：

if(parent->_bf==0){break;}elseif(abs(parent->_bf)==1){// continuecur=parent;parent=parent->_parent;}elseif(abs(parent->_bf)==2){// rotatebreak;}else{// errorexit(-1);}

接下来进入rotate（上面第二个else if）。

2.3.3 旋转

旋转共有四种：左旋转、右旋转、左右双旋 和 右左双旋。

（1）旋转原则

1. 旋转后保持搜索树的特性。
2. 让旋转的树从不平衡变平衡，其次降低旋转树的高度。

（2）右单旋

左子树太高了。
即如图中a子树新增一个结点 高h+1，太高了。

①过程
subL的右子树（subLR）变为parent结点的左子树，subL结点到parent结点的位置上。

• parent上面还有parentParent，后面会用到。

最终实现结果：

②代码实现
框架：

voidRotateR(Node*parent){//...}

• 注意修改结点位置也要修改它的_parent。

1. 记录各个结点（根据传参parent）

Node*subL=parent->_left;Node*subLR=subL->_right;Node*parentParent=parent->_parent;

2. 处理parent和subLR

parent->_left=subLR;if(subLR){subLR->_parent=parent;}

• 存在subLR为nullptr的情况。

3. 处理subL和parent

subL->_right=parent;parent->_parent=subL;

4. 处理parentParent和subL

if(parentParent){if(parentParent->_left==parent){parentParent->_left=subL;}else{parentParent->_right=subL;}subL->_parent=parentParent;}else{_root=subL;_root->_parent=nullptr;}

• 涉及parentParent存在不存在的问题。
• 若存在，涉及parentParent存在于哪个分支的问题。
  

5. 记得更新bf

parent->_bf=subL->_bf=0;

（3） 左单旋

右子树太高了。
即如图中a子树新增一个结点后 高h+1：

①过程
subR的左子树（subRL）变为parent结点的右子树，subR结点到parent结点的位置上。
最终实现结果：

②代码实现
跟右单旋代码类似：

voidRotateL(Node*parent){Node*subR=parent->_right;Node*subRL=subR->_left;Node*parentParent=parent->_parent;parent->_right=subRL;if(subRL){subRL->_parent=parent;}subR->_left=parent;parent->_parent=subR;if(parentParent){if(parentParent->_left==parent){parentParent->_left=subR;}else{parentParent->_right=subR;}subR->_parent=parentParent;}else{_root=subR;_root->_parent=nullptr;}parent->_bf=subR->_bf=0;}

（4）左右双旋

左子树高了，左子树的右子树高了。

• 即图中 e子树 新增结点后 高h。
• subL 总高h+2，跟c子树高度差超过1了。
  
  ①过程
  subL左单旋 >> parent右单旋。
  实现结果：
  
  ②代码实现
  框架:

voidRotateRL(Node*parent){//...}

1. 记录各个结点

Node*subL=parent->_left;Node*subLR=subL->_right;Node*parentParent=parent->_parent;

额外记录一下bf：

intbf=subLR->_bf;

2. 旋转

RotateL(parent->_left);RotateR(parent);

这个直接复用写过的代码。

3. 重点： 更新bf

if(bf==0){subL->_bf=0;subLR->_bf=0;parent->_bf=0;}elseif(bf==-1){subL->_bf=0;subLR->_bf=0;parent->_bf=1;}elseif(bf==1){subL->_bf=-1;subLR->_bf=0;parent->_bf=0;}else{exit(-1);}

演示一下这几种情况：

（5）右左双旋

右子树高了，右子树的左子树高了。

• 即图中 e子树 新增结点后 高h。
  
  ①过程
  subR右单旋 >> parent左单旋。
  结果：
  
  ②代码实现
  跟左右双旋类似，直接上代码：

voidRotateRL(Node*parent){Node*subR=parent->_right;Node*subRL=subR->_left;Node*parentParent=parent->_parent;intbf=subRL->_bf;RotateR(subR);RotateL(parent);if(bf==0){subR->_bf=0;subRL->_bf=0;parent->_bf=0;}elseif(bf==-1){subR->_bf=1;subRL->_bf=0;parent->_bf=0;}elseif(bf==1){subR->_bf=0;subRL->_bf=0;parent->_bf=-1;}else{exit(-1);}}

2.3.4 Insert完整代码

加上省略掉的rotate部分：

boolInsert(constpair<K,V>&kv){if(_root==nullptr){_root=newNode(kv);returntrue;}Node*parent=nullptr;Node*cur=_root;while(cur){if(cur->_kv.first<kv.first){parent=cur;cur=cur->_right;}elseif(cur->_kv.first>kv.first){parent=cur;cur=cur->_left;}else{returnfalse;}}cur=newNode(kv);if(parent->_kv.first>kv.first){parent->_left=cur;}else{parent->_right=cur;}cur->_parent=parent;// Update balance factorwhile(parent){if(parent->_kv.first>kv.first){parent->_bf--;}else{parent->_bf++;}if(parent->_bf==0){break;}elseif(abs(parent->_bf)==1){// continuecur=parent;parent=parent->_parent;}elseif(abs(parent->_bf)==2){// rotateif(parent->_bf==-2){if(cur->_bf==-1){RotateL(parent);}elseif(cur->_bf==1){RotateLR(parent);}}elseif(parent->_bf==2){if(cur->_bf==1){RotateR(parent);}elseif(cur->_bf==-1){RotateRL(parent);}}break;}else{// errorexit(-1);}}returntrue;}

2.4 AVL树的平衡检测

框架：

boolIsBalanceTree(Node*root){// ...}

1. 处理root为空的情况

if(root==nullptr){returntrue;}

2. 记录左右子树高度

intleftHeight=_Height(root->_left);intrightHeight=_Height(root->_right);

3. 计算高度差，即为 root 的实际bf

intdifference=rightHeight-leftHeight;

4. 检查 difference 是否合理

if(abs(difference)==2){cout<<root->_kv.first<<"abnormal height difference"<<endl;returnfalse;}

5. 检查已存储bf是否正确

if(difference!=root->_bf){cout<<root->_kv.first<<"abnormal balance factor"<<endl;returnfalse;}

• 不能直接检查bf，因为bf可能更新错。

6. 递归往root左右判断

returnIsBalanceTree(root->_left)&&IsBalanceTree(root->_right);

7. 再开放一个public接口供外部使用：

boolIsBalanceTree(){return_IsBalanceTree(_root);}

2.5 AVL树的查找

没啥好说的，跟二叉搜索树一样：

Node*Find(constK&key){Node*cur=_root;while(cur){if(cur->_kv.first<key){cur=cur->_right;}elseif(cur->_kv.first>key){cur=cur->_left;}else{returncur;}}returnnullptr;}

2.6 简单测试一下

AVLTree定义在定义域wyzy里了。

wyzy::AVLTree<int,int>t;inta[]={4,2,6,1,3,5,15,7,16,14};for(autoe:a){t.Insert({e,e});}t.Print();cout<<endl;cout<<t.IsBalanceTree()<<endl;

定义了一个Print函数用于输出：

classAVLTree{public：voidPrint(){_Print(_root);}private:void_Print(Node*root){if(root==nullptr){return;}_Print(root->_left);cout<<root->_kv.first<<" "<<root->_bf<<endl;_Print(root->_right);}}

这个递归老生常谈了，就不多说了。
运行：

这么一棵树：

AVLTree 的学习就到这里，下一篇我们再上一个新的树 红黑树 ，很快（bushi）会更出来~