【C++】AVLTree——高度平衡二叉搜索树

个人简介📝

🏆2022年度博客之星Top18;🏆2022社区之星Top2;的🥇C/C++领域优质创作者;

🥇阿里云专家博主;🥇华为云云享专家;🥇腾讯云年度进取作者;🥇掘金成长之星;

一、AVL树的概念

二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。

因此，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。
一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：

它的左右子树都是AVL树
左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)

平衡因子= 右子树高度-左子树高度

如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在O(log2N) ，搜索时间复杂度O(log2N)

---

二、AVL树节点的定义

节点结构：三叉链结构（左、右、父），以及平衡因子bf+构造函数（左右为空，平衡因子初始化为0）

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;//balance factorAVLTreeNode(const pair<K,V>&kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0){}
};

---

三、AVL树的插入

AVL树在二叉搜索树的基础上引入了平衡因子，因此AVL树也可以看成是二叉搜索树。步骤过程：

找到插入的位置：根据二叉搜索树的做法

进行插入：判断插入的位置是parent的左还是右

更新平衡因子：如果不平衡的话，就要进行旋转

找到插入位置（比较节点大小即可）：

• 插入的节点key值 > 当前位置的key值，往右子树走
• 插入的节点key值 < 当前位置的key值，往左子树走
• 插入的节点key值等于当前位置的key值，不能插入，返回false

插入之后，与二叉搜索树不同的是：我们还需要去进行平衡因子的更新，调平衡：

如果新增加的在右，平衡因子加加

如果新增加的在左，平衡因子减减

更新一个结点之后我们需要去进行判断，子树的高度是否发生了变化：

1.如果parent的平衡因子是0：说明之前parent的平衡因子是1或-1，说明之前parent一边高、一边低；这次插入之后填入矮的那边，parent所在的子树高度不变，不需要继续往上更新

2.如果parent的平衡因子是1或者-1：说明之前parent的平衡因子是0，两边一样高，插入之后一边更高，parent所在的子树高度发生变化，继续往上更新

3.平衡因子是2或-2，说明之前parent的平衡因子是1或-1，现在插入严重不平衡，违反规则，需要进行旋转处理

最坏的情况下：需要一直更新到根root：

我们更新平衡因子时第一个更新的就是parent,如果parent->_bf1或parent->_bf-1需要继续往上进行平衡因子的更新，向上迭代，直到parent为空的情况：

else if (parent->_bf == 1 || parent->_bf == -1)
{cur = parent;parent = parent->_parent;
}

当parent->_bf = 2或parent->_bf==-2时，我们就需要进行旋转了：

🔴如果parent的平衡因子是2，cur的平衡因子是1时，说明右边的右边比较高，我们需要进行左单旋

🔴如果parent的平衡因子是-2，cur的平衡因子是-1时，说明左边的左边比较高，我们需要进行右单旋

🔴如果parent的平衡因子是-2，cur的平衡因子是1时，我们需要进行左右双旋

🔴如果parent的平衡因子是2，cur的平衡因子是-1时，我们需要进行右左双旋

bool Insert(const pair<K, V>& kv){if (_root == nullptr){_root = new Node(kv);return true;}Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(kv);if (parent->_kv.first < kv.first){parent->_right = cur;cur->_parent = parent;}else{parent->_left = cur;cur->_parent = parent;}//更新平衡因子while (parent){if (cur == parent->_left){parent->_bf--;}else{parent->_bf++;}if (parent->_bf == 0){break;}else if (parent->_bf == 1 || parent->_bf == -1){cur = parent;parent = parent->_parent;}else if(parent->_bf==2||parent->_bf==-2){//左旋转if (parent->_bf == 2 && cur->_bf == 1){RotateL(parent);}//右旋else if (parent->_bf == -2 && cur->_bf == -1){RotateR(parent);}//左右双旋else if (parent-> _bf == -2&&cur->_bf==1){RotateLR(parent);}//右左双旋else if (parent->_bf ==2&&cur->_bf ==-1){RotateRL(parent);}else{assert(false);}break;}else{assert(false);}}return true;}

---

四、AVL树的旋转

在一棵原本是平衡的AVL树中插入一个新节点，可能造成不平衡，此时必须调整树的结构，使之平衡化。根据节点插入位置的不同，AVL树的旋转分为四种。

旋转规则：

1.让这颗子树左右高度差不超过1

2.旋转过程中继续保持它是搜索树

3.更新调整孩子节点的平衡因子

4.让这颗子树的高度根插入前保持一致

1.左单旋

新节点插入较高右子树的右侧—右右：左单旋

抽象图：

a/b/c是高度为h的AVL子树，代表多数情况：h>=0,其中h可以等于0、1、2…，不过都可以抽象成h，处理情况都一样：此时parent等于2，subR等于1。

具体左旋的步骤：

subRL成为parent的右子树：注意subL和parent的关系，调整parent的右以及subRL的父（subRL可能为空）

parent成为subR的左子树：调整parent的父与subR的左

subR成为相对的根节点：调整subR与ppNode：注意parent是不是整棵树的root，如果是，则让subR为_root,同时让_root->_parent置为空

更新平衡因子

左旋调整：subR的左子树值（subRL）本身就比parent的值要大，所以可以作为parent的右子树;而parent及其左子树当中结点的值本身就比subR的值小，所以可以作为subR的左子树。

**更新平衡因子bf:**subR与parent的bf都更新为0

代码实现左旋转：

//左单旋void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;Node* ppNode = parent->_parent;subR->_left = parent;parent->_parent = subR;if (ppNode == nullptr){_root = subR;_root->_parent = nullptr;}else{if (ppNode->_left == parent){ppNode->_left = subR;}else{ppNode->_right = subR;}subR->_parent = ppNode;}parent->_bf = subR->_bf = 0;}

---

2.右单旋

新节点插入较高左子树的左侧—左左：右单旋

有了前面左旋的基础，我们在来看右旋就没有那么费劲了：

a/b/c是高度为h的AVL树，右旋旋转动作：b变成60的左边，60变成30的右边，30变成子树的根。
30比60小，b值是处于30和60之间，此时作为60的左边是没有问题的。

有了这个图，在结合前面左单旋的基础，我们就能很快实现我们的右单旋代码：

//右单旋
void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;Node* ppNode = parent->_parent;parent->_parent = subL;subL->_right = parent;//if(_root==parent)if (ppNode == nullptr){_root = subL;_root->_parent = nullptr;}else{if (ppNode->_left == parent){ppNode->_left = subL;}else{ppNode->_right = subL;}subL->_parent = ppNode;}subL->_bf = parent->_bf = 0;}

---

3.左右双旋

新节点插入较高左子树的右侧—左右：先左单旋再右单旋

a/d是高度为h的AVL树，b/c是高度为h-1的AVL树。

以30为轴点进行左单旋：b变成30的右边，30变成60的左边，60变成子树根

以90为轴点进行右单旋：c变成90的左边，90变成60的右边，60变成子树的根

左右双旋：以subL为轴点左旋，以parent为轴点进行右旋，在进行平衡因子的更新(最大的问题)

我们从总体的角度来看，左右双旋的结果就是：就是把subLR的左子树和右子树，分别作为subL和parent的右子树和左子树，同时subL和parent分别作为subLR的左右子树，最后让subLR作为整个子树的根

subLR的左子树作为subL的右子树：因为subLR的左子树结点比subL的大

subLR的右子树作为parent的左子树：因为subLR的右子树结点比parent的小

平衡因子的更新：重新判断（识别插入节点是在b还是在c）根据subLR平衡因子的初始情况进行分类：

• 如果subLR初始平衡因子是-1时，左右双旋后parent、subL、subLR的平衡因子分别更新为1、0、0（插入在b）

• 如果subLR的初始平衡因子是1时，左右双旋后parent、subL、subLR的平衡因子分别更新为0、-1、0（插入在c）

• 如果subLR初始平衡因子是0时，左右双旋后parent、subL、subLR的平衡因子分别更新为0、0、0（subLR自己新增）

代码实现：

//左右双旋void RotateLR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR ->_bf;RotateL(parent->_left);RotateR(parent);//更新平衡因子if (bf == -1)//b插入,subLR左子树新增{subL->_bf = 0;parent->_bf = 1;subLR->_bf = 0;}else if (bf == 1)//c插入，subLR右子树新增{parent->_bf = 0;subL->_bf = -1;subLR->_bf = 0;}else if (bf == 0)//subLR自己新增加{parent->_bf = 0;subL->_bf = 0;subLR->_bf = 0;}else{assert(false);}}

---

4.右左双旋

新节点插入较高右子树的左侧—右左：先右单旋再左单旋

插入

subR为轴点进行右单旋：

parent为轴进行左单旋：

既右左双旋：

右左双旋后，根据subRL 初始平衡因子的不同分为三种情况分别对应subRL = 0、1、-1情况，与左右双旋情况类似。

void RotateRL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(subR);RotateL(parent);if (bf == 1){subR->_bf = 0;subRL->_bf = 0;parent->_bf = -1;}else if (bf == -1){subR->_bf = 1;subRL->_bf = 0;parent->_bf = 0;}else if (bf == 0){subR->_bf = 0;subRL->_bf = 0;parent->_bf = 0;}else{assert(false);}}

五、进行验证

AVL树是在二叉搜索树的基础上加入了平衡性的限制，因此要验证AVL树，可以分两步：

• 验证其为二叉搜索树
  如果中序遍历可得到一个有序的序列，就说明为二叉搜索树

	void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << endl;_InOrder(root->_right);}

• 验证其为平衡树
  每个节点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子)节点的平衡因子是否计算正确

  如果是空树，是AVL树；高度差不大于2，并且递归左右子树的高度差都不大于2，也是AVL树；判断平衡因子和该点的高度差是否相等

//求高度
int Height(Node* root){if (root == nullptr)return 0;int lh = Height(root->_left);int rh = Height(root->_right);return lh > rh ? lh + 1 : rh + 1;}
//判断平衡
bool IsBalance(Node* root){if (root == nullptr){return true;}int leftHeight = Height(root->_left);int rightHeight = Height(root->_right);if (rightHeight - leftHeight != root->_bf){cout << root->_kv.first << "平衡因子异常" << endl;return false;}return abs(rightHeight - leftHeight) < 2&& IsBalance(root->_left)&& IsBalance(root->_right);}

---

六、AVLTree的性能

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

---

送上源码：

#pragma once
#include <iostream>
#include <assert.h>
#include <time.h>
using namespace std;
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;//balance factorAVLTreeNode(const pair<K,V>&kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0){}
};template <class K,class V>
struct AVLTree
{typedef AVLTreeNode<K, V> Node;
public:bool Insert(const pair<K, V>& kv){if (_root == nullptr){_root = new Node(kv);return true;}Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(kv);if (parent->_kv.first < kv.first){parent->_right = cur;cur->_parent = parent;}else{parent->_left = cur;cur->_parent = parent;}//更新平衡因子while (parent){if (cur == parent->_left){parent->_bf--;}else{parent->_bf++;}if (parent->_bf == 0){break;}else if (parent->_bf == 1 || parent->_bf == -1){cur = parent;parent = parent->_parent;}else if(parent->_bf==2||parent->_bf==-2){//左旋转if (parent->_bf == 2 && cur->_bf == 1){RotateL(parent);}//右旋else if (parent->_bf == -2 && cur->_bf == -1){RotateR(parent);}//左右双旋else if (parent-> _bf == -2&&cur->_bf==1){RotateLR(parent);}//右左双旋else if (parent->_bf ==2&&cur->_bf ==-1){RotateRL(parent);}else{assert(false);}break;}else{assert(false);}}return true;}//左单旋void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;Node* ppNode = parent->_parent;subR->_left = parent;parent->_parent = subR;if (ppNode == nullptr){_root = subR;_root->_parent = nullptr;}else{if (ppNode->_left == parent){ppNode->_left = subR;}else{ppNode->_right = subR;}subR->_parent = ppNode;}parent->_bf = subR->_bf = 0;}void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;Node* ppNode = parent->_parent;parent->_parent = subL;subL->_right = parent;//if(_root==parent)if (ppNode == nullptr){_root = subL;_root->_parent = nullptr;}else{if (ppNode->_left == parent){ppNode->_left = subL;}else{ppNode->_right = subL;}subL->_parent = ppNode;}subL->_bf = parent->_bf = 0;}//左右双旋void RotateLR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR ->_bf;RotateL(parent->_left);RotateR(parent);//更新平衡因子if (bf == -1)//b插入,subLR左子树新增{subL->_bf = 0;parent->_bf = 1;subLR->_bf = 0;}else if (bf == 1)//c插入，subLR右子树新增{parent->_bf = 0;subL->_bf = -1;subLR->_bf = 0;}else if (bf == 0)//subLR自己新增加{parent->_bf = 0;subL->_bf = 0;subLR->_bf = 0;}else{assert(false);}}//右左双旋void RotateRL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(subR);RotateL(parent);if (bf == 1){subR->_bf = 0;subRL->_bf = 0;parent->_bf = -1;}else if (bf == -1){subR->_bf = 1;subRL->_bf = 0;parent->_bf = 0;}else if (bf == 0){subR->_bf = 0;subRL->_bf = 0;parent->_bf = 0;}else{assert(false);}}void InOrder(){_InOrder(_root);}void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << endl;_InOrder(root->_right);}int Height(Node* root){if (root == nullptr)return 0;int lh = Height(root->_left);int rh = Height(root->_right);return lh > rh ? lh + 1 : rh + 1;}bool IsBalance(){return IsBalance(_root);}bool IsBalance(Node* root){if (root == nullptr){return true;}int leftHeight = Height(root->_left);int rightHeight = Height(root->_right);if (rightHeight - leftHeight != root->_bf){cout << root->_kv.first << "平衡因子异常" << endl;return false;}return abs(rightHeight - leftHeight) < 2&& IsBalance(root->_left)&& IsBalance(root->_right);}
private:Node* _root = nullptr;
};//测试
void TestAVLTree()
{//int a[] = { 8,3,1,10,6,4,7,14,13 };//int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };int a[] = { 4,2,6,1,3,5,15,7,16,14 };AVLTree<int, int> t;for (auto e : a){t.Insert(make_pair(e,e));}t.InOrder();cout << t.IsBalance() << endl;
}void TestAVLTree2()
{srand(time(0));const size_t N = 100000;AVLTree<int, int> t;for (size_t i = 0; i < N; i++){size_t x = rand();t.Insert(make_pair(x, x));}//t.InOrder();cout << t.IsBalance() << endl;
}

本篇结束…