AVL树
欢迎来到本期节目- - -
AVL树
前言：
代码以及图片较多；
建议在PC端查看本篇文章；
AVL树
- AVL树：
- AVL树的模拟实现
- AVL树的类定义
- AVL树的模拟插入：
- 平衡因子
- 左单旋/右左双旋
- 左旋
- 右左双旋
- 右单旋/左右双旋
- 右旋
- 左右双旋
- AVL树的模拟删除：
- AVL树的简单方法：
AVL树：
| 在AVL树中，任一节点对应的两颗子树的最大高度差为1，因此也称为高度平衡树; |
| AVL树具有二叉搜索树的搜索规则，可以在Ο(logN)时间复杂度完成查找\插入\删除操作; |
也就是说AVL树是一颗平衡二叉搜索树.
至于为啥叫AVL，其实那是以发明者的名字命名的。
特点：
- 本身是一颗二叉搜索树
- 带有平衡条件（任意节点的两颗子树高度差最大为1）
应用场景：
- 数据库系统
- 哈希表
- 文件系统
AVL树的模拟实现
由于AVL树要考虑平衡，所以可以通过特定算法或者平衡因子来控制平衡度,
这里我选择使用平衡因子.
AVL树的类定义
树节点：
template<class T>
struct AVLNode
{AVLNode(const T& val = T()):_val(val),_bf(0),_left(nullptr),_right(nullptr),_parent(nullptr)T _val;int _bf;AVLNode<T>* _left;AVLNode<T>* _right;AVLNode<T>* _parent; //虽然是二叉树，但是实际上是三叉链，_parent在插入/删除会频繁用到.
};
树：
#include<iostream>
#include<assert.h>
using namespace std;template<class T>
class AVLTree
{typedef AVLNode<T> Node;
public:AVLTree();AVLTree(const AVLTree& tree);AVLTree& operator=(AVLTree<T> tree);~AVLTree();//---------------------------------------------------------------------//重点介绍bool Insert(const T& val) //插入节点bool Erase(const T& val); //删除节点bool Find(const T& val); //查看节点是否存在 //---------------------------------------------------------------------size_t Height(){return _Height(_root);}bool IsAVLTree(){return _IsAVLTree(_root);}void InOrder(){_InOrder(_root);}size_t Size(){return _Size(_root);}
private:Node* _root;//-------------------------------------void RotateL(Node* parent);void RotateR(Node* parent);void RotateLR(Node* parent);void RotateRL(Node* parent);Node* LeftestNode(Node* root);Node* RightestNode(Node* root);//------------------------------------size_t _Height(Node* root);size_t _Size(Node* root);void _InOrder(Node* root);bool _IsAVLTree(Node* root);Node* CreateAVL(Node* root);void Destroy(Node* root);
}
为了方便介绍，以下的各个函数不会放在同一个文件中.
AVL树的模拟插入：
平衡因子
为了引入模型，这里我们可以思索一下，AVL树就是一颗平衡二叉搜索树；
该树有- -
| 搜索规则：中序遍历后的结果是呈递增或递减的.(默认递增). |
| 平衡规则：任何一个节点的左右子树的高度差不超过1. |
如果只是按搜索规则插入的话，相信对小伙伴们来说是简简单单.
但是又要考虑平衡度，这就犯愁了，不过不要紧，我们可以引入平衡因子，当然聪明的小伙伴还有其它的办法，但我这里就使用平衡因子了。
那么我们该如何使用平衡因子?
首先我们知道每次插入的节点它都是没有左右子树的，所以平衡因子是0，但是插入之后，肯定会影响该节点父亲的平衡因子，由于会插入到某颗树的底部，所以平衡因子应该是从下往上更新的.这里有三类场景：
- 插入后父亲的平衡因子是0 （1-1或-1+1）
- 插入后父亲的平衡因子是1/-1 （0+1或者0-1）
- 插入后父亲的平衡因子是2/-2 (1+1或-1-1)
这里的旋转可以使树的高度恢复到插入前的高度需要结合旋转图理解；
详情请看下方旋转部分：
平衡因子总结：
| 在插入的情况下，插入节点后，如果父亲节点的平衡因子为1或者-1就需要继续向上更新. |
| 在删除情况下，删除节点后，如果父亲节点的平衡因子为0就需要继续向上更新. |
（虽然没画删除情况下的平衡因子图解，但是相信聪明的小伙伴是可以推理出来的）
AVL树插入代码：
bool Insert(const T& val) //插入节点
{if (_root == nullptr){_root = new Node(val);return true;}
//------------------------------------------------------------------//按搜索规则找到空位.Node* cur = _root;Node* parent = nullptr;while (cur){if (val > cur->_val){parent = cur;cur = cur->_right;}else if (val < cur->_val){parent = cur;cur = cur->_left;}else //不插入重复键值return false;}//将父子关系链接起来cur = new Node(val);if (val > parent->_val){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent; //别忘了，这是个三叉链哦，有爸爸的.
//-------------------------------------------------------------------//插入之后，调整平衡因子， 通过平衡因子判断是否需要旋转while (parent){if (parent->_left == cur){parent->_bf--;}else{parent->_bf++;}if (parent->_bf == 0){break;}else if (parent->_bf == 1 || parent->_bf == -1){cur = parent;parent = cur->_parent;}else if(parent->_bf == 2 || parent->_bf == -2)//只需要一次单旋或者双旋--因为旋转之后的这颗树相对原来高度没有发生变化，所以不用继续更新.{if (parent->_bf == 2){if (cur->_bf == 1){RotateL(parent);}else if (cur->_bf == -1){RotateRL(parent);}else{assert(false);}}else{if (cur->_bf == -1){RotateR(parent);}else if (cur->_bf == 1){RotateLR(parent);}else{assert(false);}}break;}else{assert(false);}}return true;
}
左单旋/右左双旋
在这里我们需要引入- -
左旋/右左双旋基本模型
这个图就是左旋/右左双旋的通用模型，H>=0；
有小伙伴可能会问为啥Sub的左右子树都是H，不能是H-1，H或者H-1，H；
如果两边高度不等那么插入节点后可能会导致Sub成为Parent，也就是说会把该模型或者另外一个基本模型嵌套出来，简单说就是跳出了这个基本模型，也就不是通用模型了，所以只有两边都为H，才能代表这左旋以及右左双旋这一类的情况.
左旋
左旋是右边树太高了，需要往左压.
左旋的具体过程：
这里我把Parent的父亲节点叫做PParent;
首先我们知道在旋转过程中，会发生数据变化的节点无非就是PParent,Parent,Sub,SubL
这其中，Parent和Sub是肯定存在的，所以需要留意PParent以及SubL.
我个人认为将旋转代码分为两部分写比较清晰：
以下代码仅用于梳理逻辑，不支持运行
首先修改父亲指向
//Parent,Sub肯定存在
Sub->_parent = PParent;
Parent->parent = Sub;//SubL特殊处理
if(SubL)SubL->_parent = Parent;
然后修改孩子指向
//Parent,Sub肯定存在
Sub->_left = Parent;
Parent->_right = SubL;//PParent特殊处理
if(PParent == nullptr)_root = Sub;
else
{if (PParent->_left == Parent)PParent->_left = Sub;elsePParent->_right = Sub;
}//最后更新一下平衡因子
Sub->_bf = Parent->_bf = 0;
左旋代码：
private:void RotateL(Node* parent){Node* Pparent = parent->_parent;Node* sub = parent->_right;Node* subl = sub->_left;sub->_parent = Pparent;parent->_parent = sub;if (subl)subl->_parent = parent;sub->_left = parent;parent->_right = subl;if (Pparent == nullptr){_root = sub;}else{if (Pparent->_left == parent)Pparent->_left = sub;elsePparent->_right = sub;}sub->_bf = parent->_bf = 0;}
左旋总结：
| Sub平衡因子为1以及Parent平衡因子为2时； |
| 直接传Parent左旋； |
| 旋转后Sub，Parent的平衡因子都是0； |
| Sub为该树的根，相对于插入前该树高度未发生变化，停止更新. |
右左双旋
也就是在Sub左子树插入节点的场景：
分两种情况：
1.H==0
| 更新完平衡因子后，发现超出平衡度，需要旋转： |
2.H>=1
这里分为两种场景：
| 更新完平衡因子后，发现超出平衡度，需要旋转： |
| 更新完平衡因子后，发现超出平衡度，需要旋转： |
右左双旋代码：
private:void RotateRL(Node* parent){Node* sub = parent->_right;int bf = sub->_left->_bf;RotateR(sub);RotateL(parent);if (bf == 0){sub->_bf = 0;parent->_bf = 0;}else if (bf == 1){sub->_bf = 0;parent->_bf = -1;}else if (bf == -1){sub->_bf = 1;parent->_bf = 0;}}
右左双旋总结:
| Sub平衡因子为-1以及Parent平衡因子为2时； |
| 先传Sub进行右旋, 再传Parent进行左旋； |
| 如果SubL平衡因子为0；Sub以及Parent的平衡因子也为0； |
| 如果SubL平衡因为1；Sub平衡因子为0，Parent平衡因子为-1； |
| 如果SubL平衡因为-1；Sub平衡因子为1，Parent平衡因子为0； |
| 旋转后，该树的根为SubL,且SubL平衡因子为0，相比于插入前该树高度未发生变化，停止更新. |
右单旋/左右双旋
这里引入另外一个
右旋/左右双旋基本模型
这个图就是右旋/左右双旋的最小规模的基本模型，H>=0；
右旋
右旋是左边树高了，需要往右压.
右旋的具体过程：
这里我把Parent的父亲节点叫做PParent;
首先我们知道在旋转过程中，会发生数据变化的节点无非就是PParent,Parent,Sub,SubL
这其中，Parent和Sub是肯定存在的，所以需要留意PParent以及SubL.
我个人认为将旋转代码分为两部分写比较清晰：
以下代码仅用于梳理逻辑，不支持运行；
首先修改父亲指向
//Parent,Sub肯定存在
Sub->_parent = PParent;
Parent->parent = Sub;//SubR特殊处理
if(SubR)SubR->_parent = Parent;
然后修改孩子指向
//Parent,Sub肯定存在
Sub->_right = Parent;
Parent->_left = SubR;//PParent特殊处理
if(PParent == nullptr)_root = Sub;
else
{if (PParent->_left == Parent)PParent->_left = Sub;elsePParent->_right = Sub;
}//最后更新一下平衡因子
Sub->_bf = Parent->_bf = 0;
右旋代码：
private:void RotateR(Node* parent){Node* Pparent = parent->_parent;Node* sub = parent->_left;Node* subr = sub->_right;sub->_parent = Pparent;parent->_parent = sub;if (subr)subr->_parent = parent;sub->_right = parent;parent->_left = subr;if (Pparent == nullptr)_root = sub;else{if (Pparent->_left == parent)Pparent->_left = sub;elsePparent->_right = sub;}sub->_bf = parent->_bf = 0;}
右旋总结：
| Sub平衡因子为-1以及Parent平衡因子为-2； |
| 直接传Parent右旋； |
| 旋转后Sub,Parent的平衡因子都为0； |
| Sub为该树的根，相对于插入前该树高度为发生变化，停止更新； |
左右双旋
也就是在Sub右子树插入节点的场景：
分两种情况：
1.H==0
| 更新完平衡因子后，发现超出平衡度，需要旋转： |
2.H>=1
这里也分两种场景：
| 更新完平衡因子后，发现超出平衡度，需要旋转： |
| 更新完平衡因子后，发现超出平衡度，需要旋转： |
左右双旋代码：
private:void RotateLR(Node* parent){Node* sub = parent->_left;int bf = sub->_right->_bf;RotateL(sub);RotateR(parent);if (bf == 0){sub->_bf = 0;parent->_bf = 0;}else if (bf == 1){sub->_bf = -1;parent->_bf = 0;}else if (bf == -1){sub->_bf = 0;parent->_bf = 1;}else{assert(false);}}
左右双旋总结：
| Sub平衡因子为1以及Parent平衡因子为-2时； |
| 先传Sub进行左旋，再传Parent进行右旋； |
| 如果SubR平衡因子为0；Sub以及Parent的平衡因子也为0； |
| 如果SubR平衡因子为1；Sub的平衡因子为-1，Parent的平衡因子为0； |
| 如果SubR平衡因子为-1；Sub的平衡因子为0，Parent的平衡因子为1； |
| 旋转后，该树的根为SubR，且SubR平衡因子为0，相比插入前该树高度未发生变化，停止更新. |
AVL树的模拟删除：
删除逻辑：
删除一颗子树的节点；
如果是这个节点有两个孩子，则我们使用替换法，将删除位置移至最多只有一个孩子的位置.
那么删除节点就方便多了，删除之后往上更新平衡因子；
如果父亲节点的平衡因子为1或-1，未发生高度变化，停止更新；
如果父亲节点的平衡因子为0，说明删除前该节点的平衡因子是-1或者1，原本高度为H的树现在高度为H-1，高度发生变化，需要向上更新；
如果父亲节点的平衡因子为2或-2，则需要通过旋转调整，调整后高度为H的树现在高度为H-1，高度发生变化，需要先更新cur和parent，然后继续向上更新.
删除后旋转操作和插入是一样的，就是有两种情况的平衡因子需要手动处理.
简单说也就是Sub平衡因子为0时，平衡因子需要进行手动处理;
AVL树节点删除代码：
bool Erase(const T& val)
{Node* cur = _root;Node* parent = nullptr;while (cur){if (val > cur->_val){parent = cur;cur = cur->_right;}else if (val < cur->_val){parent = cur;cur = cur->_left;}else //找到了，删除加调整{//确保删除的是最多只有一个孩子的节点if (cur->_left && cur->_right) //替换法{Node* tmp = LeftestNode(cur->_right);cur->_val = tmp->_val;cur = tmp;parent = tmp->_parent;}//删除之前把 与删除节点相关的节点找到并链接在一起，并更新父亲的平衡因子（最好现在更新，因为如果删除的节点没有孩子，在后面更新平衡因子时会出错）Node* del = cur;if (cur->_left == nullptr){if (cur->_right)cur->_right->_parent = cur->_parent;if (parent){if (parent->_left == cur){parent->_left = cur->_right;parent->_bf++;}else{parent->_right = cur->_right;parent->_bf--;}}cur = cur->_right;}else{if (cur->_left)cur->_left->_parent = cur->_parent;if (parent){if (parent->_left == cur){parent->_left = cur->_left;parent->_bf++;}else{parent->_right = cur->_left;parent->_bf--;}}cur = cur->_left;}delete del;if (parent == nullptr)//删除根节点需要更新_root {_root = cur;return true;}//------------------------------------------------------------------------//查看是否需要继续向上更新，以及是否需要通过旋转调整.while (parent){if (parent->_bf == 1 || parent->_bf == -1)break;else if (parent->_bf == 0){cur = parent;parent = cur->_parent;}else if (parent->_bf == 2 || parent->_bf == -2)//可能多次单旋或者双旋--因为旋转后该树（产生旋转行为的那颗）的高度相对原来降低了1，发生了高度变化，需要向上更新.{//相对来说，降低一边高度就相当于增加一边高度，所以和插入的旋转操作相同//只需要注意两种特殊情况的平衡因子更新问题Node* sub = nullptr;if (parent->_left == cur)sub = parent->_right;elsesub = parent->_left;Node* tmp = sub;if (parent->_bf == 2){if(sub->_bf == 1||sub->_bf==0){int bf = sub->_bf;RotateL(parent);if (bf == 0)//手动更新情况1{sub->_bf = -1;parent->_bf = 1;}}else if (sub->_bf == -1){sub = sub->_left;RotateRL(parent);}else{assert(false);}}else{if (sub->_bf == -1 || sub->_bf ==0){int bf = sub->_bf;RotateR(parent);if (bf == 0)//手动更新情况2{sub->_bf = 1;parent->_bf = -1;}}else if (sub->_bf == 1){sub = sub->_right;RotateLR(parent);}else{assert(false);}}if (sub->_bf ==0 && sub->_parent){cur = sub;parent = sub->_parent;}else //注意旋转后如果sub(这个sub可能是sub或者subr或者subl,也就是旋转后的那颗树的根)为0,需要继续向上更新.{//注意如果旋转过程涉及到根，需要更新根位置if (sub->_parent == nullptr)_root = sub;break;}}else{assert(false);}if (parent == nullptr)break;else{if (parent->_left == cur)parent->_bf++;elseparent->_bf--;}}return true;}}return false;
}
删除节点总结：
更新平衡因子和插入时相反
| 只要Parent的平衡因子为0，就继续向上更新，为1或-1停止 ，或者为根节点停止； |
旋转操作和插入时类似
| 当平衡因子为2或者-2时，此时的cur肯定为0（因为只有为0才会向上更新）; |
| 相对来说，cur这颗树（Parent的一颗子树）删除了节点，相当与Parent的另一颗子树多了一个节点（效果）； |
| 所以直接调用对应的函数就行了，但是有两种特殊情况需要我们手动置一下平衡因子. |
| 最重要的一点就是因为旋转后很有可能该树根节点(可能是Sub或者SubL或者SubR)的平衡因子为0，所以要继续向上更新. |
AVL树的简单方法：
OK,重点已经介绍完毕，接下来把这些小函数送给我们的小伙伴：
为了让大家看的清楚，没有放在类里.
构造与析构：
public:AVLTree(){}AVLTree(const AVLTree& tree){_root = CreateAVL(tree._root);}AVLTree& operator=(AVLTree<T> tree){Node* tmp = _root;_root = tree._root;tree._root = tmp;return *this;}~AVLTree(){Destroy(_root);_root = nullptr;}
private:Node* CreateAVL(Node* root){if (root == nullptr)return nullptr;Node* newnode = new Node(root->_val);newnode->_bf = root->_bf;newnode->_left = CreateAVL(root->_left);newnode->_right = CreateAVL(root->_right);if (newnode->_left)newnode->_left->_parent = newnode;if (newnode->_right)newnode->_right->_parent = newnode;return newnode;}void Destroy(Node* root){if (root){Destroy(root->_left);Destroy(root->_right);delete root;}}
AVL树的特征方法：
public:size_t Height(){return _Height(_root);}size_t Size(){return _Size(_root);}void InOrder(){_InOrder(_root);}bool IsAVLTree(){return _IsAVLTree(_root);}bool Find(const T& val){Node* cur = _root;while(cur){if(val > cur->_val)cur = cur->_right;else if(val < cur->_val)cur = cur->_left;elsereturn true;}return false;}
private:size_t _Height(Node* root){if (root == nullptr)return 0;size_t left = _Height(root->_left)+1;size_t right = _Height(root->_right)+1;return left > right ? left : right;}size_t _Size(Node* root){if (root == nullptr)return 0;return _Size(root->_left) + _Size(root->_right) + 1;}void _InOrder(Node* root){if (root){_InOrder(root->_left);cout << root->_val<<" ";_InOrder(root->_right);}}bool _IsAVLTree(Node* root){if (root == nullptr)return true;if (root->_bf == 0|| root->_bf == 1|| root->_bf == -1){int differ = _Height(root->_right) - _Height(root->_left);if (differ != root->_bf)return false;}elsereturn false;return _IsAVLTree(root->_left) && _IsAVLTree(root->_right);}
希望本片文章对您有帮助，请点赞支持一下吧😘💕