1. AVL树的概念

AVL树是最早被发明的自平衡二叉搜索树，AVL是一颗空树，或者具备下列性质的二叉搜索树：

它的左右子树都是AVL树，且左右子树的高度差的绝对值不超过1（由于结点个数的限制，某些情况下无法做到高度差为0，所以此处定义的是1）

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

AVL树得名于它的发明者G. M. Adelson-Velsky和E. M. Landis是两个前苏联的科学家，他们在1962年的论文《An algorithm for the organization of information》中发表了它。

AVL树整体结点数量和分布和完全二叉树类似，高度可以控制在logN ，那么增删查改的效率也可以控制在logN ，相比二叉搜索树有了本质的提升。

本文仅介绍AVL树最核心的两个部分的实现（插入/删除，只有这两个操作会影响到搜索树的结构），其他部分于普通二叉搜索树无异。

可参考：C++笔记---二叉搜索树_c++二叉树高度-CSDN博客

平衡因子

AVL树实现这里我们引入一个平衡因子(balance factor)的概念。

每个结点都有一个平衡因子，任何结点的平衡因子等于右子树的高度减去左子树的高度，也就是说任何结点的平衡因子等于0/1/-1。

AVL树并不是必须要平衡因子，但是有了平衡因子可以更方便我们去进行观察和控制树是否平衡，就像一个风向标一样。

在其他的地方我见识过直接使用高度来控制平衡的（还存在其他实现方式，但我每见识过），但是是在需要使用的时候再利用函数去计算树的高度，效率相对来说可能较低，但是省去了在调整树的高度的过程中对平衡因子进行更新的这一麻烦步骤。

既然本文都提出了平衡因子的概念，那么我自然是更倾向于平衡因子。

在原本二叉搜索树的结点中添加上平衡因子_bf，以及_parent（方便调整）：

<code>template<class K, class V>

struct BSTreeNode

{

K _key;

V _value;

BSTreeNode<K, V>* _left;

BSTreeNode<K, V>* _right;

BSTreeNode<K, V>* _parent;

int _bf;

BSTreeNode(const K& key, const V& value)

:_key(key)

, _value(value)

, _left(nullptr)

, _right(nullptr)

, _parent(nullptr)

, _bf(0)

{}

};

2. AVL树的插入

2.1 插入的大致过程

1. 按照普通二叉搜索树的方式，先将值插入到树中。

2. 插入之后，该结点的祖先可能会受到影响，依次向上检查并更新平衡因子。

3. 若发现不平衡的祖先(_bf为2或-2)，则进行调整，使之平衡。

AVL树针对不平衡的调整被称为旋转，接下来会介绍。

平衡因子更新规则

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

2. 只有子树的高度变化，才会影响到结点的平衡因子

3. 结点插入到其父节点parent的左子树，则parent的平衡因子--；结点插入到其父节点parent的右子树，则parent的平衡因子++

4. 若当前子树的高度发生了变化，则需要向上继续更新

 更新停止条件

• 更新后parent的平衡因子等于0，更新中parent的平衡因子变化为 - 1->;0 或者 1->0，说明更新前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所在的子树高的那边更高了，破坏了平衡，parent所在的子树不符合平衡要求，需要旋转处理，旋转处理之后parent所在子树高度会与之前相同，此时不需要继续向上更新。

2.2 插入并更新平衡因子代码实现

bool Insert(const K& key, const V& value)

{

if (_root == nullptr)

{

_root = new Node(key, value);

return true;

}

Node* cur = _root, *parent = nullptr;

while (cur)

{

parent = cur;

if (key < cur->_key)

cur = cur->_left;

else if (key > cur->_key)

cur = cur->_right;

else

return false;

}

cur = new Node(key, value);

cur->_parent = parent;

if (key < cur->_parent->_key)

{

cur->_parent->_left = cur;

cur->_parent->_bf -= 1;

}

else

{

cur->_parent->_right = cur;

cur->_parent->_bf += 1;

}

cur = cur->_parent;

while (cur->_parent && cur->_bf)

{

if (cur->_bf == -2 || cur->_bf == 2)

{

// 进行调整

break;

}

else if (cur->_bf == -1 || cur->_bf == 1)

{

if (cur == cur->_parent->_left)

cur->_parent->_bf -= 1;

else

cur->_parent->_bf += 1;

}

else

assert(false);

cur = cur->_parent;

}

return true;

}

2.3 旋转

在插入新结点之后，导致AVL树不平衡的情形一共有四种:

我们并不关注子树的结构，只关心其高度，所以使用长方形来简单概括子树。

针对这四种情形，我们也有四种对应的旋转方案：右单旋/左单旋/左右双旋/右左双旋。

旋转的原则：

1. 保持搜索树的规则

2. 让旋转的树从不满足变平衡，其次降低旋转树的高度。

2.3.1 右单旋

适用于parent._bf == -2，subL._bf == -1的情况（左倾右旋）。

如图所示，这样的调整方法就像是以subL为中心进行了一次顺时针的旋转。

代码实现：

<code>void RotateR(Node* parent)

{

Node* subL = parent->;_left;

Node* subLR = subL->_right;

subL->_right = parent;

subL->_parent = parent->_parent;

parent->_parent = subL;

parent->_left = subLR;

if(subLR)

subLR->_parent = parent;

if (parent == _root)

_root = subL;

else

{

if (subL->_parent->_left == parent)

subL->_parent->_left = subL;

else

subL->_parent->_right = subL;

}

subL->_bf = parent->_bf = 0;

}

注意结点之间的相互连接，不要漏掉或连错。

注意平衡因子的更新，被概括起来的子树作为一个整体，平衡因子不会受到影响，而parent和subL的平衡因子在调整之后都为0.

还要考虑边界情况，如parent恰好是_root时，需要更新_root。 

2.3.2 左单旋

适用于parent._bf == 2，subR._bf == 1的情况（右倾左旋）。

 我坦白了，这图就是把上面的前后两棵树分别镜像得到的，代码上也是如出一辙。

代码实现：

<code>void RotateL(Node* parent)

{

Node* subR = parent->;_right;

Node* subRL = subR->_left;

subR->_left = parent;

subR->_parent = parent->_parent;

parent->_parent = subR;

parent->_right = subRL;

if(subRL)

subRL->_parent = parent;

if (parent == _root)

_root = subR;

else

{

if (subR->_parent->_left == parent)

subR->_parent->_left = subR;

else

subR->_parent->_right = subR;

}

subR->_bf = parent->_bf = 0;

}

2.3.3 左右双旋

适用于parent._bf == -2，subL._bf == 1的情况(先使其左倾，再右旋)。

我感觉叫做左右旋两次更加合适，顾名思义，就是先进行一次左单旋，再进行一次右单旋。

第一次以subL为parent，这样就使得整颗子树满足了使用右单旋的条件，再正常使用右单旋即可。

左右双旋的平衡因子调整：

调整后，一定满足subLR._bf = 0。

但由于第一次左旋其实是不满足使用左旋的条件的，所以需要重新考量subL和parent的平衡因子。

从结果上看，左右双旋使得：

1. subLR成为了子树的根。

2. subL成为subLR的左子树，parent成为subLR的右子树。

3. subLR的左子树交给subL成为其右子树，subLR的右子树交给parent成为其左子树。

 所以，在调整前：

如果subLR._bf == -1，则调整后，subL._bf = 0，parent._bf = 1；

如果subLR._bf == 1，则调整后，subL._bf = -1，parent._bf = 0；

代码实现：

<code>void RotateLR(Node* parent)

{

Node* subL = parent->;_left;

Node* subLR = subL->_right;

int flag = subLR->_bf;

RotateL(parent->_left);

RotateR(parent);

if (flag == -1)

{

parent->_bf = 1; subL->_bf = 0; subLR->_bf = 0;

}

else if (flag == 1)

{

parent->_bf = 0; subL->_bf = -1; subLR->_bf = 0;

}

else if (flag == 0)

{

parent->_bf = 0; subL->_bf = 0; subLR->_bf = 0;

}

else

assert(false);

}

2.3.4 右左双旋

喷不了，这个是真镜像，代码也是镜像。

左改右，右改左，调整平衡因子时parent和subR角色交换。

代码实现： 

<code>void RotateRL(Node* parent)

{

Node* subR = parent->;_right;

Node* subRL = subR->_left;

int flag = subRL->_bf;

RotateR(parent->_right);

RotateL(parent);

if (flag == -1)

{

parent->_bf = 0; subR->_bf = 1; subRL->_bf = 0;

}

else if (flag == 1)

{

parent->_bf = -1; subR->_bf = 0; subRL->_bf = 0;

}

else if (flag == 0)

{

parent->_bf = 0; subR->_bf = 0; subRL->_bf = 0;

}

else

assert(false);

}

2.4 插入的补全代码

bool Insert(const K& key, const V& value)

{

if (_root == nullptr)

{

_root = new Node(key, value);

return true;

}

Node* cur = _root, *parent = nullptr;

while (cur)

{

parent = cur;

if (key < cur->_key)

cur = cur->_left;

else if (key > cur->_key)

cur = cur->_right;

else

return false;

}

cur = new Node(key, value);

cur->_parent = parent;

if (key < cur->_parent->_key)

{

cur->_parent->_left = cur;

cur->_parent->_bf -= 1;

}

else

{

cur->_parent->_right = cur;

cur->_parent->_bf += 1;

}

cur = cur->_parent;

while (cur->_parent && cur->_bf)

{

if (cur->_bf == -2)

{

if (cur->_left->_bf == -1)

RotateR(cur);

else

RotateLR(cur);

break;

}

else if (cur->_bf == 2)

{

if (cur->_right->_bf == 1)

RotateL(cur);

else

RotateRL(cur);

break;

}

else if (cur->_bf == -1 || cur->_bf == 1)

{

if (cur == cur->_parent->_left)

cur->_parent->_bf -= 1;

else

cur->_parent->_bf += 1;

}

else

assert(false);

cur = cur->_parent;

}

return true;

}

3. AVL树的删除

3.1 删除的大致过程

1. 找到要删除的结点，若没有则返回false。

2. 如果要删除的结点既有左子树又有右子树，则采用替换法更新要删除的结点。

3. 按照至少有一个子树为空的逻辑进行删除。

4. 更新平衡因子。

 平衡因子更新规则

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

2. 只有子树的高度变化，才会影响到结点的平衡因子

3. 删除的结点在其父节点parent的左子树，则parent的平衡因子++；删除的结点在其父节点parent的右子树，则parent的平衡因子--(与插入时相反)

4. 若当前子树的高度发生了变化，则需要向上继续更新

更新停止条件

• 更新后parent的平衡因子等于0，更新中parent的平衡因子变化为 - 1->0 或者 1->0，说明更新前parent子树一边高一边低，被删除的结点在高的那边，删除后parent所在的子树高度减少1，会影响parent父节点的平衡，继续向上更新。

• 更新后parent的平衡因子等于1 或 - 1，更新前更新中parent的平衡因子变化为0->1 或者 0-> - 1，说明更新前parent子树两边一样高，删除指定结点后，parent所在的子树一边高一边低，parent所在的子树符合平衡要求，但是高度未发生变化，不会影响arent的父亲结点的平衡因子，更新结束。

• 更新后parent的平衡因子等于2 或 - 2，更新前更新中parent的平衡因子变化为1->2 或者 - 1-> - 2，说明更新前parent子树一边高一边低，删除的结点在低的那边，parent所在的子树低的那边更低了，破坏了平衡，parent所在的子树不符合平衡要求，需要旋转处理，而旋转之后会有两种不同的情况：

1. subR/subL的平衡因子为1或-1，旋转之后高度与旋转之前相比会减少1(与插入时情况相同，旋转减少高度)，此时需要继续向上更新。

2. subR/subL的平衡因子为0，旋转之后高度与删除之前相同，此时结束更新。

蓝色表示由于结点被删除而导致该子树减少1的高度。

可以看到，上面的情况与插入时相同，旋转后高度下降，而下面的情况只会发生在删除中，旋转之后高度不变，但是子树变得平衡了。

 3.2 代码实现

<code>bool Erase(const K& key)

{

Node* del = Find(key);

if (del == nullptr)

return false;

if(del->;_left != nullptr && del->_right != nullptr)//左右都不空，替换法更新要删除的结点

{

Node* replace = del->_right;

while (replace->_left) { replace = replace->_left; }

std::swap(del->_key, replace->_key);

std::swap(del->_value, replace->_value);

del = replace;

}

//接下来是至少一个孩子为空的直接删除逻辑

if (del->_parent == nullptr)//删除的是根结点

{

if (del->_left == nullptr)

_root = del->_right;

else

_root = del->_left;

if (_root != nullptr)//左右都为空时不用更新

_root->_parent = nullptr;

}

else

{

if (del == del->_parent->_left)

{

if (del->_left == nullptr)

{

del->_parent->_left = del->_right;

if (del->_right != nullptr)//左右都为空时不更新

del->_right->_parent = del->_parent;

}

else

{

del->_parent->_left = del->_left;

del->_left->_parent = del->_parent;

}

del->_parent->_bf += 1;//删除左结点一定导致左边高度下降

}

else

{

if (del->_right == nullptr)

{

del->_parent->_right = del->_left;

if (del->_left != nullptr)//左右都为空时不更新

del->_left->_parent = del->_parent;

}

else

{

del->_parent->_right = del->_right;

del->_right->_parent = del->_parent;

}

del->_parent->_bf -= 1;//删除右结点一定导致右边高度下降

}

//更新平衡因子及调整

Node* cur = del;

while (cur->_parent->_parent)

{

if (cur->_parent->_bf == 1 || cur->_parent->_bf == -1)//高度没有发生变化

break;

else if (cur->_parent->_bf == 2)//右边高，需要左旋

{

if (cur->_parent->_right->_bf == -1)

RotateRL(cur->_parent);

else if (cur->_parent->_right->_bf == 1)

RotateL(cur->_parent);

else if (cur->_parent->_right->_bf == 0)//这里可能会出现subR有两个孩子的情况bf==0

{

Node* subR = cur->_parent->_right;

RotateL(cur->_parent);

subR->_bf = -1;

cur->_parent->_bf = 1;

break;

}

else

assert(false);

//前两种情况旋转之后高度依然是减少的，继续更新不退出

}

else if (cur->_parent->_bf == -2)//左边高，需要右旋

{

if (cur->_parent->_left->_bf == 1)

RotateLR(cur->_parent);

else if(cur->_parent->_left->_bf == -1)

RotateR(cur->_parent);

else if (cur->_parent->_left->_bf == 0)//subL._bf == 0

{

Node* subL = cur->_parent->_left;

RotateR(cur->_parent);

subL->_bf = 1;

cur->_parent->_bf = -1;

break;

}

//前两种情况旋转之后高度依然是减少的，继续更新不退出

}

else if (cur->_parent->_bf == 0)//高度减少了，但还平衡，继续更新

{

if (cur->_parent->_parent->_left == cur->_parent)

cur->_parent->_parent->_bf += 1;

else

cur->_parent->_parent->_bf -= 1;

cur = cur->_parent;

}

else

assert(false);

}

}

delete del;

return true;

}

呕心沥血写了一坤时的删除逻辑，有错误的地方还请指正。

若未发现错误，就请三连支持一下吧。