【C++篇】平衡二叉搜索树（上篇）：AVL树详解
【C++篇】平衡二叉搜索树（上篇）：AVL树详解
前言
过去介绍二叉搜索树时，我们发现其存在缺陷：极端情况下（类链表结构），查找的时间复杂度退化到了
。因此map、set等关联式容器的底层结构是对二叉树进行了平衡处理，即采用平衡树来实现。
常见的平衡树有AVL树（本文内容） 和 红黑树（下篇内容）。
一、AVL树概念
两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了AVL树（以两位科学家的名字命名）。
AVL树是如何做到平衡的呢？ AVL树规则：
- 每个节点的左右子树都是AVL树
- 左右子树的高度差的绝对值不超过
1
上图中每个节点上方的数字就是平衡因子
当然，也可以不用平衡因子来控制，只是会更复杂，不建议。
二、AVL树节点和类的定义
template<class K， class V>
struct AVLTreeNode
{
AVLTreeNode(const pair<K, V>& kv)
: _pLeft(nullptr)
, _pRight(nullptr)
, _pParent(nullptr)
, _kv(kv)
, _bf(0)
{}
AVLTreeNode<T>* _Left; // 该节点的左孩子
AVLTreeNode<T>* _pRight; // 该节点的右孩子
AVLTreeNode<T>* _pParent; // 该节点的父亲
pair<K, V> _kv; // 该节点的键值
int _bf; // 该节点的平衡因子
};
template<class K， class V>
class AVLTree
{
typedef AVLTreeNode<K, V> Node;
public:
//……
private:
Node* _root = nullptr;
};三、AVL树的插入
AVL树就是在二叉搜索树的基础上引入了平衡因子，因此AVL树也可以看成是二叉搜索树。那么AVL树的插入过程可以分为两步：
- 按照二叉搜索树的方式插入新节点
- 调整节点的平衡因子
第一步过去有讲解，本文不过多赘述了，主要步骤为：1.查找需要插入的位置 2.插入
// 在AVL树中插入值为val的节点
bool Insert(const pair<K, V>& kv)
{
if (_root == nullptr)
{
_root = new Node(kv);
return true;
}
Node* cur = _root;
Node* parent = nullptr;
while (cur)
{
if (cur->_kv.first < kv.first)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_kv.first > kv.first)
{
parent = cur;
cur = cur->_left;
}
else
{
return false;
}
}
cur = new Node(kv);
//新增在左
if (parent->_kv.first > kv.first)
{
parent->_left = cur;
}
else//新增在右
{
parent->_right = cur;
}
cur->_parent = parent;
//更新平衡因子，若平衡因子异常，调节其至平衡
……
}第二步调节平衡因子：
- 新增节点在parent的左，左子树高度加一，parent的平衡因子减一（
by--） - 新增节点在parent的右，右子树高度加一，parent的平衡因子加一（
by++）
不难发现：插入新节点，只可能会影响其祖先节点的bf。 因此，可以确定节点bf更新方向：沿着其到root的祖先路径，往上更新。
- 更新后，parent的bf == 0，说明parent所在的子树高度不变，不会影响祖先的bf，无需继续沿着到root的祖先路径往上更新，插入结束。
- 更新后，parent的bf == 1 or -1，说明parent所在的子树高度变化，会影响祖先的bf，需要继续沿着到root的祖先路径往上更新，直到parent的bf == 0或更新到根节点，插入结束
- 更新后，parent的bf == 2 or -2，说明parent所在的子树高度变化且不平衡了，需要对parent所在子树进行旋转，使其平衡，插入结束。
代码：
//更新平衡因子，若平衡因子异常，调节其至平衡
while (parent)
{
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 = cur->_parent;
}
else if (parent->_bf == 2 || parent->_bf == -2)
{
//旋转……
break;
}
else
{
assert(false);
}
}
return true;四、AVL树的旋转（牢记）
旋转的时候需要注意的问题：
- 保持该树还是一颗搜索树
- 不破坏其内部结构（善后工作要做好）
- 变成平衡树且降低了这个子树的高度
根据节点插入位置的不同，AVL树的旋转分为四种：
1. 左旋转
当新节点插入较高右子树的右侧—右右：就用左旋
左旋的核心操作步骤：
- cur的左子树给parent的右子树
- parent作为cur的左子树
核心操作代码：
parent->_right = cur->_left;
cur->_left = parent;可以看到：左旋后，cur和parent的bf都为0。
代码：
// 左单旋
void RotateL(Node* parent)
{
Node* cur = parent->_right;
Node* curleft = cur->_left;
parent->_right = curleft;
cur->_left = parent;
//更新_parent
if (curleft)//curleft可能为空，避免访问空节点
curleft->_parent = parent;
//存储parent的父节点，后续需要区分parent是否为root节点
Node* ppnode = parent->_parent;
parent->_parent = cur;
if (parent == _root)
{
_root = cur;
cur->_parent = nullptr;
}
else
{
if (ppnode->_left == parent)
{
ppnode->_left = cur;
}
else
{
ppnode->_right = cur;
}
cur->_parent = ppnode;
}
//更新bf
cur->_bf = parent->_bf = 0;
}2. 右旋转
当新节点插入较高左子树的左侧—左左：就用右旋
右旋转和左旋转雷同，左右反一下就好了：
右旋的核心操作步骤：
- cur的右子树给parent的左子树
- parent作为cur的右子树
核心操作代码：
parent->_left= cur->_right;
cur->_right= parent;右旋后，cur和parent的bf也都为0。
代码：
// 右单旋
void RotateR(Node* parent)
{
Node* cur = parent->_left;
Node* curright = cur->_right;
parent->_left = curright;
cur->_right = parent;
//更新_parent
if (curright)
curright->_parent = parent;
Node* ppnode = parent->_parent;
parent->_parent = cur;
if (parent == _root)
{
_root = cur;
cur->_parent = nullptr;
}
else
{
if (ppnode->_left == parent)
{
ppnode->_left = cur;
}
else
{
ppnode->_right = cur;
}
cur->_parent = ppnode;
}
//更新bf
cur->_bf = parent->_bf = 0;
}3. 右左双旋
仔细观察前文的单旋，发现它们似乎都是“直线”情况，如下图：
但当遇上“折线”情况的时候，单旋就无法解决问题了，如下图：
此时，需要靠双旋来出手了。
新节点插入较高右子树的左侧—右左：先右单旋再左单旋
右左双旋的核心操作步骤：
- 先对cur进行右单旋
- 再对parent进行左单旋
核心操作代码：
RotateR(cur);
RotateL(parent);旋转完成后再考虑平衡因子的更新。
平衡因子分析：
- 当h == 0时，60自身为新增节点：
旋转结果的平衡因子皆为0.
- 当h > 0时，分两种情况，两种情况旋转结果的bf不同：
- 在c中新增：
- 在b中新增：
对于bf，关键点在于旋转前60的bf：
- 如果60的
bf == 1，则parent的bf = -1，其他的bf都为0； - 如果60的
bf == -1，则cur的bf = 1，其他的bf都为0； - 如果60的
bf == 0，bf皆为0；
代码：
void RotateRL(Node* parent)
{
Node* cur = parent->_right;
Node* curleft = cur->_left;
int bf = curleft->_bf;
RotateR(cur);
RotateL(parent);
//控制bf
curleft->_bf = 0;
if (bf == 0)
{
cur->_bf = parent->_bf = 0;
}
else if (bf == 1)
{
cur->_bf = 0;
parent->_bf = -1;
}
else if (bf == -1)
{
cur->_bf = 1;
parent->_bf = 0;
}
else
{
assert(false);
}
}4. 左右双旋
新节点插入较高左子树的右侧—左右：先左单旋再右单旋
右左双旋的核心操作步骤：
- 先对cur进行左单旋
- 再对parent进行右单旋
核心操作代码：
RotateL(cur);
RotateR(parent);旋转完成后再考虑平衡因子的更新。
平衡因子分析： 与右左双旋雷同，笔者不再赘述，留给读者独立分析。
分析结果：
对于bf，关键点在于旋转前60的bf：
- 如果60的
bf == 1，则cur的bf = -1，其他的bf都为0； - 如果60的
bf == -1，则parent的bf = 1，其他的bf都为0； - 如果60的
bf == 0，bf皆为0；
代码：
// 左右双旋
void RotateLR(Node* parent)
{
Node* cur = parent->_left;
Node* curright = cur->_right;
int bf = curright->_bf;
RotateL(cur);
RotateR(parent);
//控制bf
curright->_bf = 0;
if (bf == 0)
{
cur->_bf = parent->_bf = 0;
}
else if (bf == 1)
{
cur->_bf = -1;
parent->_bf = 0;
}
else if (bf == -1)
{
cur->_bf = 0;
parent->_bf = 1;
}
else
{
assert(false);
}
}实现了四大旋转后，我们来补充插入的旋转代码：
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)
{
RotateRL(parent);
}
else if (parent->_bf == -2 && cur->_bf == 1)
{
RotateLR(parent);
}五、AVL树的验证
AVL树是在二叉搜索树的基础上加入了平衡性的限制，因此要验证AVL树，可以分两步： 1. 验证其为二叉搜索树 如果中序遍历可得到一个有序的序列，就说明为二叉搜索树 2. 验证其为平衡树 每个节点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子)节点的平衡因子是否计算正确
代码：
bool _IsAVLTree(Node* root)
{
if (root == nullptr)
{
return true;
}
//记录高度
int LeftHeight = _Height(root->_left);
int RightHeight = _Height(root->_right);
if (root->_bf != RightHeight - LeftHeight)
{
cout << "平衡因子异常" << root->_kv.first << "->" << root->_bf << endl;
}
return abs(RightHeight - LeftHeight) < 2
&& _IsAVLTree(root->_left)
&& _IsAVLTree(root->_right);
}
//计算高度
size_t _Height(Node* root)
{
if (root == nullptr)
return 0;
size_t LeftHeight = _Height(root->_left);
size_t RightHeight = _Height(root->_right);
return LeftHeight > RightHeight ? LeftHeight + 1 : RightHeight + 1;
}六、AVL树的优劣
AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这样可以保证查询时高效的时间复杂度。
但是如果要对AVL树做一些结构修改的操作，性能非常低下。 比如：插入时要维护其绝对平衡旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。
因此：如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的(即不会改变)，可以考虑AVL树，但一个结构经常修改，就不太合适了。
完~ 下篇预告：红黑树详解
腾讯云开发者
