【C++笔记】AVL树

前言

各位读者朋友们大家好，上期我们讲解了map和set这两大容器的使用，这一期我们讲解最早的平衡二叉搜索树——AVL树。

一. AVL树的概念

• AVL树是最先发明的自平衡二叉查找树，AVL是一棵空树，或者具备下列性质的⼆叉搜索树：它的左右子树都是AVL树，且左右子树的高度差的绝对值不超过1。AVL树是一颗高度平衡搜索二叉树，通过控制高度差去控制平衡。
• AVL树得名于它的发明者G.M.Adelson-Velsky和E.M.Landis是两个前苏联的科学家，他们在1962年的论文中发表了它。
• AVL树实现这里我们引入一个平衡因子(balance factor)的概念，每个节点都有一个平衡因子，任何节点的平衡因子等于右子树的高度减去左子树的高度，也就是说任何节点的平衡因子等于0/1/-1，AVL树并不是必须要平衡因子，但是有了平衡因子可以更方便我们去进行观察和控制树是否平衡，就像一个风向标一样。
  
• AVL树整体节点数量和分布和完全二叉树类似，高度可控制在logN，增删查改的效率也可以控制在O(logN)，相比二叉搜索树有了本质的提升。
  

二. AVL树的实现

2.1 AVL树的结构

template <class K, class V>
struct AVLTreeNode
{pair<K, T> _kv;AVLTreeNode* _left;AVLTreeNode* _right;AVLTreeNode* _parent;int _bf;// 平衡因子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:private:Node* _root = nullptr;
};

2.2 AVL树的插入

2.2.1 AVL树插入一个值的大致过程

1. 按照二叉搜索树的规则插入一个值
2. 新增节点以后，只会影响祖先节点的高度，也就是可能会影响部分祖先节点的平衡因子，所以更新插入节点到根路径上的平衡因子，实际中最坏的情况下要更新到根，有些情况更新到中间就可以停止了，具体情况下面再详细分析。
3. 更新平衡因子过程中没有出现问题，插入结束。
4. 更新平衡因子过程中出现不平衡，对不平衡子树旋转，旋转后调平衡的同时，本质降低了子树的高度，不会再影响上一层，所以插入结束。

2.2.2 平衡因子的更新

更新原则：

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

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

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

• parent所在子树的高度是否变化决定了是否向上继续更新
  更新停止条件：

• 更新后parent的平衡因子等于0，更新中parent的平衡因子的变化为1到0或者-1到0,说明更新前parent的子树一边高一边低，新插入的节点在低的一侧，插入后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所在的子树不符合平衡要求，需要旋转处理。旋转的目标有两个：1、把parent的子树旋转平衡。 2、降低parent子树的高度，恢复到插入节点之前的高度。所以旋转之后也不需要向上更新，插入结束。
  

2.2.3 插入代码实现

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;}else{parent->_left = cur;}// 链接父亲cur->_parent = parent;// 更新平衡因子while (parent){if (cur == parent->_right)// 插入右边平衡因子++++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){// 旋转}elseassert(false);}return true;
}

插入前面的逻辑根二叉搜索树插入的逻辑一样，只是插入完节点之后，更新了平衡因子，并调整树的平衡。

2.3 旋转

2.3.1 旋转的原则

• 保持搜索树的规则
• 让旋转的树从不平衡变得平衡，其次降低树的高度
  旋转一共有四种：左单旋/右单旋/左右双旋/右左双旋

2.3.2 右单旋(单纯左子树高)

旋转核心步骤，因为5 < b子树的值 < 10，将b变成10的左子树，10变成5的右子树，5变成这棵树新的根，符合搜索树的规则，控制了平衡，同时这棵树的高度恢复到了插入之前的h+2，符合旋转原则。如果插入之前10整棵树的⼀个局部子树，旋转后不会再影响上一层，插入结束了。
上图中是抽象图，有a/b/c抽象为三棵高度为h的子树(h>=0)，a/b/c均符合AVL树的要
求。10可能是整棵树的根，也可能是⼀个整棵树中局部的子树的根。这里a/b/c是高度为h的子树，上图适用于所有的右单旋情况，下面我们展开几种情况来看一下：

• 插入前a/b/c/的高度为0
  
• 插入前a/b/c/的高度为1
  
• 插入前a/b/c/的高度为2
  
  
  a必须是x,否则就不能在10节点旋转了(可能在5的左孩子节点旋转，也可能不会旋转)
• 插入前a/b/c/的高度为3
  
  
  只有a是4个节点或者三个节点插入到两个节点上才会旋转。

2.3.3 右单旋的实现

subL当根节点，parent当subL的右子树，subLR当parent的右子树，也要注意所有的parent的处理，每个节点要将对应的父亲节点调整好

void RotateR(Node* parent)
{// subL当根节点，parent当subL的右子树，subLR当parent的右子树，注意所有的parent的处理Node* subL = parent->_left;Node* subLR = subL->_right;subL->_right = parent;parent->_left = subLR;// 从下往上链接父节点if (subLR)// subL可能为空，为空就不需要处理父亲节点subLR->_parent = parent;Node* pParent = parent->_parent;// 父节点的父亲，便于后续链接parent->_parent = subL;if (parent == _root)// 如果调整的是整棵树的根{_root = subL;subL->_parent = nullptr;}else// 局部树，链接祖先{if (parent == pParent->_left)pParent->_left = subL;elsepParent->_right = subL;subL->_parent = pParent;}// 更新平衡因子subL->_bf = parent->_bf = 0;
}

2.3.4 左单旋(单纯右子树高)

• a/b/c抽象为三棵高度为h的子树(h>=0)，a/b/c均符合AVL树的要求。10可能是整棵树的根，也可能是一整棵树中局部的子树的根。这里a/b/c是高度为h的子树，是一种概括抽象表示，他代表了所有左单旋的场景，实际左单旋形态有很多种，和右单旋很类似。
• 在a子树中插入一个新节点，导致a子树的高度从h变成h+1，不断向上更新平衡因子，导致10的平衡因子从1变成2，10为根的树左右高度差超过1，违反平衡规则。10为根的树右边太高了，需要往左边旋转，控制两棵树的平衡。
• 旋转核心步骤，因为10 < b子树的值 < 15，将b变成10的右子树，10变成15的左子树，15变成这棵树新的根，符合搜索树的规则，控制了平衡，同时这棵的高度恢复到了插入之前的h+2，符合旋转原则。如果插入之前10整棵树的一个局部子树，旋转后不会再影响上一层，插入结束了。

2.3.5 左单旋的实现

void RotateL(Node* parent)
{Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;subR->_left = parnet;// 从下往上链接父节点if (subRL)subRL->_parent = parent;Node* pParent = parent->_parent;parent->_parent = subR;if (parent == _root)// 调整的是整棵树的根{_root = subR;subR->_parent = nullptr;}else{if (parent == pParent->_left)pParent->_left = subR;elsepParent->_right = subR;subR->_parent = pParent;}subR->_bf = parent->_bf = 0;
}

2.3.6 左右双旋(左子树的右子树高)

我们先通过具体图来分析：

• 情况1、a/b/c子树的高度为0
  
• 情况2、a/b/c子树的高度h==1，在b树的右边插入节点
  
• 情况3、a/b/c子树的高度h==1，在b树的左边插入节点

2.3.7 左右双旋的实现

void RotateLR(Node* parent)
{Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;// 记录其平衡因子，看新节点是插入在左还是在右RotateL(subL);// 先左旋RotateR(parent);// 再右旋// 更新平衡因子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 if (bf == 0)// 树为空直接插入{parent->_bf = 0;subL->_bf = 0;subLR->_bf = 0;}elseassert(false);
}

2.3.8 右左双旋(右子树的左子树高)

这里和左右双旋一样，也是有三种情况

2.3.9 右左双旋的实现

void RotateRL(Node * parent)
{Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf; // 记录其平衡因子，看新节点是插入在左还是在右// 先右旋RotateR(subR);// 左旋RotateL(parent);if (bf == -1)// 左边插入 {parent->_bf = 0;subR->_bf = 1;subRL->_bf = 0;}else if (bf == 1){parent->_bf = -1;subR->_bf = 0;subRL->_bf = 0;}else if (bf == 0){parent->_bf = 0;subR->_bf = 0;subRL->_bf = 0;}elseassert(false);
}

2.4 AVL树的查找

和二叉树搜索树的逻辑一样，只是效率提升到O(logN)

Node* Find(const K& key)
{Node* cur = _root;while (cur){if (key > cur->_kv.first)// 大的往右走cur = cur->_right;else if (key < cur->_kv.first)// 小的往左走cur = cur->_left;elsereturn cur;}return nullptr;
}

三. AVL树的全体实现

AVL树的实现代码

3.1 AVL树的平衡检测

我们可以检查AVL树的高度差，如果高度差>=2，就说明不是AVL树

bool _IsBalanceTree(Node * root){if (root == nullptr)return true;int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);int diff = rightHeight - leftHeight;if (abs(diff) >= 2){cout << root->_kv.first << "高度差异常，不是AVL树！！！" << endl;return false;}if (diff != root->_bf){cout << root->_kv.first << "平衡因子异常" << endl;return false;}return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);}

测试代码

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();AVLTree<int, int> t;for (auto e : v){t.Insert(make_pair(e, e));}size_t end2 = clock();cout << "Insert:" << end2 - begin2 << endl;if (t.IsBalanceTree())cout << "AVL" << endl;cout << "Height:" << t.Height() << endl;cout << "Size:" << t.Size() << endl;size_t begin1 = clock();for (size_t i = 0; i < N; i++){t.Find((rand() + i));}size_t end1 = clock();cout << "Find:" << end1 - begin1 << endl;
}int main()
{TestAVLTree2();return 0;
}

结语

以上我们就讲完了AVL树的实现，这部分需要好好消化，感谢大家的阅读！欢迎大家批评指正！