【C++笔记】AVL树的深度剖析

🔥个人主页：大白的编程日记

🔥专栏：C++笔记

---

前言

哈喽，各位小伙伴大家好!上期我们讲了map和set的深度剖析。今天我们来讲一下AVL树的深度剖析。话不多说，我们进入正题！向大厂冲锋

一. AVL树的概念

• 定义
  AVL树是最先发明的自平衡⼆叉查找树，AVL是一颗空树，或者具备下列性质的⼆叉搜索树：它的左右子树都是AVL树，且左右子树的高度差的绝对值不超过1。AVL树是⼀颗高度平衡搜索⼆叉树，通过控制高度差去控制平衡。
  注意是所有的子树都满足高度差绝对值不超过1。
• 发明者
  AVL树得名于它的发明者G. M. Adelson-Velsky和E. M. Landis是两个前苏联的科学家，他们在1962年的论文《An algorithm for the organization of information》中发表了它。
• 平衡因子
  AVL树实现这里我们引入⼀个平衡因子(balance factor)的概念，每个结点都有⼀个平衡因子，任何结点的平衡因子等于右子树的高度减去左子树的高度，也就是说任何结点的平衡因子等于0/1/-1，AVL树并不是必须要平衡因子，但是有了平衡因子可以更方便我们去进行观察和控制树是否平衡，就像⼀个风向标⼀样。

• 高度差
  思考⼀下为什么AVL树是高度平衡搜索⼆叉树，要求⾼度差不超过1，而不是高度差是0呢？0不是更好的平衡吗？画画图分析我们发现，不是不想这样设计，而是有些情况是做不到高度差是0的。比如⼀棵树是2个结点，4个结点等情况下，高度差最好就是1，无法做到高度差是0
• 对比二叉搜索树
  AVL树整体结点数量和分布和完全⼆叉树类似，高度可以控制在 ，那么增删查改的效率也可以控制在logn ，相比⼆叉搜索树有了本质的提升。
  

二.AVL树的实现

2.1 AVL树的结构

这里我们为了旋转时需要用到父亲节点，所以我们就是一个三叉链的结构。
同时我们引入了平衡因子，方便我们控制高度差。

template<class k, class v>
struct AVLNode
{using node = AVLNode<k, v>;k _key;v _value;node* left;//左节点node* right;//右节点node* parent;//父亲节点int bf;//平衡因子AVLNode(const k& key, const v& value):_key(key), _value(value), left(nullptr), right(nullptr),parent(nullptr),bf(0){}
};
template<class k, class v>
class AVLTree
{using node = AVLNode<k, v>;private:node* _root = nullptr;
};

2.2 AVL树的插入

二叉搜索树还是按照二叉搜索树的规则插入。
但是插入后要更新平衡因子，如果高度差超过1那么就旋转。

• 插入
  插入一个值按二叉搜索树规则进行插入。
  插入的节点，左右为空所以平衡因子为0.

• 更新平衡因子
  新增结点以后，只会影响祖先结点的高度，也就是可能会影响部分祖先结点的平衡因子，所以更新从新增结点->根结点路径上的平衡因子，实际中最坏情况下要更新到根，有些情况更新到中间就可以停止了，具体情况我们下面再详细分析。

• 结束
  更新平衡因子过程中没有出现问题，则插入结束。

• 旋转
  更新平衡因子过程中出现不平衡，对不平衡子树旋转，旋转后本质调平衡的同时，本质降低了子树的高度，保持原来的高度，不会再影响上一层，所以插入结束。

2.3 平衡因子更新

更新原则：

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

• 只有子树高度变化才会影响当前结点平衡因子。

• 插入结点，会增加高度，所以新增结点在parent的右子树，parent的平衡因子++，新增结点在parent的左子树，parent平衡因子–。

• parent所在子树的高度是否变化决定了是否会继续往上更新
  如果当前子树高度没有变化，那当前子树往上的祖先节点的平衡因子也不会变化
  更新结束。

更新停止条件：

• 更新后parent的平衡因子等于0，更新中parent的平衡因子变化为-1->0 或者 1->0，说明更新前parent子树⼀边高⼀边低，新增的结点插入在低的那边，插入后parent所在的子树高度不变，不会影响parent的⽗亲结点的平衡因子，更新结束。

• 更新后parent的平衡因子等于1 或 -1，更新前更新中parent的平衡因子变化为0->1 或者 0->-1，说明更新前parent子树两边⼀样高，新增的插入结点后，parent所在的子树⼀边高⼀边低，parent所在的子树符合平衡要求，但是高度增加了1，会影响parent的⽗亲结点的平衡因子，所以要继续向上更新。

• 更新后parent的平衡因子等于2 或 -2，更新前更新中parent的平衡因子变化为1->2 或者 -1->-2，说明更新前parent子树⼀边高⼀边低，新增的插入结点在高的那边，parent所在的子树高的那边更高了，破坏了平衡，parent所在的子树不符合平衡要求，需要旋转处理，旋转的目标有两个：1、把parent子树旋转平衡。2、降低parent子树的高度，恢复到插入结点以前的高度。所以旋转后也不需要继续往上更新，插入结束。

• 不断更新，更新到根，跟的平衡因子是1或-1也停停止了。

三.旋转

3.1旋转的原则

旋转的原则如下：

1. 保持搜索树的规则
2. 让旋转的树从不满足变平衡，其次降低旋转树的高度
   旋转总共分为四种，左单旋/右单旋/左右双旋/右左双旋。
   说明：下面的图中，有些结点我们给的是具体值，如10和5等结点，这里是为了方便讲解，实际中是什么值都可以，只要大小关系符合搜索树的性质即可。

3.2右单旋

旋转时我们需要注意保持二叉搜索树的性质。
同时注意父亲节点和平衡因子的更新。
注意旋转后子树的高度不变，平衡因子向上更新停止。

	void RoRateR( node* parent)//右单旋{node* subL = parent->left;node* subLR = subL->right;node* pparnet = parent->parent;parent->left = subLR;if (subLR){subLR->parent = parent;//修改父节点}subL->right = parent;parent->parent = subL;if (pparnet == nullptr)//parent就是根节点{_root = subL;subL->parent = nullptr;}else{if (pparnet->left == parent)//确定parent节点是左还是右{pparnet->left = subL;}else {pparnet->right = subL;}subL->parent = pparnet;//修改父节点}subL->bf = parent->bf = 0;//更新平衡因子}

3.3左单旋

左单旋和右单旋类似。

void RoRateL( node* parent)//左单旋
{node* subR = parent->right;node* subRL = subR->left;node* pparnet = parent->parent;parent->right = subRL;if (subRL)//防止subRL为空{subRL->parent = parent;//修改父节点}subR->left = parent;parent->parent = subR;if (pparnet==nullptr)//parent就是根节点{_root = subR;subR->parent = nullptr;}else{if (pparnet->left == parent)//确定parent节点是左还是右{pparnet->left = subR;}else {pparnet->right = subR;}subR->parent = pparnet;//修改父节点}subR->bf = parent->bf = 0;//更新平衡因子
}

3.4左右双旋

左右双旋的就是先左单旋再右单旋。
同时注意平衡因子的更新即可。

更新条件：parent->bf == -2 && cur->bf == 1

void RoRateLR( node* parent)//左右双旋
{node* subL = parent->left;node* subLR = subL->right;int bf = subLR->bf;//先记录插入后的平衡因子RoRateL(subL);RoRateR(parent);if (bf == 0)//分情况讨论{parent->bf = 0;subL->bf = 0;subLR->bf = 0;}else if (bf == 1){parent->bf = 0;subL->bf = -1;subLR->bf = 0;}else if (bf == -1){parent->bf = 1;subL->bf = 0;subLR->bf = 0;}else{assert(false);}
}

3.5右左双旋

右左双旋情况和左右双旋类似，这里就不过多赘述了。

更新条件：parent->bf == 2 && cur->bf == -1

3.6AVL树的插入

结合前面的知识我们就可以写出二叉搜索树的插入了。

void RoRateR( node* parent)//右单旋
{node* subL = parent->left;node* subLR = subL->right;node* pparnet = parent->parent;parent->left = subLR;if (subLR){subLR->parent = parent;//修改父节点}subL->right = parent;parent->parent = subL;if (pparnet == nullptr)//parent就是根节点{_root = subL;subL->parent = nullptr;}else{if (pparnet->left == parent)//确定parent节点是左还是右{pparnet->left = subL;}else {pparnet->right = subL;}subL->parent = pparnet;//修改父节点}subL->bf = parent->bf = 0;//更新平衡因子
}
void RoRateL( node* parent)//左单旋
{node* subR = parent->right;node* subRL = subR->left;node* pparnet = parent->parent;parent->right = subRL;if (subRL)//防止subRL为空{subRL->parent = parent;//修改父节点}subR->left = parent;parent->parent = subR;if (pparnet==nullptr)//parent就是根节点{_root = subR;subR->parent = nullptr;}else{if (pparnet->left == parent)//确定parent节点是左还是右{pparnet->left = subR;}else {pparnet->right = subR;}subR->parent = pparnet;//修改父节点}subR->bf = parent->bf = 0;//更新平衡因子
}
void RoRateLR( node* parent)//左右双旋
{node* subL = parent->left;node* subLR = subL->right;int bf = subLR->bf;//先记录插入后的平衡因子RoRateL(subL);RoRateR(parent);if (bf == 0)//分情况讨论{parent->bf = 0;subL->bf = 0;subLR->bf = 0;}else if (bf == 1){parent->bf = 0;subL->bf = -1;subLR->bf = 0;}else if (bf == -1){parent->bf = 1;subL->bf = 0;subLR->bf = 0;}else{assert(false);}
}
void RoRateRL( node* parent)//右左双旋
{node* subR = parent->right;node* subRL = subR->left;int bf = subRL->bf;//先记录插入后的平衡因子RoRateR(subR);RoRateL(parent);if (bf == 0)//分情况讨论{parent->bf = 0;subR->bf = 0;subRL->bf = 0;}else if (bf == 1){parent->bf = -1;subR->bf = 0;subRL->bf = 0;}else if (bf == -1){parent->bf = 0;subR->bf = 1;subRL->bf = 0;}else{assert(false);}
}
bool Insert(const k& x, const v& v)
{if (_root == nullptr)//插入根节点{_root = new node(x, v);return true;}node* cur = _root;node* parent = nullptr;//保留父亲节点while (cur){/*介质不冗余*/if (x < cur->_key){parent = cur;cur = cur->left;}else if (x > cur->_key){parent = cur;cur = cur->right;}else{return false;}//介质冗余//if (x <= cur->_key)//相等插入到左子树//{//	parent = cur;//	cur = cur->left;//}//else if (x > cur->_key)//{//	parent = cur;//	cur = cur->right;//}}cur = new node(x, v);if (x > parent->_key){parent->right = cur;}else//相等插入左子树{parent->left = cur;}cur->parent = parent;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 = parent->parent;}else if (parent->bf == 2 || parent->bf == -2)//旋转{if (parent->bf == -2 && cur->bf == -1){RoRateR(parent);}else if (parent->bf == 2 && cur->bf == 1){RoRateL(parent);}else if (parent->bf == -2 && cur->bf == 1){RoRateLR(parent);}else if (parent->bf == 2 && cur->bf == -1){RoRateRL(parent);}else{assert(false);}break;}else{assert(false);}}return true;
}

3.7AVL树的查找

在避免了二叉搜索树退化为单叉树的情况。
AVL树的查找效率为O(logN).

四.AVL树的检测

4.1AVL树检测

AVL树我们可以递归检测每颗子树的左右高度差是否不差过1即可。

void Inorder()
{_Inorder(_root);cout << endl;
}
bool IsBalanceTree()
{return _IsBalanceTree(_root);
}
bool _IsBalanceTree(const node* root)
{// 空树也是AVL树if (nullptr == root)return true;// 计算pRoot结点的平衡因⼦：即pRoot左右⼦树的⾼度差int leftHeight = _Height(root->left);int rightHeight = _Height(root->right);int diff = rightHeight - leftHeight;// 如果计算出的平衡因⼦与pRoot的平衡因⼦不相等，或者// pRoot平衡因子的绝对值超过1，则⼀定不是AVL树if (abs(diff) >= 2){cout << root->_value << "高度差异常" << endl;return false;}if (root->bf != diff){cout << root->_key << "平衡因子异常" << endl;return false;}// pRoot的左和右如果都是AVL树，则该树⼀定是AVL树return _IsBalanceTree(root->left) && _IsBalanceTree(root->right);
}
void _Inorder(const node* root)
{if (root == nullptr){return;}_Inorder(root->left);cout << root->_key << ":" << root->_value<<endl;_Inorder(root->right);
}
size_t Size()
{return _Size(_root);
}
size_t _Size(const node* parent)
{if (parent){return 1 + _Size(parent->left)+ _Size(parent->right);}else{return 0;}
}
size_t Height()
{return _Height(_root);
}
size_t _Height(const node* parent)
{if (parent){return 1 + max(_Height(parent->left), _Height(parent->right));}else{return 0;}
}

4.2 AVL树的验证

• 检测一

void TestAVLTree1()
{AVL::AVLTree<int, int>t;// 常规的测试⽤例//int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };// 特殊的带有双旋场景的测试⽤例int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };for (auto e : a){t.Insert(e, e);}t.Inorder();cout << t.IsBalanceTree() << endl;
}

• 检测二

void TestAVLTree2()
{const int N = 100000;vector<int> v;v.reserve(N);srand(time(0));for (size_t i = 0; i < N; i++){v.push_back(rand() + i);}size_t begin2 = clock();AVL::AVLTree<int, int> t;for (auto e : v){t.Insert(e, e);}size_t end2 = clock();cout << "Insert:" << end2 - begin2 << endl;cout << t.IsBalanceTree() << endl;cout << "Height:" << t.Height() << endl;cout << "Size:" << t.Size() << endl;size_t begin1 = clock();// 确定在的值/*for (auto e : v){t.Find(e);}*/// 随机值for (size_t i = 0; i < N; i++){t.Find((rand() + i));}size_t end1 = clock();cout << "Find:" << end1 - begin1 << endl;
}

后言

这就是AVL树的深度剖析。大家自己好好消化！今天就分享到这！感谢各位的耐心垂阅！咱们下期见！拜拜~