上文链接

• 【C++】map 容器的使用

一、什么是 AVL 树

我们都知道二叉搜索树，它的搜索效率很高，可以达到 $O(\log N)$。但是，极端情况下，一棵二叉搜索树可能退化成一个链表，就使得搜索的效率变成 $O(N)$。

那么有没有什么办法可以让这个二叉搜索树左右两端 “保持平衡”，不让它退化成链表呢？答案是肯定的，这就是我们要讲的 AVL 树。

AVL 树是最先发明的自平衡的二叉搜索树，AVL 树具备以下特点：

• 可以是一棵空树；

• 它的左右子树都是 AVL 树；

• 左右子树的高度差的绝对值不超过 1。

也就是说，AVL 树的任意一个子树的左右子树的高度差的绝对值都不超过 1，这样平衡之后，我们搜索的效率就可以控制在 $O(\log N)$，相比普通的二叉搜索树有了本质的提升。

---

二、AVL 树的实现

1. 引入平衡因子

AVL 树是一颗高度平衡的搜索二叉树，通过控制高度差去控制平衡。

在 AVL 树的实现中，我们引入一个平衡因子 (balance factor) 的概念，每个节点都有一个平衡因子，任何节点的平衡因子等于右子树的高度减去左子树的高度。也就是说任何一个节点的平衡因子都等于 0/1/-1。AVL 树并不是必须要平衡因子，但是有了平衡因子可以更方便我们去观察和控制树是否平衡，如同风向标一样。

下面这棵树就是一棵典型的 AVL 树。

而下面这棵树就不是一棵 AVL 树，因为 10 这个节点它的左右子树的高度差超过了 1。

---

2. 整体结构

template<class K, class V>
struct AVLTreeNode
{// 需要 parent 指针，后续更新平衡因子可以看到pair<K, V> _kv;AVLTreeNode<K, V>* _left;AVLTreeNode<K, V>* _right;AVLTreeNode<K, V>* _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;
};

---

3. AVL 树中的插入操作

(1) 插入节点

在 AVL 树中插入节点的过程如下：

① 按普通二叉搜索树的规则插入节点；

② 插入新节点以后，可能会导致树的高度发生变化，也就可能会影响某些节点的平衡因子，所以我们需要更新平衡因子。但是观察一下就会发现，插入操作只会影响插入节点的祖先的平衡因子，所以只需要更新从新增节点到根节点路径上节点的平衡因子即可。实际中最坏情况下要更新到根，有些情况更新到中间就可以停止了，具体情况我们下面再详细分析；

③ 更新平衡因子过程中没有出现某个子树不平衡（平衡因子的绝对值大于 1），则插入操作结束；

④ 更新平衡因子过程中如果出现不平衡，对不平衡的子树需要进行旋转操作，旋转的目的是调整这个子树使其平衡，这个操作不会影响更上一层的平衡因子，因此旋转之后插入操作结束。

---

(2) 更新平衡因子

更新规则

由于这里我们规定平衡因子 $=$ 右子树高度 $-$ 左子树高度，所以插入节点后，必然会增加该节点父节点 (parent) 子树的高度，因此如果新增节点在 parent 的右子树，那么 parent 的平衡因子 += 1，新增节点在 parent 的左子树，parent 的平衡因子 -= 1。

但是这还没有结束，新增节点的所有祖先的高度都有可能发生变化，所以我们需要继续顺着从新增节点一直到根节点这条路径更新下去，那么什么时候停止呢？

---

停止更新条件

• 如果更新后 parent 的平衡因子等于 0，即 parent 的平衡因子由 -1 变为 0 或者 由 1 变为 0，说明更新前以 parent 为根的子树一边高一边低，此时新增的节点插入在低的那边，插入后以 parent 为根的子树高度不变，不会影响 parent 的父亲节点的平衡因子，因此停止更新。

• 如果更新后 parent 的平衡因子等于 1 或 -1，即 parent 的平衡因子由 0 变为 1或者由 0 变为 -1，说明更新前以 parent 为根的子树两边一样高。插入节点后，以 parent 为根的子树一边高一边低，但仍然符合平衡要求，只不过高度增加了 1，此时会影响 parent 的父亲节点的平衡因子，所以要继续向上更新。继续向上更新的规则与停止条件同理。

• 如果更新后 parent 的平衡因子等于 2 或 -2，即 parent 的平衡因子由 1 变为 2或者由 -1 变为 -2，说明更新前 parent 子树一边高一边低，新增的节点在高的那边，以 parent 为根的子树高的那边更高了，破坏了平衡，因此需要对这棵子树进行旋转处理，旋转的目的有两个：

  • 把 parent 子树调整为平衡状态；
  • 降低 parent 子树的高度，恢复到插入节点以前的高度。

  所以旋转后也不需要继续往上更新，此时停止更新。

• 一直更新到根，更新后根的平衡因子是 0、1 或 -1 都停止更新。如果更新后为 2 或者 -2，那么对整棵树旋转后停止更新。

下面是几个示例：

示例一：插入 -1 节点，由于插入在 1 节点的左子树，所以 1 节点的平衡因子 -= 1。之后由于 1 节点的平衡因子变成 -1，所以需要继续向上更新。更新到 3 节点时，平衡因子依旧 -= 1，此时平衡因子变为 0，根据规则，此时停止更新。

示例二：更新到 10 节点时，平衡因子变为 2，此时对以 10 节点为根的这棵子树进行旋转操作，调整平衡，旋转之后停止更新。

示例三：一直更新到根节点，无论是 0、1 或者 -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;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){// 此时不平衡，需要旋转处理// ...break;}else assert(false);}return true;
}

---

4. 旋转

(1) 旋转的目的

• 保持搜索树的规则；

• 让不平衡的树变成平衡的，其次降低旋转树的高度。

旋转总共分为四种，左单旋/右单旋/左右双旋/右左双旋。根据不同的不平衡情况我们需要采取不同的旋转方式。

---

(2) 右单旋

如下图所示，一棵以 10 为根的树，由 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 节点) 的左子树的左边，这种情况可以简单记作左左型 (LL 型) 此时我们需要对以 10 为根的这棵树进行右单旋的操作。

旋转核心步骤：因为 5 < b子树的值 < 10，所以将 b 变成 10 的左子树，10 变成 5 的右子树，5 变成这棵树新的根，这样依旧符合搜索树的规则，并且控制了平衡，同时这棵的高度恢复到了插入之前，达到了旋转的目的。10 整棵树的一个局部子树，旋转后不会再影响上一层的平衡因子，插入结束。

下面是一些具体的情况：

右单旋的具体情况可以有无数多种，是列举不完的，比如下面我们可以简单分析一下：

但是实际上我们并不需要关注什么 x/y/z，我们只需要关注不平衡的那个节点以及采取何种旋转方式，至于 a/b/c 三个子树长什么样我们并不关心。

下面是代码演示：

// 在插入操作中，发现不平衡时我们需要进行旋转，并判断采取何种旋转方式
else if (parent->_bf == 2 || parent->_bf == -2)
{// 此时不平衡，需要旋转处理// 插入在失衡节点的左子树的左边 --> 右单旋if(parent->_bf == -2 && cur->_bf == -1) RotateR(parent);break;
}// 右单旋
void RotateR(Node* parent)
{Node* subL = parent->_left;  // 左子树Node* subLR = subL->_right;  // 左子树的右子树（b）parent->_left = subLR;if (subLR) subLR->_parent = parent;  // 注意 b 有可能为空，所以要判断一下Node* ppnode = parent->_parent;subL->_right = parent;parent->_parent = subL;// parent 有可能是整棵树的根，也可能是局部子树的根 // 如果是整棵树的根，要修改 _root // 如果是局部的根，指针要跟上一层链接if (parent == _root)  // 是整棵树的根{_root = subL;subL->_parent = nullptr;}else  // 是局部的根{if (ppnode->_left == parent) ppnode->_left = subL;else ppnode->_right = subL;subL->_parent = ppnode;}parent->_bf = subL->_bf = 0;
}

---

(3) 左单旋

如下图所示，一棵以 10 为根的树，由 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 节点) 的右子树的右边，这种情况可以简单记作右右型 (RR 型) 此时我们需要对以 10 为根的这棵树进行左单旋的操作。

左单旋和右单旋的操作方式几乎是一样的，二者可以看作是一个镜像的关系。

下面是代码演示：

// 在插入操作中，发现不平衡时我们需要进行旋转，并判断采取何种旋转方式
else if (parent->_bf == 2 || parent->_bf == -2)
{// ...// 插入在失衡节点的右子树的右边 --> 左单旋if (parent->_bf == 2 && cur->_bf == 1) RotateL(parent);break;
}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 (parent == _root){_root = subR;subR->_parent = nullptr;}else{if (ppnode->_left == parent) ppnode->_left = subR;else ppnode->_right = subR;subR->_parent = ppnode;}parent->_bf = subR->_bf = 0;
}

---

(4) 左右双旋

在一些情况下，右单旋和左单旋是无法解决不平衡问题的。比如下面的两种情况，左边高时，如果插入位置不是在 a 子树，而是插入在b 子树，b 子树高度从 h 变成 h+1，引发旋转，右单旋后，树依旧不平衡。

右单旋解决的是插入在不平衡节点的左子树的左边，即纯粹的左边高，但是如果插入在 b 子树中，10 为根的子树不再是纯粹的左边高，因为对于 10 来说是左边高，而对于 5 来说是右边高，此时需要用两次旋转才能解决，以 5 为旋转点进行一个左单旋，以 10 为旋转点再进行一个右单旋，这棵树这棵树就平衡了。

像上述这种情况，插入节点在不平衡节点的左子树的右边时，可以记作左右型 (LR 型)，此时采用左右双旋的方法去调整平衡，即先对不平衡节点的左子树进行一次左单旋，之后再对不平衡节点为根的子树进行一次右单旋。

具体的，可以分为以下三种情况来讨论：

下面是代码演示：

// 在插入操作中，发现不平衡时我们需要进行旋转，并判断采取何种旋转方式
else if (parent->_bf == 2 || parent->_bf == -2)
{// ...// 插入在失衡节点的左子树的右边 --> 左右双旋if (parent->_bf == -2 && cur->_bf == 1) RotateLR(parent);break;
}void RotateLR(Node* parent)
{Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;RotateL(parent->_left);RotateR(parent);if (bf == 0){subL->_bf = 0;subLR->_bf = 0;parent->_bf = 0;}else if (bf == -1){subL->_bf = 0;subLR->_bf = 0;parent->_bf = 1;}else if (bf == 1){subL->_bf = -1;subLR->_bf = 0;parent->_bf = 0;}else assert(false);
}

---

(5) 右左双旋

右左双旋与左右双旋几乎一样，二者可以看作是一个对称的关系。当插入节点在不平衡节点的右子树的左边时，可以记作右左型 (RL 型)，此时采用右左双旋的方法去调整平衡，即先对不平衡节点的右子树进行一次右单旋，之后再对不平衡节点为根的子树进行一次左单旋。

具体可以分为以下几种情况：

以下是代码演示：

// 在插入操作中，发现不平衡时我们需要进行旋转，并判断采取何种旋转方式
else if (parent->_bf == 2 || parent->_bf == -2)
{// ...// 插入在失衡节点的右子树的左边 --> 右左双旋if (parent->_bf == 2 && cur->_bf == -1) RotateRL(parent);break;
}void RotateRL(Node* parent)
{Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(parent->_right);RotateL(parent);if (bf == 0){subR->_bf = 0;subRL->_bf = 0;parent->_bf = 0;}else 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 assert(false);
}

---

5. AVL 树的查找与删除

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 树的删除操作这里不做重点讲解，这个操作会比插入稍复杂一些，但核心思路依然是走正常的二叉搜索树的删除操作 + 更新平衡因子 + 失衡时进行旋转。

---

6. AVL 树的平衡检测

我们实现的 AVL 树是否合格，需要通过检查左右子树高度差的的程序进行反向验证，同时检查一下节点的平衡因子更新是否出现了问题。

// 获取树的高度
int _Height(Node* root)
{if (root == nullptr) return 0;int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}bool _IsBalanceTree(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->_kv.first << "⾼度差异常" << endl;return false;}if (root->_bf != diff){cout << root->_kv.first << "平衡因⼦异常" << endl;return false;}// pRoot 的左和右如果都是 AVL 树，则该树一定是 AVL 树 return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);
}

---

三、完整代码

// AVLTree.h
#pragma once
#include<cassert>
#include<utility>
#include<cmath>using namespace std;template<class K, class V>
struct AVLTreeNode
{// 需要 parent 指针，后续更新平衡因子可以看到pair<K, V> _kv;AVLTreeNode<K, V>* _left;AVLTreeNode<K, V>* _right;AVLTreeNode<K, V>* _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: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->_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) RotateR(parent);else if (parent->_bf == 2 && cur->_bf == 1) RotateL(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;}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;}void IsBalanced(){return _IsBalanced(_root);}int Height(){return _Height(_root);}private:void RotateR(Node* parent){Node* subL = parent->_left;  // 左子树Node* subLR = subL->_right;  // 左子树的右子树（b）parent->_left = subLR;if (subLR) subLR->_parent = parent;  // 注意 b 有可能为空，所以要判断一下Node* ppnode = parent->_parent;subL->_right = parent;parent->_parent = subL;// parent 有可能是整棵树的根，也可能是局部子树的根 // 如果是整棵树的根，要修改 _root // 如果是局部的根，指针要跟上一层链接if (parent == _root)  // 是整棵树的根{_root = subL;subL->_parent = nullptr;}else  // 是局部的根{if (ppnode->_left == parent) ppnode->_left = subL;else ppnode->_right = subL;subL->_parent = ppnode;}parent->_bf = subL->_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 (parent == _root){_root = subR;subR->_parent = nullptr;}else{if (ppnode->_left == parent) ppnode->_left = subR;else ppnode->_right = subR;subR->_parent = ppnode;}parent->_bf = subR->_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 == 0){subL->_bf = 0;subLR->_bf = 0;parent->_bf = 0;}else if (bf == -1){subL->_bf = 0;subLR->_bf = 0;parent->_bf = 1;}else if (bf == 1){subL->_bf = -1;subLR->_bf = 0;parent->_bf = 0;}else assert(false);}void RotateRL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(parent->_right);RotateL(parent);if (bf == 0){subR->_bf = 0;subRL->_bf = 0;parent->_bf = 0;}else 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 assert(false);}int _Height(Node* root){if (root == nullptr) return 0;int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;}bool _IsBalanceTree(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->_kv.first << "高度差异常" << endl;return false;}if (root->_bf != diff){cout << root->_kv.first << "平衡因子异常" << endl;return false;}// pRoot 的左和右如果都是 AVL 树，则该树一定是 AVL 树 return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);}private:Node* _root = nullptr;
};

下文链接

• 【C++】红黑树（详解）