之前对 map / multimap / set / multiset 进行了简单的介绍，在其文档介绍中发现，这几个容器有个共同点是：其底层都是按照二叉搜索树来实现的，但是二叉搜索树有其自身的缺陷，假如往树中插入的元素有序或者接近有序，二叉搜索树就会退化成单支树，时间复杂度会退化成 O(N)，因此 map、set 等关联式容器的底层结构是对二叉树进行了平衡处理，即采用平衡树来实现。
注意：因为 map 和 set 主要是用红黑树进行封装，所以这里的 AVL 树我们主要是实现它的 插入 和 删除 和 operator[] （因为 insert 就是为了 operator[] 而存在的，还记得我们在二叉树进阶讲的吗？），所以我们这里不会去是实现 AVL 树的拷贝构造和赋值重载，这方面涉及到深拷贝，我们一并到红黑树才讲！
Ⅰ. AVL树的定义
二叉搜索树虽可以缩短查找的效率，但 如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家 G.M.Adelson-Velskii 和 E.M.Landis 在 1962 年发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过** 1( 需要对树中的结点进行调整 **)，即可降低树的高度，从而减少平均搜索长度。
一棵 AVL 树或者是空树，或者是具有以下性质的二叉搜索树：
-
左右子树都是
AVL树 -
左右子树高度之差 ( 简称 平衡因子) 的绝对值不超过
1
如果一棵二叉搜索树是高度平衡的，它就是 AVL 树。如果它有 n 个结点，其高度可保持在 ，搜索时间复杂度 O()。
Ⅱ. AVL树节点的定义
对于 AVL 树节点的定义，其实有很多个版本，各有优势，这里用的是三叉链的结构，这是为了方便后面的一些操作，但是也是有弊端的比如说在链接的时候要把三条链都考虑进去，但是三叉链的优势是利大于弊，所以这里采用三叉链！
而至于 AVL 树的一些特点，比如说调整树的高度，那么我们就得知道该节点的 平衡因子(balance factor)，所以这里我们给节点里面增加一个 bf，用于存放该节点的平衡因子。
注意：这里 平衡因子bf的值 等于：右子树高度 - 左子树高度
根据AVL树的定义，每个节点的bf值理论上只可能有三种情况：
1，0，-1。所以当bf出现其他值的时候就代表树不平衡了，需要调整了。
template <class K, class V>
struct AVLTreeNode
{
AVLTreeNode<K, V>* _left;
AVLTreeNode<K, V>* _right;
AVLTreeNode<K, V>* _parent;
pair<K, V> _kv; // _kv是一个键值对
int _bf; // 该点的平衡因子 --> balance factor
AVLTreeNode(const pair<K, V>& kv)
: _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _kv(kv)
, _bf(0)
{}
};Ⅲ. AVL树的插入Insert
一、节点的插入
AVL 树的插入和之前搜索树的插入是一样的，只不过在插入之后，我们需要做出调整，因为有可能我们插入节点后会导致二叉树的不平衡，所以我们得重新调整高度！这里就涉及到 左单旋、右单旋、左右双旋和右左双旋 四个操作。
AVL 树的插入过程可以分为两步：
-
按照二叉搜索树的方式插入新节点
-
调整节点的平衡因子
- 新增的节点如果在
parent的左边，则parent->bf-- - 新增的节点如果在
parent的右边，则parent->bf++- 如果 parent 的平衡因子为
0，说明高度是平衡的，停止更新 - 如果 parent 的平衡因子为
1或者-1，说明parent所在子树的高度变了，继续往上更新 - 如果 parent 的平衡因子为
2或者-2，说明已经出现不平衡了，需要进行旋转调整（后面会讲如何旋转）
- 如果 parent 的平衡因子为
- 新增的节点如果在
pair<Node*, bool> Insert(const pair<K, V>& kv)
{
// 若树为空则直接开辟新节点
if (_root == nullptr)
{
_root = new Node(kv);
return make_pair(_root, true);
}
// 先找到要插入的位置，用cur标记，而parent标记cur的上一个位置
Node* cur = _root;
Node* parent = _root;
while (cur != nullptr)
{
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 make_pair(cur, false);
}
}
// 接着插入节点
cur = new Node(kv);
Node* newnode = cur; // 这一步是为了后面返回值返回的
if (parent->_kv.first < kv.first)
{
parent->_right = cur;
cur->_parent = parent;
}
else
{
parent->_left = cur;
cur->_parent = parent;
}
// 调整高度
while (parent != nullptr) // 这里也可写出while(cur != _root)
{
// 1、先调节平衡因子
if (parent->_left == cur)
{
parent->_bf--;
}
else
{
parent->_bf++;
}
// 2、判断是否需要旋转
if (parent->_bf == 0)
{
break;
}
else if (parent->_bf == 1 || parent->_bf == -1)
{
// 插入前双亲的平衡因子是0，插入后双亲的平衡因为为1 或者 -1 ，说明以双亲为根的二叉树的高度增加了一层，因此需要继续向上调整
cur = parent;
parent = parent->_parent;
}
else if(parent->_bf == 2 || parent->_bf == -2)
{
// 需要调整高度
if (parent->_bf == -2)
{
if (cur->_bf == -1)
{
RotateR(parent); //右单旋
}
else if(cur->_bf == 1)
{
RotateLR(parent); //左右双旋
}
}
else if (parent->_bf == 2)
{
if (cur->_bf == 1)
{
RotateL(parent); //左单旋
}
else if (cur->_bf == -1)
{
RotateRL(parent); //右左双旋
}
}
// 注意这里的break很关键，因为我们调整了子树的平衡因子后，它的父亲以上的树其实就已经不会受影响了
break;
}
else
{
// 插入节点之前，树已经不平衡了，或者bf出错。需要检查其他逻辑
assert(false);
}
}
return make_pair(newnode, true);
}问题：这里要注意的是 Insert 的返回值为什么是 pair？
还记得我们在实现二叉搜索树的时候说到，Insert 的实现其实是为了 operator[] 而产生的，而 operator[] 需要接收到是一个键值对里面的 value，所以我们的 Insert 需要返回一个 pair，且 pair 里面第一个键值放的是迭代器，第二个值放的是 bool 值，这是为了和 STL 里面的实现保持一致！详情可查看官方文档。
二、插入的旋转
如果在一棵原本是平衡的 AVL 树中插入一个新节点，可能造成不平衡，此时必须调整树的结构，使之平衡化。根据节点插入位置的不同，AVL 树的旋转分为四种：
① 新节点插入较高左子树的左侧（左左）：右单旋
如下图，我们在 a 树下插入新节点，此时 30 节点和 60 节点的平衡因子就变了，则需要调整。
上图在插入前，AVL 树是平衡的，新节点插入到 30 的左子树（注意：此处不是左孩子）中，30 的左子树增加了一层，导致以 60 为根的二叉树不平衡，要让 60 平衡，只能将 60 左子树的高度减少一层，右子树增加一层，即将 60 的左子树往上提，这样 60 转下来，因为 60 比 30 大，只能将其放在 30 的右子树，而如果 30 有右子树，右子树根的值一定大于 30，小于 60，只能将其放在 60 的左子树，旋转完成后，更新节点的平衡因子即可。在旋转过程中，有以下几种情况需要考虑：
-
30节点的右孩子可能存在，也可能不存在 -
60节点可能是根节点，也可能是子树-
如果是根节点，旋转完成后，要更新根节点
-
如果是子树，可能是某个节点的左子树，也可能是右子树
-
-
最后记得将
30和60节点的平衡因子调为0
void RotateR(Node* parent)
{
// SubL: Parent的左孩子
// SubLR: Parent左孩子的右孩子
Node* subL = parent->_left;
Node* subLR = subL->_right;
// 先将parent的左子树连上subLR，注意要双向链接
parent->_left = subLR;
if (subLR != nullptr) // 注意要判断subLR是否为空，为空则不需要链接
subLR->_parent = parent;
// 让parent作为subL的右子树
subL->_right = parent;
Node* parent_parent = parent->_parent; // 先将parent的parent记录下来，后面链接要用到
parent->_parent = subL;
// 判断一下parent是否为二叉树的根节点
if (parent == _root)
{
_root = subL;
_root->_parent = nullptr;
}
else
{
// 如果60是子树，可能是parent_parent的左子树，也可能是右子树
if (parent_parent->_left == parent)
{
parent_parent->_left = subL;
}
else
{
parent_parent->_right = subL;
}
subL->_parent = parent_parent;
}
// 最后记得要将平衡因子置零
subL->_bf = parent->_bf = 0;
}② 新节点插入较高右子树的右侧（右右）：左单旋
实现及情况考虑可参考右单旋，与右单旋基本一致，只不过要旋转的节点不同而已！
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
// 先将parent的左子树连上subRL，注意要双向链接
parent->_right = subRL;
if (subRL != nullptr)
subRL->_parent = parent;
// 让parent作为subR的右子树
subR->_left = parent;
Node* parent_parent = parent->_parent;
parent->_parent = subR;
// 判断一下parent是否为二叉树的根节点
if (parent == _root)
{
_root = subR;
_root->_parent = nullptr;
}
else
{
if (parent_parent->_left == parent)
{
parent_parent->_left = subR;
}
else
{
parent_parent->_right = subR;
}
subR->_parent = parent_parent;
}
// 最后记得要将平衡因子置零
subR->_bf = parent->_bf = 0;
}③ 新节点插入较高左子树的右侧（左右）：先左单旋再右单旋
将双旋变成单旋后再旋转，即：先对 30 进行左单旋，然后再对 90 进行右单旋，旋转完成后再考虑平衡因子的更新。
而这里双旋后平衡因子更新的情况比较多，我们一一列举出来：
可以看出来，三种情况可以根据 60 这个节点来进行区分：
- 当
60这个节点的bf为0：旋转后该子树的节点的平衡因子都为0 - 当
60这个节点的bf为1：也就是在右子树插入了新节点，则最后subL->bf = -1，其他都为0 - 当
60这个节点的bf为-1：也就是在左子树插入了新节点，则最后parent->bf = 1，其他都为0
void RotateLR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
// 旋转之前，保存subLR的平衡因子，旋转完成之后，需要根据该平衡因子来调整其他节点的平衡因子
int bf = subLR->_bf;
RotateL(parent->_left);
RotateR(parent);
if (bf == 1)
{
subL->_bf = -1;
subLR->_bf = 0;
parent->_bf = 0;
}
else if (bf == -1)
{
subL->_bf = 0;
subLR->_bf = 0;
parent->_bf = 1;
}
else if (bf == 0)
{
subL->_bf = 0;
subLR->_bf = 0;
parent->_bf = 0;
}
else
{
assert(false);
}
}④ 新节点插入较高右子树的左侧（右左）：先右单旋再左单旋
大体与左右双旋一致，具体参考左右双旋。这里只画出其中一种情况，剩下的两种自主分析。
void RotateRL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
// 旋转之前，保存subRL的平衡因子，旋转完成之后，需要根据该平衡因子来调整其他节点的平衡因子
int bf = subRL->_bf;
RotateR(parent->_right);
RotateL(parent);
// 平衡因子的调节与左右双旋不太一样，具体自己分析
if (bf == 1)
{
parent->_bf = -1;
subRL->_bf = 0;
subR->_bf = 0;
}
else if (bf == -1)
{
parent->_bf = 0;
subRL->_bf = 0;
subR->_bf = 1;
}
else if (bf == 0)
{
parent->_bf = 0;
subRL->_bf = 0;
subR->_bf = 0;
}
else
{
assert(false);
}
}插入后旋转的总结：
假如以 parent 为根的子树不平衡，即 parent 的平衡因子为 2 或者 -2，分以下情况考虑：
-
parent的平衡因子为2，说明parent的右子树高，设parent的右子树的根为subR-
当
subR的平衡因子为1时，执行左单旋 -
当
subR的平衡因子为-1时，执行右左双旋
-
-
parent的平衡因子为-2，说明parent的左子树高，设parent的左子树的根为subL
-
当
subL的平衡因子为-1是，执行右单旋 -
当
subL的平衡因子为1时，执行左右双旋
旋转完成后，原 parent 为根的子树个高度降低，已经平衡，不需要再向上更新。
Ⅳ. AVL树的验证
AVL 树是在二叉搜索树的基础上加入了平衡性的限制，因此要验证 AVL 树，可以分两步：
-
验证其为二叉搜索树
- 如果中序遍历可得到一个有序的序列，就说明为二叉搜索树
-
验证其为平衡树
- 每个节点子树高度差的绝对值不超过
1（注意节点中如果没有平衡因子） - 节点的平衡因子是否计算正确
- 每个节点子树高度差的绝对值不超过
int Height(Node* root)
{
if (root == nullptr)
return 0;
int leftH = Height(root->_left);
int rightH = Height(root->_right);
return leftH > rightH ? leftH + 1 : rightH + 1;
}
bool IsBalanceTree(Node* root)
{
if (root == nullptr)
return true;
int leftH = Height(root->_left);
int rightH = Height(root->_right);
// 检查一下平衡因子是否正确 (右平衡因子 - 左平衡因子)
if (rightH - leftH != root->_bf)
{
cout << "平衡因子异常:" << root->_kv.first << endl;
return false;
}
if (abs(rightH - leftH) > 2)
return false;
return IsBalanceTree(root->_left) && IsBalanceTree(root->_right);
}
// 这个是调用验证AVL树的主函数
bool IsAVLTree()
{
return IsBalanceTree(_root);
}验证用例
结合上述代码按照以下的数据次序，自己动手画 AVL 树的创建过程，验证代码是否有漏洞。
常规场景1：{16, 3, 7, 11, 9, 26, 18, 14, 15}
特殊场景2：{4, 2, 6, 1, 3, 5, 15, 7, 16, 14}
Ⅴ. AVL树的删除Erase
一、节点的删除
因为 AVL 树也是二叉搜索树，可按照二叉搜索树的方式将节点删除，然后再更新平衡因子，只不过与插入不同的是，删除节点后的平衡因子更新，最差情况下一直要调整到根节点的位置。
AVL 树删除节点的过程是，先找到该节点，然后进行删除。由于删除节点的位置不同，导致删除后节点进行移动的方式不同。删除节点的位置分为以下 4 类：
-
删除叶子结点。操作：直接删除，然后依次向上调整为
AVL树。
这里叶子节点还有两种比较特殊的情况：
-
删除非叶子节点，该节点只有左孩子。操作：该节点的值替换为左孩子节点的值，然后删除左孩子节点。
-
为什么左孩子节点为叶子节点，因为删除节点前，该树是
AVL树，由AVL树的定义知，每个节点的左右子树的高度差的绝对值<=1，由于该节点只有左孩子，没有右孩子，如果左孩子还有子节点，那么将不满足每个节点的左右子树的高度差的绝对值<=1，所以左孩子节点为叶子结点。
-
-
删除非叶子节点，该节点只有右孩子。操作：该节点的值替换为右孩子节点的值，然后删除右孩子节点。
-
【右孩子节点为叶子结点，所以删除右孩子节点的情况为第1种情况。】
-
【为什么右孩子节点为叶子节点？答案和第二种情况一样】
-
-
删除非叶子节点，该节点既有左孩子，又有右孩子。操作：该节点的值替换为该节点的前驱节点（或者后继节点），然后删除前驱节点（或者后继节点）。
-
前驱结点：在中序遍历中，一个节点的前驱结点，先找到该节点的左孩子节点，再找左孩子节点的最后一个右孩子节点。向左走一步，然后向右走到头。最后一个右孩子节点即为前驱节点
-
后继节点：在中序遍历中，一个节点的后继结点，先找到该节点的右孩子节点，再找右孩子节点的最后一个左孩子节点。向右走一步，然后向左走到头。最后一个左孩子节点即为前驱节点
-
这里我们选择的是后继节点！说的简单一点就是右子树的最小节点！
总结：对于非叶子节点的删除，最终都将转化为对叶子节点的删除。
// 删除的情况：
// 1.删除的节点为叶子节点，直接删除，修改父节点的bf并从该节点的父节点向上调整
// 下面两种情况由于删除之前就是AVL树，又因为有一个子树为空，所以另一个子树（非空）一定只包含一个节点！，搞清楚这点很重要，这种节点一定是叶子节点的上一层！！！！这里虽然是删除该节点实际上删除的是他的唯一一个非空节点
// 2.删除的节点左子树为空，右子树非空： 相当于删除左子树，修改该节点的bf并向上调整
// 3.删除的节点右子树为空，左子树非空： 相当于删除右子树，修改该节点的bf并向上调整
// 4.左右子树都不为空，用替换删除法，找右子树的最小节点（最左边节点，这个节点左子树一定为空）实际上就转化成了上面三种情况
// bf调整原则：
// 1. 删左节点，父节点的bf++
// 2. 删右节点，父节点的bf--
// 3. bf为0继续向上调整，bf为1或-1停止向上调整
// 4. cur->bf为2的时候情况就与插入不同了，插入的时候调整的是插入的节点所在cur的半边子树，而删除要调整的是删除节点对面那一半进行旋转（这点很重要！！！，我在这上面卡了半天），旋转的操作与插入相同
bool Erase(const K& key)
{
// 开头检查一下是否是空树
if (_root == nullptr)
return false;
Node* cur = _root;
Node* parent = nullptr;
while (cur != nullptr)
{
if (cur->_kv.first > key)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_kv.first < key)
{
parent = cur;
cur = cur->_right;
}
else
{
// 找到了该节点，准备删除
// 1、左右都为空或者其中一个为空
if (cur->_left == nullptr || cur->_right == nullptr)
{
// 删除的节点就是根节点话，则先判断是否有左右子树然后在delete
if (_root == cur)
{
if (cur->_left == nullptr)
_root = _root->_right;
else
_root = _root->_left;
delete cur;
// 平衡因子调节，注意要加这个判断，否则当左右子树不存在的时候，_root是nullptr，修改bf会报错
if(_root != nullptr)
_root->_bf = 0;
}
else if (cur->_left == nullptr && cur->_right == nullptr) // 左右子树均为空
{
if (parent->_left == cur)
{
parent->_left = nullptr;
parent->_bf++;
}
else
{
parent->_right = nullptr;
parent->_bf--;
}
delete cur;
// 调节高度
Erase_rotate(parent);
}
else if (cur->_left == nullptr && cur->_right != nullptr) // 左为空右不为空
{
// 用右节点来代替作为删除的节点
cur->_kv = cur->_right->_kv;
delete cur->_right;
cur->_right = nullptr;
// 调节高度
cur->_bf--;
Erase_rotate(cur);
}
else if (cur->_left != nullptr && cur->_right == nullptr) // 右为空左为空
{
// 用左节点来代替作为删除的节点
cur->_kv = cur->_left->_kv;
delete cur->_left;
cur->_left = nullptr;
// 调节高度
cur->_bf++;
Erase_rotate(cur);
}
}
else // 2、左右都不为空
{
// 找到右子树中的最小值与cur节点的值进行替换
// 找右子树最小节点,也就是右子树的最左边的节点，这个节点：左子树一定为nullptr，右子树未知
Node* minRight = cur->_right;
Node* minParent = cur;
while (minRight->_left != nullptr)
{
minParent = minRight;
minRight = minRight->_left;
}
cur->_kv = minRight->_kv;
// 现在要搞清楚等效删除的是哪个节点，以及从哪个节点开始向上检查！
// 将删除节点转化为上面左右都为空或者其中一个为空的情况解决
if (cur == minParent)
{
// 相当于删除的是minRight->_right，改变minRight的bf，并从minRight节点向上检查
if (minRight->_right != nullptr)
{
minRight->_kv = minRight->_right->_kv;
delete minRight->_right;
minRight->_right = nullptr;
minRight->_bf++;
Erase_rotate(minRight);
}
// 相当于删除的是minRight节点，改变minParent的bf，并从minParent向上检查
else
{
minParent->_right = nullptr;
delete minRight;
minParent->_bf--;
Erase_rotate(minParent);
}
}
else
{
// 相当于删除的是minRight->_right，改变minRight的bf，并从minRight节点向上检查
if (minRight->_right != nullptr)
{
// 左子树为空右子树不为空
minRight->_kv = minRight->_right->_kv;
delete minRight->_right;
minRight->_right = nullptr;
minRight->_bf++;
Erase_rotate(minRight);
}
//相当于删除的是minRight，改变minParent的bf，并从minParent向上检查
else
{
// 左右子树 均为空的删除情况
minParent->_left= nullptr;
delete minRight;
minParent->_bf++;
Erase_rotate(minParent);
}
}
}
return true;
}
}
return false;
}二、删除的旋转
bf 调整原则：
- 删左节点，父节点的
bf++ - 删右节点，父节点的
bf-- bf为0继续向上调整，bf为1或-1停止向上调整（与插入正好反过来）cur->bf为2的时候情况就与插入不同了，插入的时候调整的是插入的节点所在的半边子树，而删除要调整的是删除节点对面那一半进行旋转（这点很重要！！！），也就是如果cur节点的bf为2，意味着右边高删除的节点一定在cur的左子树，接下来要调整右子树
🏗 与插入不同的是：删除左右单旋各自会出现一种新的情况，这种情况是插入中不可能发生的（也就是上面删除叶子节点的两种特殊情况）：
由于插入的时候一定是插入的那半边子树高，所以插入的时候只能在 B 的左右一个子树插入，所以 B 树的平衡因子不可能为 0，而删除就不同了删除节点影响的是另一半边子树，旋转的也是另一半边子树（上面删除的地方一定是是高度为h的那颗子树），所以这种情况就出现了，这种情况依然是按照左单旋和右单旋处理。旋转完成之后记得要调整整个树的 bf 值。
// bf调整原则：
// 1. 删左节点，父节点的bf++
// 2. 删右节点，父节点的bf--
// 3. bf为0继续向上调整，bf为1或-1停止向上调整
// 4. cur->bf为2的时候情况就与插入不同了，插入的时候调整的是插入的节点所在cur的半边子树，而删除要调整的是删除节点对面那一 半进行旋转（这点很重要！！！）
// 旋转的操作与插入相同
void Erase_rotate(Node* cur) // 删除节点的操作函数 传入的是已经修改过bf的删除节点的父节点
{
Node* prev = nullptr;
while (cur != nullptr)
{
if (cur->_bf == 1 || cur->_bf == -1)
{
break;
}
else if (cur->_bf == 0)
{
prev = cur;
cur = cur->_parent;
}
else if (cur->_bf == 2 || cur->_bf == -2)
{
if (cur->_bf == 2)
{
if (cur->_right->_bf == 0) // 这种情况是插入没有的，这里要特殊处理一下
{
RotateL(cur);
cur->_parent->_bf = -1;
cur->_bf = 1;
break; // 由于旋转完的树的bf的值为-1，所以不用继续循环
}
else if (cur->_right->_bf == 1) //左单旋
{
RotateL(cur);
// 下面这两步置零其实可以不用写，因为在左旋的实现里面已经置零了
// cur->_parent->_bf = 0;
// cur->_bf = 0;
prev = cur->_parent;
cur = prev->_parent;
continue;
}
else if (cur->_right->_bf == -1) //先来一个右单旋 再来一个左单旋
{
RotateRL(cur);
prev = cur->_parent;
cur = prev->_parent;
continue;
}
}
else if(cur->_bf == -2)
{
if (cur->_left->_bf == 0) // 这种情况是插入没有的，这里要特殊处理一下
{
RotateR(cur);
cur->_bf = -1;
cur->_parent->_bf = 1;
break;
}
else if (cur->_left->_bf == -1) //右单旋
{
RotateR(cur);
prev = cur->_parent;
cur = prev->_parent;
continue;
}
else if (cur->_left->_bf == 1) // 先来一个左单旋 再来一个右单旋
{
RotateRL(cur);
prev = cur->_parent;
cur = prev->_parent;
continue;
}
}
}
else
{
assert(false);
}
// 更新平衡因子
if (cur && cur->_left == prev)
cur->_bf++;
else if (cur && cur->_right == prev)
cur->_bf--;
}
}Ⅵ. AVL树的性能
AVL 树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过 1，这样可以保证查询时高效的时间复杂度，即 O()。但是如果要对 AVL 树做一些结构修改的操作，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。
因此：如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的(即不会改变)，可以考虑 AVL 树，但一个结构经常修改，就不太适合。
Ⅶ. AVL树的整体框架
前言中说到，我们这里不实现 AVL 树的拷贝构造以及赋值重载，但是我们这里会实现一下 operator[]，毕竟 insert 函数的出现就是为了它的！
🏗 operator[] 的实现代码：
V& operator[](const K& key)
{
pair<Node*, bool> res = Insert(make_pair(key, V()));
return res.first->_kv.second;
}测试代码：
#include "AVLTree.h"
void TestTree1()
{
AVLTree<int, int> t;
int arr[] = { 3,10,1,2,9,4,5,6,7 };
//int arr[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
//int arr[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
for (auto e : arr)
{
t.Insert(make_pair(e, 1));
}
t.Inorder();
cout << t.IsAVLTree() << endl;
t[3] *= 102;
t[1] *= 10;
t[2] *= 10;
t.Inorder();
t.Erase(3);
t.Inorder();
cout << t.IsAVLTree() << endl;
t.Erase(1);
t.Inorder();
cout << t.IsAVLTree() << endl;
t.Erase(1);
t.Inorder();
cout << t.IsAVLTree() << endl;
t.Erase(2);
t.Inorder();
cout << t.IsAVLTree() << endl;
t.Erase(4);
t.Inorder();
cout << t.IsAVLTree() << endl;
t.Erase(5);
t.Inorder();
cout << t.IsAVLTree() << endl;
t.Erase(6);
t.Inorder();
cout << t.IsAVLTree() << endl;
t.Erase(7);
t.Inorder();
cout << t.IsAVLTree() << endl;
t.Erase(8);
t.Inorder();
cout << t.IsAVLTree() << endl;
t.Erase(9);
t.Inorder();
cout << t.IsAVLTree() << endl;
t.Erase(10);
t.Inorder();
cout << t.IsAVLTree() << endl;
t.Erase(10);
t.Inorder();
cout << t.IsAVLTree() << endl;
}
int main()
{
TestTree1();
return 0;
}AVLTree.h
#pragma once
#include <iostream>
#include <string>
#include <cassert>
using namespace std;
template <class K, class V>
struct AVLTreeNode
{
AVLTreeNode<K, V>* _left;
AVLTreeNode<K, V>* _right;
AVLTreeNode<K, V>* _parent;
pair<K, V> _kv;
int _bf; //该点的平衡因子 --> balance factor
AVLTreeNode(const pair<K, V>& kv)
: _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _kv(kv)
, _bf(0)
{}
};
template <class K, class V>
class AVLTree
{
typedef AVLTreeNode<K, V> Node;
public:
AVLTree()
:_root(nullptr)
{}
V& operator[](const K& key)
{
pair<Node*, bool> res = Insert(make_pair(key, V()));
return res.first->_kv.second;
}
~AVLTree()
{
Destory(_root);
_root = nullptr;
}
pair<Node*, bool> Insert(const pair<K, V>& kv)
{
if (_root == nullptr)
{
_root = new Node(kv);
return make_pair(_root, true);
}
// 先找到该节点
Node* cur = _root;
Node* parent = _root;
while (cur != nullptr)
{
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 make_pair(cur, false);
}
}
// 接着插入节点
cur = new Node(kv);
Node* newnode = cur; // 这一步是为了后面返回值返回的
if (parent->_kv.first < kv.first)
{
parent->_right = cur;
cur->_parent = parent;
}
else
{
parent->_left = cur;
cur->_parent = parent;
}
// 1、更新平衡因子
while (parent != nullptr) // 或者while(cur != _root)
{
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)
{
// 2、调整高度
if (parent->_bf == -2)
{
if (cur->_bf == -1)
{
RotateR(parent); //右单旋
}
else if(cur->_bf == 1)
{
RotateLR(parent); //左右双旋
}
}
else if (parent->_bf == 2)
{
if (cur->_bf == 1)
{
RotateL(parent); //左单旋
}
else if (cur->_bf == -1)
{
RotateRL(parent); //右左双旋
}
}
// 注意这里的break很关键，因为我们调整了子树的平衡因子后，它的父亲其实就已经不会有影响了
break;
}
else
{
// 插入节点之前，树已经不平衡了，或者bf出错。需要检查其他逻辑
assert(false);
}
}
return make_pair(newnode, true);
}
void RotateR(Node* parent)
{
// SubL: Parent的左孩子
// SubLR: Parent左孩子的右孩子
Node* subL = parent->_left;
Node* subLR = subL->_right;
// 先将parent的左子树连上subLR，注意要双向链接
parent->_left = subLR;
if (subLR != nullptr)
subLR->_parent = parent;
// 让parent作为subL的右子树
subL->_right = parent;
Node* parent_parent = parent->_parent; // 先将parent的parent记录下来，后面链接要用到
parent->_parent = subL;
// 判断一下parent是否为二叉树的根节点
if (parent == _root)
{
_root = subL;
_root->_parent = nullptr;
}
else
{
if (parent_parent->_left == parent)
{
parent_parent->_left = subL;
}
else
{
parent_parent->_right = subL;
}
subL->_parent = parent_parent;
}
// 最后记得要将平衡因子置零
subL->_bf = parent->_bf = 0;
}
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL != nullptr)
subRL->_parent = parent;
subR->_left = parent;
Node* parent_parent = parent->_parent;
parent->_parent = subR;
if (parent == _root)
{
_root = subR;
_root->_parent = nullptr;
}
else
{
if (parent_parent->_left == parent)
{
parent_parent->_left = subR;
}
else
{
parent_parent->_right = subR;
}
subR->_parent = parent_parent;
}
// 最后记得要将平衡因子置零
subR->_bf = parent->_bf = 0;
}
void RotateLR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
// 旋转之前，保存subLR的平衡因子，旋转完成之后，需要根据该平衡因子来调整其他节点的平衡因子
int bf = subLR->_bf;
RotateL(parent->_left);
RotateR(parent);
if (bf == 1)
{
subL->_bf = -1;
subLR->_bf = 0;
parent->_bf = 0;
}
else if (bf == -1)
{
subL->_bf = 0;
subLR->_bf = 0;
parent->_bf = 1;
}
else if (bf == 0)
{
subL->_bf = 0;
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 == 1)
{
parent->_bf = -1;
subRL->_bf = 0;
subR->_bf = 0;
}
else if (bf == -1)
{
parent->_bf = 0;
subRL->_bf = 0;
subR->_bf = 1;
}
else if (bf == 0)
{
parent->_bf = 0;
subRL->_bf = 0;
subR->_bf = 0;
}
else
{
assert(false);
}
}
Node* Find(const K& key)
{
Node* cur = _root;
while (cur != nullptr)
{
if (cur->_kv.first < key)
{
cur = cur->_right;
}
else if (cur->_kv.first > key)
{
cur = cur->_left;
}
else
{
return cur;
}
}
return nullptr;
}
bool Erase(const K& key)
{
if (_root == nullptr)
return false;
Node* cur = _root;
Node* parent = nullptr;
while (cur != nullptr)
{
if (cur->_kv.first > key)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_kv.first < key)
{
parent = cur;
cur = cur->_right;
}
else
{
// 找到了该节点，准备删除
// 1、左右都为空或者其中一个为空
if (cur->_left == nullptr || cur->_right == nullptr)
{
if (_root == cur)
{
if (cur->_left == nullptr)
_root = _root->_right;
else
_root = _root->_left;
delete cur;
// 平衡因子调节
if(_root != nullptr)
_root->_bf = 0;
}
else if (cur->_left == nullptr && cur->_right == nullptr)
{
if (parent->_left == cur)
{
parent->_left = nullptr;
parent->_bf++;
}
else
{
parent->_right = nullptr;
parent->_bf--;
}
delete cur;
// 调节高度
Erase_rotate(parent);
}
else if (cur->_left == nullptr && cur->_right != nullptr)
{
cur->_kv = cur->_right->_kv;
delete cur->_right;
cur->_right = nullptr;
// 调节高度
cur->_bf--;
Erase_rotate(cur);
}
else if (cur->_left != nullptr && cur->_right == nullptr)
{
cur->_kv = cur->_left->_kv;
delete cur->_left;
cur->_left = nullptr;
// 调节高度
cur->_bf++;
Erase_rotate(cur);
}
}
else // 2、左右都不为空
{
Node* minRight = cur->_right;
Node* minParent = cur;
while (minRight->_left != nullptr)
{
minParent = minRight;
minRight = minRight->_left;
}
cur->_kv = minRight->_kv;
// 将删除节点转化为上面左右都为空或者其中一个为空的情况解决
if (cur == minParent)
{
if (minRight->_right != nullptr)
{
minRight->_kv = minRight->_right->_kv;
delete minRight->_right;
minRight->_right = nullptr;
minRight->_bf++;
Erase_rotate(minRight);
}
else
{
minParent->_right = nullptr;
delete minRight;
minParent->_bf--;
Erase_rotate(minParent);
}
}
else
{
if (minRight->_right != nullptr)
{
minRight->_kv = minRight->_right->_kv;
delete minRight->_right;
minRight->_right = nullptr;
minRight->_bf++;
Erase_rotate(minRight);
}
else
{
minParent->_left= nullptr;
delete minRight;
minParent->_bf++;
Erase_rotate(minParent);
}
}
}
return true;
}
}
return false;
}
void Erase_rotate(Node* cur)
{
Node* prev = nullptr;
while (cur != nullptr)
{
if (cur->_bf == 1 || cur->_bf == -1)
{
break;
}
else if (cur->_bf == 0)
{
prev = cur;
cur = cur->_parent;
}
else if (cur->_bf == 2 || cur->_bf == -2)
{
if (cur->_bf == 2)
{
if (cur->_right->_bf == 0) // 这种情况是插入没有的，这里要特殊处理一下
{
RotateL(cur);
cur->_parent->_bf = -1;
cur->_bf = 1;
break; // 由于旋转完的树的bf的值为-1，所以不用继续循环
}
else if (cur->_right->_bf == 1)
{
RotateL(cur);
// 下面这两步置零其实可以不用写，因为在左旋的实现里面已经置零了
// cur->_parent->_bf = 0;
// cur->_bf = 0;
prev = cur->_parent;
cur = prev->_parent;
continue;
}
else if (cur->_right->_bf == -1)
{
RotateRL(cur);
prev = cur->_parent;
cur = prev->_parent;
continue;
}
}
else if(cur->_bf == -2)
{
if (cur->_left->_bf == 0) // 这种情况是插入没有的，这里要特殊处理一下
{
RotateR(cur);
cur->_bf = -1;
cur->_parent->_bf = 1;
break;
}
else if (cur->_left->_bf == -1)
{
RotateR(cur);
prev = cur->_parent;
cur = prev->_parent;
continue;
}
else if (cur->_left->_bf == 1)
{
RotateRL(cur);
prev = cur->_parent;
cur = prev->_parent;
continue;
}
}
}
else
{
assert(false);
}
// 更新平衡因子
if (cur && cur->_left == prev)
cur->_bf++;
else if (cur && cur->_right == prev)
cur->_bf--;
}
}
bool IsAVLTree()
{
return IsBalanceTree(_root);
}
void Inorder()
{
_Inorder(_root);
cout << endl;
}
private:
void Destory(Node* root)
{
if (root == nullptr)
return;
Destory(root->_left);
Destory(root->_right);
delete root;
}
void _Inorder(Node* root)
{
if (root == nullptr)
return;
_Inorder(root->_left);
cout << root->_kv.first << ":" << root->_kv.second << endl;
_Inorder(root->_right);
}
int Height(Node* root)
{
if (root == nullptr)
return 0;
int leftH = Height(root->_left);
int rightH = Height(root->_right);
return leftH > rightH ? leftH + 1 : rightH + 1;
}
bool IsBalanceTree(Node* root)
{
if (root == nullptr)
return true;
int leftH = Height(root->_left);
int rightH = Height(root->_right);
// 检查一下平衡因子是否正确 (右平衡因子 - 左平衡因子)
if (rightH - leftH != root->_bf)
{
cout << "平衡因子异常:" << root->_kv.first << endl;
return false;
}
if (abs(rightH - leftH) > 2)
return false;
return IsBalanceTree(root->_left) && IsBalanceTree(root->_right);
}
Node* _root;
};