C++AVL树

目录

一、AVL树的概念

二、AVL树插入新节点的规则

三、AVL树旋转调节的规则

1.右单旋：新节点插入较高左子树的左侧（左左）

2.左单旋：新节点插入较高右子树的右侧（右右）

3.双旋1（先左单旋再右单旋）：新节点插入较高左子树的右侧（左右）

（1）情况

（2）情况

（3）情况

4.双旋2（先右单旋再左单旋）：新节点插入较高右子树的左侧（右左）

四、AVL树插入函数的完整代码

五、验证二叉搜索树为AVL树（验证是否平衡）

六、AVL高度函数

七、AVL大小Size函数

八、AVL树中序遍历

九、AVL树查找

十、AVL树的性能

十一、AVL树完整代码

一、AVL树的概念

二叉搜索树的查找效率很高，但是如果数据有序或接近有序二叉搜索树将退化为单支树，超找数据相当于在顺序表中查找，效率直线下降。

为了解决这个问题，提出一种方法：向二叉树中插入新节点时，要保证每个节点的左右子树高度差不超过1，即可降低树的高度，减少平均搜索长度

AVL树的性质：

左右子树都是AVL树

每个节点左右子树高度差（平衡因子）绝对值不超过1

AVL树节点的定义

template<class K,class V>
struct AVLTreeNode {pair<K, V> _kv;//键值对AVLTreeNode<K, V>* _left;AVLTreeNode<K, V>* _right;AVLTreeNode<K, V>* _parent;int _bf = 0;//平衡因子AVLTreeNode(const pair<K,V>& kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0){}
};

二、AVL树插入新节点的规则

1.按照二叉搜索树规则插入

2.更新新节点的所有祖先节点的平衡因子

a.新节点为父亲的左孩子，父亲节点平衡因子--（对于祖先节点，变动的是其左子树）

b.新节点为父亲的右孩子，父亲节点平衡因子++（对于祖先节点，变动的是其右子树）

c.父亲节点平衡因子==0，说明父亲节点所在子树高度不变，不再继续更新祖先，插入结束

d.父亲节点平衡因子==1 or ==-1，说明父亲节点所在子树高度改变了，继续更新祖先节点

e.父亲节点平衡因子==2 or ==-2，说明父亲节点所在子树不满足AVL树，需要进行旋转调节（旋转调节成功后，插入即结束，因为调节后的新根节点（或子树的根节点）平衡因子为0）

插入代码（部分代码）

//插入
bool insert(const pair<K, V>& kv)
{//1.按照二叉搜索树规则插入Node* cur = _root;Node* parent = nullptr;if (cur == nullptr)//树为空{_root = new Node(kv);return true;}else//树不为空{while (cur){if (kv.first < cur->_kv.first){parent = cur;cur = cur->_left;}else if (kv.first > cur->_kv.first){parent = cur;cur = cur->_right;}else{return false;//二叉搜索树不允许数据冗余}}cur = new Node(kv);if (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;}//2.更新新节点的所有祖先节点的平衡因子while (parent){if (cur == parent->_left)parent->_bf--;elseparent->_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)//子树不平衡，需要旋转调节{//旋转调节//......}else{assert(false);//不可能出现这种情况，但不排除意外发生，因此直接断言}}return true;
}

三、AVL树旋转调节的规则

出现旋转情况的树有很多种情况，所以此处不画出树的具体形状，而是用抽象图表示

抽象图中每个节点都有一个平衡因子，默认为右子树高度减去左子树高度

1.右单旋：新节点插入较高左子树的左侧（左左）

旋转方法：将30节点的右孩子给成60节点的左孩子，再将60节点给成30节点的右孩子

两种需要情况：

1.a、b为空树，那么旋转后60节点的左孩子为空

2.60节点可能为根，也可能为子树：

a.如果是根，旋转后要更新根节点

b.如果是子树，要考虑是某个节点的左子树或者右子树

//右单旋
void RotateR(Node* parent)
{Node* subL = parent->_left;//需要旋转节点的左孩子Node* subLR = subL->_right;//需要旋转节点的左孩子的右孩子//Node* ppNode = parent->_parent;//旋转节点的父亲节点parent->_left = subLR;//将旋转节点左孩子的右孩子给成旋转节点的左孩子if(subLR)subLR->_parent = parent;//父亲节点也需要修改（但前提是旋转节点左孩子的右孩子存在，所以有个判断条件）subL->_right = parent;//将旋转节点给成旋转节点左孩子的右孩子Node* ppNode = parent->_parent;//旋转节点的父亲节点parent->_parent = subL;//父亲节点也需要修改if (parent == _root)//parent是根节点{_root = subL;_root->_parent = nullptr;}else//parent是子树{if (ppNode->_left == parent)//旋转节点是左节点，则将subL作为左节点ppNode->_left = subL;else//旋转节点是右节点，则将subL作为右节点ppNode->_right = subL;subL->_parent = ppNode;}parent->_bf = subL->_bf = 0;//最后旋转后的节点平衡因子为0
}

2.左单旋：新节点插入较高右子树的右侧（右右）

旋转方法：将60节点的左孩子给成30节点的右孩子，再将30节点给成60节点的左孩子

//左单旋
void RotateL(Node* parent)
{Node* subR = parent->_right;//旋转节点的右孩子Node* subRL = subR->_left;//旋转节点右孩子的左孩子//Node* ppNode = parent->_parent;//旋转节点的父亲节点parent->_right = subRL;//将旋转节点右孩子的左孩子给成旋转节点的右孩子if (subRL)subRL->_parent = parent;//父亲节点也需要修改（但前提是旋转节点右孩子的左孩子存在，所以有个判断条件）subR->_left = parent;//将旋转节点给成旋转节点的右孩子的左孩子Node* ppNode = parent->_parent;//旋转节点的父亲节点parent->_parent = subR;//父亲节点也需要修改if (parent == _root)//旋转节点是根节点{_root = subR;_root->_parent = nullptr;}else//旋转节点是子树{if (ppNode->_left == parent)//旋转节点是左节点，则将subR作为左节点ppNode->_left = subR;else//旋转节点是右节点，则将subR作为右节点ppNode->_right = subR;subR->_parent = ppNode;}subR->_bf = parent->_bf = 0;//最后旋转后的节点平衡因子为0
}

3.双旋1（先左单旋再右单旋）：新节点插入较高左子树的右侧（左右）

旋转方法：先对30节点进行左单旋，再对90节点进行右单旋

单旋的时候默认旋转节点以及它们的左孩子/右孩子平衡因子为0，但是双旋后节点的平衡因子会根据插入新节点的情况而变化，因此还需要重新调节各节点的平衡因子

此处又分为三种情况：

（1）情况

（1）新节点插入在60节点的左侧（较高左子树的右子树的左侧）（60节点平衡因子为-1）

按照单旋的逻辑，理论上90、60、30节点旋转后的平衡因子都为0，但事实并不是这样，观察抽象图，如果新节点插入在60节点的左侧，最终90节点的平衡因子为1

（2）情况

（2）新节点插入在60节点的右侧（较高左子树的右子树的右侧）（60节点平衡因子为1）

观察抽象图，如果新节点插入在60节点的右侧，最终30节点的平衡因子为-1

（3）情况

（3）新节点就是60节点（高度h为0）（60节点平衡因子为0） 

观察抽象图，如果60就是新增节点，最终90、60、30节点平衡因子都是0

//双旋1
void RotateLR(Node* parent)
{//旋转前先保存一下各个节点Node* subL = parent->_left;Node* subLR = subL->_right;//还要保存一下subLR的平衡因子用于判断新节点情况int bf = subLR->_bf;RotateL(parent->_left);//先左单旋RotateR(parent);//再右单旋//判断新节点情况if (bf == 0){//单旋中默认都为0，不需要再调节}else if (bf == -1){//新增节点在subLR左侧parent->_bf = 1;//（其余两个节点已在单旋中调节为0）}else if (bf == 1){//新增节点在subLR右侧subL->_bf = -1;//（其余两个节点已在单旋中调节为0）}elseassert(false);
}

4.双旋2（先右单旋再左单旋）：新节点插入较高右子树的左侧（右左）

旋转方法：先对90进行右单旋，再对60进行左单旋

双旋2和双旋1一样，都需要在旋转后根据新节点插入情况对各个节点重新进行平衡因子调节（此处不再提供分析，直接上代码）

//双旋2
void RotateRL(Node* parent)
{//旋转前先保存一下各个节点Node* subR = parent->_right;Node* subRL = subR->_left;//还要保存一下subLR的平衡因子用于判断新节点情况int bf = subRL->_bf;RotateR(parent->_right);//先右单旋RotateL(parent);//再左单旋if (bf == 0){//单旋中默认都为0，不需要再调节}else if (bf == -1){//新增节点在subRL左侧subR->_bf = 1;//（其余两个节点已在单旋中调节为0）}else if (bf == 1){//新增节点在subRL右侧parent->_bf = -1;//（其余两个节点已在单旋中调节为0）}else assert(false);
}

四、AVL树插入函数的完整代码

//插入
bool insert(const pair<K, V>& kv)
{//1.按照二叉搜索树规则插入Node* cur = _root;Node* parent = nullptr;if (cur == nullptr)//树为空{_root = new Node(kv);return true;}else//树不为空{while (cur){if (kv.first < cur->_kv.first){parent = cur;cur = cur->_left;}else if (kv.first > cur->_kv.first){parent = cur;cur = cur->_right;}else{return false;//二叉搜索树不允许数据冗余}}cur = new Node(kv);if (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;}//2.更新新节点的所有祖先节点的平衡因子while (parent){if (cur == parent->_left)parent->_bf--;elseparent->_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 && cur->_bf == -1)//右单旋{RotateR(parent);}else if (parent->_bf == 2 && cur->_bf == 1)//左单旋{RotateL(parent);}else if (parent->_bf == -2 && cur->_bf == 1)//双旋1（左右）{RotateLR(parent);}else if (parent->_bf == 2 && cur->_bf == -1)//双旋2（右左）{RotateRL(parent);}elseassert(false);break;//旋转调节后插入结束}else{assert(false);//不可能出现这种情况，但不排除意外发生，因此直接断言}}return true;
}

五、验证二叉搜索树为AVL树（验证是否平衡）

验证二叉搜索树为AVL树，要求：

• 每个节点子树高度差的绝对值不超过1
• 每个节点的平衡因子计算正确

public://判断树是否平衡bool IsBalanceTree(){return _IsBalanceTree(_root);}private://判断树是否平衡bool _IsBalanceTree(Node* root){//1.检验高度差的绝对值是否都小于2if (root == nullptr)return true;int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);if (abs(rightHeight - leftHeight) >= 2)return false;//2.检验平衡因子是否正确if (root->_bf != rightHeight - leftHeight)return false;//递归继续检查子树是否平衡return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);}

六、AVL高度函数

public://求树高度int Height(){return _Height(_root);}
private://求树的高度int _Height(Node* root){if (root == nullptr)return 0;elsereturn max(_Height(root->_left), _Height(root->_right)) + 1;}

七、AVL大小Size函数

public://求AVL树的数据个数int Size(){return _Size(_root);}
private://求AVL树数据个数int _Size(Node* root){if (root == nullptr)return 0;elsereturn _Size(root->_left) + _Size(root->_right) + 1;}

八、AVL树中序遍历

public://中序遍历void InOrder(){_InOrder(_root);cout << endl;}private://中序遍历void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << endl;_InOrder(root->_right);}

九、AVL树查找

//查找
Node* Find(const K& key)
{Node* cur = _root;while (cur){if (cur->_kv.first < key){cur = cur->_right;}else if (cur->_kv.first > key){cur = cur->_left;}else{return cur;}}return nullptr;
}

十、AVL树的性能

AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这样可以保证查询时高效的时间复杂度，即log_2 (N)。但是如果要对AVL树做一些结构修改的操作，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。因此：如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的(即不会改变)，可以考虑AVL树，但一个结构经常修改，就不太适合。

十一、AVL树完整代码

namespace AVL {template<class K,class V>struct AVLTreeNode {pair<K, V> _kv;//键值对AVLTreeNode<K, V>* _left;AVLTreeNode<K, V>* _right;AVLTreeNode<K, V>* _parent;int _bf = 0;//平衡因子AVLTreeNode(const pair<K,V>& kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0){}};template<class K,class V>class AVLTree {typedef AVLTreeNode<K, V> Node;//树节点重命名public://构造函数AVLTree():_root(nullptr){}//插入bool Insert(const pair<K, V>& kv){//1.按照二叉搜索树规则插入Node* cur = _root;Node* parent = nullptr;if (cur == nullptr)//树为空{_root = new Node(kv);return true;}else//树不为空{while (cur){if (kv.first < cur->_kv.first){parent = cur;cur = cur->_left;}else if (kv.first > cur->_kv.first){parent = cur;cur = cur->_right;}else{return false;//二叉搜索树不允许数据冗余}}cur = new Node(kv);if (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;}//2.更新新节点的所有祖先节点的平衡因子while (parent){if (cur == parent->_left)parent->_bf--;elseparent->_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 && cur->_bf == -1)//右单旋{RotateR(parent);}else if (parent->_bf == 2 && cur->_bf == 1)//左单旋{RotateL(parent);}else if (parent->_bf == -2 && cur->_bf == 1)//双旋1（左右）{RotateLR(parent);}else if (parent->_bf == 2 && cur->_bf == -1)//双旋2（右左）{RotateRL(parent);}elseassert(false);break;//旋转调节后插入结束}else{assert(false);//不可能出现这种情况，但不排除意外发生，因此直接断言}}return true;}//右单旋void RotateR(Node* parent){Node* subL = parent->_left;//需要旋转节点的左孩子Node* subLR = subL->_right;//需要旋转节点的左孩子的右孩子//Node* ppNode = parent->_parent;//旋转节点的父亲节点parent->_left = subLR;//将旋转节点左孩子的右孩子给成旋转节点的左孩子if(subLR)subLR->_parent = parent;//父亲节点也需要修改（但前提是旋转节点左孩子的右孩子存在，所以有个判断条件）subL->_right = parent;//将旋转节点给成旋转节点左孩子的右孩子Node* ppNode = parent->_parent;//旋转节点的父亲节点parent->_parent = subL;//父亲节点也需要修改if (parent == _root)//parent是根节点{_root = subL;_root->_parent = nullptr;}else//parent是子树{if (ppNode->_left == parent)//旋转节点是左节点，则将subL作为左节点ppNode->_left = subL;else//旋转节点是右节点，则将subL作为右节点ppNode->_right = subL;subL->_parent = ppNode;}parent->_bf = subL->_bf = 0;//最后旋转后的节点平衡因子为0}//左单旋void RotateL(Node* parent){Node* subR = parent->_right;//旋转节点的右孩子Node* subRL = subR->_left;//旋转节点右孩子的左孩子//Node* ppNode = parent->_parent;//旋转节点的父亲节点parent->_right = subRL;//将旋转节点右孩子的左孩子给成旋转节点的右孩子if (subRL)subRL->_parent = parent;//父亲节点也需要修改（但前提是旋转节点右孩子的左孩子存在，所以有个判断条件）subR->_left = parent;//将旋转节点给成旋转节点的右孩子的左孩子Node* ppNode = parent->_parent;//旋转节点的父亲节点parent->_parent = subR;//父亲节点也需要修改if (parent == _root)//旋转节点是根节点{_root = subR;_root->_parent = nullptr;}else//旋转节点是子树{if (ppNode->_left == parent)//旋转节点是左节点，则将subR作为左节点ppNode->_left = subR;else//旋转节点是右节点，则将subR作为右节点ppNode->_right = subR;subR->_parent = ppNode;}subR->_bf = parent->_bf = 0;//最后旋转后的节点平衡因子为0}//双旋1void RotateLR(Node* parent){//旋转前先保存一下各个节点Node* subL = parent->_left;Node* subLR = subL->_right;//还要保存一下subLR的平衡因子用于判断新节点情况int bf = subLR->_bf;RotateL(parent->_left);//先左单旋RotateR(parent);//再右单旋//判断新节点情况if (bf == 0){//单旋中默认都为0，不需要再调节}else if (bf == -1){//新增节点在subLR左侧parent->_bf = 1;//（其余两个节点已在单旋中调节为0）}else if (bf == 1){//新增节点在subLR右侧subL->_bf = -1;//（其余两个节点已在单旋中调节为0）}elseassert(false);}//双旋2void RotateRL(Node* parent){//旋转前先保存一下各个节点Node* subR = parent->_right;Node* subRL = subR->_left;//还要保存一下subLR的平衡因子用于判断新节点情况int bf = subRL->_bf;RotateR(parent->_right);//先右单旋RotateL(parent);//再左单旋if (bf == 0){//单旋中默认都为0，不需要再调节}else if (bf == -1){//新增节点在subRL左侧subR->_bf = 1;//（其余两个节点已在单旋中调节为0）}else if (bf == 1){//新增节点在subRL右侧parent->_bf = -1;//（其余两个节点已在单旋中调节为0）}else assert(false);}//查找Node* Find(const K& key){Node* cur = _root;while (cur){if (cur->_kv.first < key){cur = cur->_right;}else if (cur->_kv.first > key){cur = cur->_left;}else{return cur;}}return nullptr;}//判断树是否平衡bool IsBalanceTree(){return _IsBalanceTree(_root);}//求AVL树高度int Height(){return _Height(_root);}//求AVL树的数据个数int Size(){return _Size(_root);}//中序遍历void InOrder(){_InOrder(_root);cout << endl;}private://判断树是否平衡bool _IsBalanceTree(Node* root){//1.检验高度差的绝对值是否都小于2if (root == nullptr)return true;int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);if (abs(rightHeight - leftHeight) >= 2){cout << root->_kv.first << endl;return false;}//2.检验平衡因子是否正确if (root->_bf != (rightHeight - leftHeight)){cout << root->_kv.first << endl;return false;}//递归继续检查子树是否平衡return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);}//求AVL树的高度int _Height(Node* root){if (root == nullptr)return 0;return max(_Height(root->_left), _Height(root->_right)) + 1;}//求AVL树数据个数int _Size(Node* root){if (root == nullptr)return 0;elsereturn _Size(root->_left) + _Size(root->_right) + 1;}//中序遍历void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << endl;_InOrder(root->_right);}private:Node* _root;//根节点};
}