也许因为插入的值不够随机，也许因为经过某些插入或删除操作，二叉搜索树可能会失去平衡，甚至可能退化为单链表，造成搜索效率低。
AVL Tree 是一个「加上了额外平衡条件」的二叉搜索树，其平衡条件的建立是为了确保整棵树的深度为 O(log2N)。
AVL Tree 要求任何节点的左右子树高度相差最多为 1。当违反该规定时，就需要进行旋转来保证该规定。
AVL 树节点的定义比一般的二叉搜索树复杂，它需要额外一个 parent 指针，方便后续旋转。并在每个节点中引入平衡因子，便于判断是否需要旋转。
/// @brief AVL 树节点结构
/// @tparam K 节点的 key 值
/// @tparam V 节点的 value 值
template <class K, class V>
struct AVLTreeNode {
AVLTreeNode(const pair<K, V>& kv)
: _kv(kv)
, _parent(nullptr)
, _left(nullptr)
, _right(nullptr)
, _bf(0)
{}
pair<K, V> _kv;
AVLTreeNode<K, V>* _parent;
AVLTreeNode<K, V>* _left;
AVLTreeNode<K, V>* _right;
// 左右子树高度相同平衡因子为：0
// 左子树高平衡因子为负
// 右子树高平衡因子为正
int _bf;
};
template<class K, class V>
class AVLTree {
typedef AVLTreeNode<K, V> Node;
public:
Node* Find(const K& key);
bool Insert(const pair<K, V>& kv);
private:
void RotateR(Node* parent);
void RotateL(Node* parent);
void RotateLR(Node* parent);
void RotateRL(Node* parent);
private:
Node* _root = nullptr;
};
查找
AVL 树的查找和普通的搜索二叉树一样：
/// @brief 查找指定 key 值
/// @param key 要查找的 key
/// @return 找到返回节点的指针，没找到返回空指针
Node* Find(const K& key) {
Node* cur = _root;
while (cur != nullptr) {
// key 值与当前节点值比较
if (key > cur->_kv.first) {
cur = cur->_right;
} else if (key < cur->_kv.first) {
cur = cur->_left;
} else {
return cur;
}
}
return nullptr;
}
AVL 的插入整体分为两步：
平衡因子是怎么调整的？
设新插入的节点为 pCur，新插入节点的父节点为 pParent。在插入之前，pParent 的平衡因子有三种可能：0、-1、1。
插入分为两种：
此时，pParent 的平衡因子可能有三种情况：0、正负 1、正负 2。
/// @brief 插入指定节点
/// @param kv 待插入的节点
/// @return 插入成功返回 true，失败返回 false
bool Insert(const pair<K, V>& kv) {
if (_root == nullptr) {
_root = new Node(kv);
return true;
}
// 先找到要插入的位置
Node* parent = nullptr;
Node* cur = _root;
while (cur != nullptr) {
if (kv.first > cur->_kv.first) {
parent = cur;
cur = cur->_right;
} else if (kv.first < cur->_kv.first) {
parent = cur;
cur = cur->_left;
} else {
// 已经存在，插入失败
return false;
}
}
// 将节点插入
cur = new Node(kv);
if (kv.first > parent->_kv.first) {
parent->_right = cur;
cur->_parent = parent;
} else {
parent->_left = cur;
cur->_parent = parent;
}
// 更新平衡因子，直到正常
while (parent != nullptr) {
// 调整父亲的平衡因子
if (parent->_left == cur) {
--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) {
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);
} // end of if (parent->_bf == 0)
} // end of while (parent != nullptr)
return true;
}
假设平衡因子为正负 2 的节点为 X，由于节点最多拥有两个子节点，因此可以分为四种情况：
右单旋
假设平衡因子为正负 2 的节点为 parent，parent 的父节点为 pParent，parent 的左子树为 subL，subL 的右子树为 subLR。
右单旋的操作流程：
/// @brief 进行右单旋
/// @param parent 平衡因子为正负 2 的节点
void RotateR(Node* parent) {
Node* pParent = parent->_parent;
Node* subL = parent->_left;
Node* subLR = parent->_left->_right;
// 更改链接关系
// 1. subLR 作为 parent 的左子树
parent->_left = subLR;
if (subLR != nullptr) {
subLR->_parent = parent;
}
// 2. parent 作为 subL 的右子树
subL->_right = parent;
parent->_parent = subL;
// 3. subL 作为整个子树的新根
if (parent == _root) {
// parent 为 _root，此时令 subL 为 _root
_root = subL;
subL->_parent = nullptr;
} else {
// parent 不为 _root，pParent 也就不为空
if (parent == pParent->_left) {
pParent->_left = subL;
} else {
pParent->_right = subL;
}
subL->_parent = pParent;
}
// 4. 更新平衡因子
// 观察上图明显可知
subL->_bf = 0;
parent->_bf = 0;
}
左单旋
左单旋与右单旋类似，只是方向不同。
假设平衡因子为正负 2 的节点为 parent，parent 的父节点为 pParent，parent 的右子树为 subR，subR 的左子树为 subRL。
左单旋的操作流程：
/// @brief 进行左单旋
/// @param parent 平衡因子为正负 2 的节点
void RotateL(Node* parent) {
Node* pParetn = parent->_parent;
Node* subR = parent->_right;
Node* subRL = parent->_right->_left;
// 更改链接关系
// 1. subRL 作为 parent 的右子树
parent->_right = subRL;
if (subRL != nullptr) {
subRL->_parent = parent;
}
// 2. parent 作为 subR 的左子树
subR->_left = parent;
parent->_parent = subR;
// 3. subR 作为整个子树的新根
if (parent == _root) {
_root = subR;
subR->_parent = nullptr;
} else {
if (parent == pParetn->_left) {
pParetn->_left = subR;
} else {
pParetn->_right = subR;
}
subR->_parent = pParetn;
}
// 4. 更新平衡因子
subR->_bf = 0;
parent->_bf = 0;
}
左右双旋
假设平衡因子为正负 2 的节点为 parent，parent 的左子树为 subL，subL 的右子树为 subLR。
左右双旋就是对 subL 进行一次左单旋，对 parent 进行一次右单旋。双旋也就完成了，要注意的是双旋后平衡因子的更新。
此时分三种情况：
1.新插入的节点是 subLR 的右子树
2.新插入的节点是 subLR 的左子树
3.新插入的是 subLR
结合上述情况，写出如下代码：
/// @brief 进行左右双旋
/// @param parent 平衡因子为正负 2 的节点
void RotateLR(Node* parent) {
Node* subL = parent->_left;
Node* subLR = parent->_left->_right;
int bf = subLR->_bf;
RotateL(subL);
RotateR(parent);
if (bf == 1) {
// 新插入节点是 subLR 的右子树
parent->_bf = 0;
subL->_bf = -1;
subLR->_bf = 0;
} else if (bf == -1) {
// 新插入的节点是 subLR 的左子树
parent->_bf = 1;
subL->_bf = 0;
subLR->_bf = 0;
} else if (bf == 0) {
// 新插入的节点是 subLR
parent->_bf = 0;
subL->_bf = 0;
subLR->_bf = 0;
} else {
assert(false);
}
}
右左双旋
假设平衡因子为正负 2 的节点为 parent，parent 的右子树为 subR，subR 的左子树为 subRL。
右左双旋就是对 subR 进行一次右单旋，对 parent 进行一次左单旋。流程和左右双旋一样，这里就不过多介绍了。
void RotateRL(Node* parent) {
Node* subR = parent->_right;
Node* subRL = parent->_right->_left;
int bf = subRL->_bf;
RotateR(subR);
RotateL(parent);
if (bf == 1) {
// 新插入节点是 subRL 的右子树
parent->_bf = -1;
subR->_bf = 0;
subRL->_bf = 0;
} else if (bf == -1) {
// 新插入的节点是 subRL 的左子树
parent->_bf = 0;
subR->_bf = 1;
subRL->_bf = 0;
} else if (bf == 0) {
// 新插入的节点是 subRL
parent->_bf = 0;
subR->_bf = 0;
subRL->_bf = 0;
} else {
assert(false);
}
}
