【数据结构】AVL树

一、AVL树的概念

当我们用普通的搜索树插入数据的时候，如果插入的数据是有序的，那么就退化成了一个链表，搜索效率低下。

为了应对这种情况，就出现了AVL树（高度平衡二叉搜索树）：

当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1

AVL树的性质：

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

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

平衡因子是用来检测树的状态，如果平衡因子都在（-1， 0， 1）中，则没问题，反之则需要调整。

二、AVL的接口

AVL的节点定义：

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

2.1 插入

AVL的基本插入流程跟搜索树相似，但是AVL树多了一个平衡因子。
一旦插入新节点，就要往上更新平衡因子。

• 如果是在左边点插入，则平衡因子--
• 如果是在右边点插入，则平衡因子++

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

1️⃣ 当父节点的平衡因子变成0：说明原来是-1或1，那么也就是把矮的地方填平了，父节点所在树的高度不变，不需要继续更新。
2️⃣ 当父节点的平衡因子变成1或-1：说明原来是0，父节点所在树的高度发生变化，需要继续更新。
3️⃣ 当当父节点的平衡因子变成2或-2：违反规则，需要进行旋转处理。

所以我们可以利用parent节点（插入之前的叶子节点），从它开始往上更新。

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 (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 (kv.first < parent->_kv.first){parent->_left = cur;}else{parent->_right = 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);}break;}else{cout << "结构出错" << endl;assert(false);}}return true;
}

2.2 旋转

为了保证每个结点的左右子树高度之差的绝对值不超过1，所以当平衡因子变为-2或2时，需要旋转来保持平衡。
旋转规则：
1️⃣ 让这颗子树左右高度差不超过1
2️⃣ 旋转过程中继续保持它是搜索树
3️⃣ 更新调整孩子节点的平衡因子
4️⃣ 让这颗子树的高度根插入前保持一致

2.2.1 左单旋

二叉树的结构有无数种情况，所以我们需要总结出抽象图来分析

解释：
a/b/c是高度为h的AVL树。

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

左单旋的步骤：

1️⃣ 20的左边调整到10的右边
2️⃣ 10变成20的左边，20做根
3️⃣ 把平衡因子变为0

void RotateL(Node* parent)
{Node* top = parent->_parent;Node* right = parent->_right;// 20的左边调整到10的右边parent->_right = right->_left;if (right->_left) right->_left->_parent = parent;// 10变成20的左边，20做根right->_left = parent;parent->_parent = right;if (top)// 子树{if (parent == top->_left) top->_left = right;else top->_right = right;right->_parent = top;}else// 完整的树{_root = right;_root->_parent = nullptr;}// 更新平衡因子parent->_bf = right->_bf = 0;
}

2.2.2 右单旋

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

void RotateR(Node* parent)
{Node* top = parent->_parent;Node* left = parent->_left;Node* leftR = left->_right;parent->_left = leftR;if (leftR) leftR->_parent = parent;left->_right = parent;parent->_parent = left;if (top){if (parent == top->_left) top->_left = left;else top->_right = left;left->_parent = top;}else{_root = left;_root->_parent = nullptr;}parent->_bf = left->_bf = 0;
}

2.2.3 左右双旋

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

我们看到上面的单旋，我们会想，如果是这么插入呢？

其实这个图可以转化为：

先以10为轴进行左单旋，这样就把“折线”变成了直线，在以20为轴进行右单旋。

这里就要注意平衡因子的更新
15的平衡因子为0
但是其他两个会有三个不同的情况：

1️⃣ 当right的平衡因子为-1时（插入在b），双旋结束后parent、left、right的平衡因子分别更新为1、0、0

2️⃣ 当right的平衡因子为1时（插入在c），双旋结束后parent、left、right的平衡因子分别更新为0、-1、0

3️⃣ 当right的平衡因子为0时，双旋后parent、left、right的平衡因子分别更新为0、0、0

所以在旋转前要先进行判断在哪插入（通过平衡因子），旋转后手动更新即可。

void RotateLR(Node* parent)
{Node* left = parent->_left;Node* right = left->_right;int bf = right->_bf;// 提前记录RotateL(parent->_left);RotateR(parent);if (bf == -1)// 左子树新增{left->_bf = 0;right->_bf = 0;parent->_bf = 1;}else if (bf == 1)// 右子树新增{left->_bf = -1;right->_bf = 0;parent->_bf = 0;}else if (bf == 0)// 自己就是新增{left->_bf = right->_bf = parent->_bf = 0;}else assert(false);
}

2.2.4 右左双旋

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

三、验证

为了验证是否为二叉搜索树，我们可以先写一个中序遍历

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

为了验证是否为AVL树，我们要让每个节点的左右子树高度的绝对值差小于等于1。

int Height(Node* root)
{if (!root){return 0;}int lh = Height(root->_left) + 1;int rh = Height(root->_right) + 1;return max(lh, rh);
}bool IsBalance(Node* root)
{if (!root){return true;}int lh = Height(root->_left);int rh = Height(root->_right);if (rh - lh != root->_bf){cout << root->_kv.first << ":";cout << root->_bf << ":";cout << "平衡因子出错" << endl;return false;}if (abs(rh - lh) > 1){return false;}return IsBalance(root->_left) && IsBalance(root->_right);
}bool IsBalance()
{return IsBalance(_root);
}

我们可以用大量的随机值来测定：

void test()
{const int N = 100000;AVLTree<int, int> tt;srand(time(0));for (int i = 0; i < N; i++){int x = rand();tt.insert(make_pair(x, x));}//tt.Inorder();cout << tt.IsBalance() << endl;
}

四、源码

#pragma once
#include <iostream>
#include <string>
#include <cassert>
#include <cstdlib> using namespace std;template <class K, class V>
struct AVLNode
{AVLNode(const pair<K, V>& kv): _kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _bf(0){}pair<K, V> _kv;AVLNode<K, V>* _left;AVLNode<K, V>* _right;AVLNode<K, V>* _parent;int _bf;// 平衡因子
};template <class K, class V>
class AVLTree
{typedef AVLNode<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 (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 (kv.first < parent->_kv.first){parent->_left = cur;}else{parent->_right = 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);}break;}else{cout << "结构出错" << endl;assert(false);}}return true;}void RotateL(Node* parent){Node* top = parent->_parent;Node* right = parent->_right;// 20的左边调整到10的右边parent->_right = right->_left;if (right->_left) right->_left->_parent = parent;// 10变成20的左边，20做根right->_left = parent;parent->_parent = right;if (top)// 子树{if (parent == top->_left) top->_left = right;else top->_right = right;right->_parent = top;}else// 完整的树{_root = right;_root->_parent = nullptr;}// 更新平衡因子parent->_bf = right->_bf = 0;}void RotateR(Node* parent){Node* top = parent->_parent;Node* left = parent->_left;Node* leftR = left->_right;parent->_left = leftR;if (leftR) leftR->_parent = parent;left->_right = parent;parent->_parent = left;if (top){if (parent == top->_left) top->_left = left;else top->_right = left;left->_parent = top;}else{_root = left;_root->_parent = nullptr;}parent->_bf = left->_bf = 0;}void RotateLR(Node* parent){Node* left = parent->_left;Node* right = left->_right;int bf = right->_bf;// 提前记录RotateL(left);RotateR(parent);if (bf == -1)// 左子树新增{left->_bf = 0;right->_bf = 0;parent->_bf = 1;}else if (bf == 1)// 右子树新增{left->_bf = -1;right->_bf = 0;parent->_bf = 0;}else if (bf == 0)// 自己就是新增{left->_bf = right->_bf = parent->_bf = 0;}else assert(false);}void RotateRL(Node* parent){Node* right = parent->_right;Node* left = right->_left;int bf = left->_bf;RotateR(right);RotateL(parent);if (bf == -1){parent->_bf = 0;left->_bf = 0;right->_bf = 1;}else if (bf == 1){right->_bf = 0;left->_bf = 0;parent->_bf = -1;}else if (bf == 0){left->_bf = right->_bf = parent->_bf = 0;}else assert(false);}void _Inorder(Node* root){if (root == nullptr)return;_Inorder(root->_left);cout << root->_kv.first << "<=>" << root->_kv.second << endl;_Inorder(root->_right);}void Inorder(){_Inorder(_root);}int Height(Node* root){if (!root){return 0;}int lh = Height(root->_left) + 1;int rh = Height(root->_right) + 1;return max(lh, rh);}bool IsBalance(Node* root){if (!root){return true;}int lh = Height(root->_left);int rh = Height(root->_right);if (rh - lh != root->_bf){cout << root->_kv.first << ":";cout << root->_bf << ":";cout << "平衡因子出错" << endl;return false;}if (abs(rh - lh) > 1){return false;}return IsBalance(root->_left) && IsBalance(root->_right);}bool IsBalance(){return IsBalance(_root);}
private:Node* _root = nullptr;
};void test()
{const int N = 100000;AVLTree<int, int> tt;srand(time(0));for (int i = 0; i < N; i++){int x = rand();tt.insert(make_pair(x, x));}//tt.Inorder();cout << tt.IsBalance() << endl;
}