AVL树是由G. M. Adelson-Velsky和E. M. Landis 在1962年发明， 是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为1，也被称为高度平衡树。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。
目录
- AVL Tree
- Tips
- BST改进
- 添加导致的失衡
- 右旋 LL
- 左旋 RR
- 左旋+右旋 LR
- 右旋+左旋 RL
- 添加后的操作 C++
- 添加代码 C++
- 删除导致的失衡
- 删除代码 C++
- 完整代码 C++
Tips
二叉搜索树(BST)
对于普通的二叉搜索树（BST)，增加或删除节点都可能使其退化成链表，时间复杂度就是O(N)，AVL在BST的基础上维护了树的平衡，通过树的旋转保持整棵树趋向于一颗满二叉树，使其高度保持在 O(logN)
BST改进
添加节点12，此时这颗树并不平衡。
中序遍历依旧是有序的，但保持了树的平衡，本质上其实是为了减少树的高度
添加导致的失衡
AVL添加节点前都是平衡的，添加节点最坏情况可能会导致其祖先节点都失衡（父节点不会失衡）。
右旋 LL
红色节点为新增节点，添加后此时子树是失衡的，通过以下步骤恢复平衡。
- g.left = p.right
- p.right = g
- 使p成为新的根
注意旋转后需要维护高度和parent的指向。
旋转后子树依旧是有序的
旋转后根节点往上的其他节点并不会失衡，因为添加新节点前AVL永远是平衡的，旋转后子树的高度并不会发生改变，所以添加节点只需要一次的旋转，而删除可能需要 logN 次旋转。
左旋 RR
和LL情况相反
- g.right = p.left
- p.left = g
- 使p成为新的根
注意旋转后需要维护高度和parent的指向。
也依旧有序。
左旋+右旋 LR
需要进行两次旋转，向对p进行右旋，将n旋转上来，再对g进行左旋，此时n成为新的根节点
注意维护高度和parent指向
子树恢复平衡，也依旧有序。
右旋+左旋 RL
和LR差不多，也是通过旋转想办法将n成为根节点。
注意维护高度和parent指向
子树恢复平衡，也依旧有序。
添加后的操作 C++
void afterAdd(Node* cur)
{
//从新增节点的父节点往上
while ((cur = cur->_parent) != nullptr)
{
if (cur->isBalance()) //平衡情况下更新高度信息。
cur->reHight();
else { //只需要一次旋转就可以恢复平衡。
maintain(cur); //调整子树恢复平衡
break;
}
}
}
添加代码 C++
bool put(const K& key, const V& value)
{
if (!_root) {
_root = new Node(key, value);
_size++;
return true;
}
Node* cur = _root;
while (cur)
{
if (cur->_key < key) //大往右
{
if (cur->_right) //新节点都为叶子节点
cur = cur->_right;
else {
Node* newNode = new Node(key, value);
cur->_right = newNode;
newNode->_parent = cur;
afterAdd(newNode); //添加后一路往上更新高度和维持平衡
_size++;
return true;
}
}
else if (cur->_key > key) //小往右
{
if (cur->_left)
cur = cur->_left;
else {
Node* newNode = new Node(key, value);
cur->_left = newNode;
newNode->_parent = cur;
afterAdd(newNode); //添加后一路往上更新高度和维持平衡
_size++;
return true;
}
}
else { //存在直接更新value
cur->_value = value;
return true;
}
}//end of while
return true;
}
删除导致的失衡
删除节点可能导致其父节点，或往上的祖先节点失衡（只会存在一个失衡）。
我们通过旋转可以让失衡的子树恢复了平衡，但可能导致更高层次的节点发生失衡，最坏情况下，每次旋转可能导致所有祖先节点都失衡，最坏logN次的旋转调整。
删除代码 C++
bool remove(const K& key)
{
if (empty()) return false;
//只有根节点
if (_root->_key == key && size() == 1) {
_size = 0;
delete _root, _root = nullptr;
return true;
}
Node* cur = _root;
bool find = false;
while (cur)
{
if (cur->_key < key)
cur = cur->_right;
else if (cur->_key > key)
cur = cur->_left;
else {
find = true;
break;
}
}//end of while
//没找到直接返回
if (!find) {
return false;
}
if (cur->_left && cur->_right) //度为2
{
Node* prev = cur->_left; //找到前驱节点
while (prev && prev->_right)
prev = prev->_right;
cur->_key = prev->_key, cur->_value = prev->_value;
cur = prev;
}
if (cur->_left || cur->_right) //度为1情况
{
Node* parent = cur->_parent;
Node* child = cur->_left ? cur->_left : cur->_right;
parent->_left == cur ? parent->_left = child : parent->_right = child;
child->_parent = parent;
afterRemove(cur);
}
else { //度为0的情况
Node* parent = cur->_parent;
parent->_left == cur ? parent->_left = nullptr : parent->_right = nullptr;
afterRemove(cur);
}
_size--;
delete cur;
return true;
}
#include#include #include #include using namespace std; template class AVL { public: struct Node { Node(const K& key, const V& value) : _key(key), _value(value), _parent(nullptr), _left(nullptr), _right(nullptr) {} Node* tallerChild() { size_t left = this->_left->hight(); size_t right = this->_right->hight(); return left < right ? this->_right : this->_left; } size_t hight() { return !this ? 0 : this->_hight; } bool isBalance() { int left = this->_left->hight(); int right = this->_right->hight(); return fabs(left - right) < 2 ? true : false; } void reHight() { int left = this->_left->hight(); int right = this->_right->hight(); this->_hight = left > right ? left + 1 : right + 1; } K _key; V _value; Node* _parent; Node* _left; Node* _right; size_t _hight = 1; }; public: bool put(const K& key, const V& value) { if (!_root) { _root = new Node(key, value); _size++; return true; } Node* cur = _root; while (cur) { if (cur->_key < key) //大往右 { if (cur->_right) //新节点都为叶子节点 cur = cur->_right; else { Node* newNode = new Node(key, value); cur->_right = newNode; newNode->_parent = cur; afterAdd(newNode); //添加后一路往上更新高度和维持平衡 _size++; return true; } } else if (cur->_key > key) //小往右 { if (cur->_left) cur = cur->_left; else { Node* newNode = new Node(key, value); cur->_left = newNode; newNode->_parent = cur; afterAdd(newNode); //添加后一路往上更新高度和维持平衡 _size++; return true; } } else { //存在直接更新value cur->_value = value; return true; } }//end of while return true; } bool remove(const K& key) { if (empty()) return false; //只有根节点 if (_root->_key == key && size() == 1) { _size = 0; delete _root, _root = nullptr; return true; } Node* cur = _root; bool find = false; while (cur) { if (cur->_key < key) cur = cur->_right; else if (cur->_key > key) cur = cur->_left; else { find = true; break; } }//end of while //没找到直接返回 if (!find) { return false; } if (cur->_left && cur->_right) //度为2 { Node* prev = cur->_left; //找到前驱节点 while (prev && prev->_right) prev = prev->_right; cur->_key = prev->_key, cur->_value = prev->_value; cur = prev; } if (cur->_left || cur->_right) //度为1情况 { Node* parent = cur->_parent; Node* child = cur->_left ? cur->_left : cur->_right; parent->_left == cur ? parent->_left = child : parent->_right = child; child->_parent = parent; afterRemove(cur); } else { //度为0的情况 Node* parent = cur->_parent; parent->_left == cur ? parent->_left = nullptr : parent->_right = nullptr; afterRemove(cur); } _size--; delete cur; return true; } void afterRemove(Node* cur) { while ((cur = cur->_parent) != nullptr) { if (cur->isBalance()) cur->reHight(); else { maintain(cur); } } } void afterAdd(Node* cur) { while ((cur = cur->_parent) != nullptr) { if (cur->isBalance()) cur->reHight(); else { maintain(cur); break; } } } bool contains(const K& key) { if (empty()) return false; Node* cur = _root; while (cur) { if (cur->_key > key) cur = cur->_left; else if (cur->_key < key) cur = cur->_right; else return true; } return false; } void maintain(Node* grand) { if (!grand) return; Node* parent = grand->tallerChild(); Node* node = parent ? parent->tallerChild() : nullptr; if (parent && node && parent == grand->_left) { if (node == parent->_left) //LL right_rotate(grand); else { //LR left_rotate(parent); right_rotate(grand); } } else if (parent && node && parent == grand->_right) { if (node == parent->_right) //RR left_rotate(grand); else { //RL right_rotate(parent); left_rotate(grand); } } } void left_rotate(Node* cur) { Node* parent = cur->_parent; bool isRoot = (cur == _root) ? true : false; Node* R = cur->_right; cur->_parent = R; cur->_right = R->_left; if (cur->_right) cur->_right->_parent = cur; R->_left = cur; cur->reHight(); R->reHight(); if (isRoot) { _root = R; _root->_parent = nullptr; } else { parent->_left == cur ? parent->_left = R : parent->_right = R; R->_parent = parent; } } void right_rotate(Node* cur) { Node* parent = cur->_parent; bool isRoot = (cur == _root) ? true : false; Node* L = cur->_left; cur->_parent = L; cur->_left = L->_right; if (cur->_left) cur->_left->_parent = cur; L->_right = cur; cur->reHight(); L->reHight(); if (isRoot) { _root = L; _root->_parent = nullptr; } else { parent->_left == cur ? parent->_left = L : parent->_right = L; L->_parent = parent; } } size_t size() { return _size; } bool empty() { return _root == nullptr; } //private: Node* _root = nullptr; size_t _size = 0; };
