| 打怪升级：第60天 |
|---|
 |
AVLTree，也就是我们所说的：自平衡二叉搜索树，AVL命名由来是两位发明者的名字的首字母，并无其他含义。
AVL树有两个重要的特点：
注：我们将左右子树的高度差称为平衡因子，简称为bf（Balance Factor）。
下面我们首先从二叉搜索树的插入开始引入AVL树的插入，以及之后的旋转操作，话不多说，大家上车。
根据二叉搜索树的性质：左子树节点的值都小于根，右子树节点的值都大于根，我们可以在插入的时候进行一下判断即可，
需要注意的是：如果出现相同的值我们不进行插入。
template<class K>
struct BSTreeNode
{
BSTreeNode(const K& key)
:_left(nullptr)
,_right(nullptr)
,_key(key)
{}
struct BSTreeNode* _left;
struct BSTreeNode* _right;
K _key;
};
bool Insert(const k& key)
{
if (_root == nullptr) // 空树 -- 插入的节点作为根
{
_root = new Node(key);
}
else
{
Node* prev = nullptr; // cur的父节点
Node* cur = _root;
while (cur) // 小放左，大放右，同不加
{
if (key < cur->_key)
{
prev = cur;
cur = cur->_left;
}
else if (key > cur->_key)
{
prev = cur;
cur = cur->_right;
}
else
{
return false;
}
}
if (key < prev->_key) // 判断插入到prev的左边还是右边
prev->_left = new Node(key);
else
prev->_right = new Node(key);
}
return true;
}
上面的操作就可以让我们实现二叉搜索树的插入，因为AVL树也是一棵二叉搜索树，他也需要符合二叉搜索树的性质，因此有了二叉搜索树的插入我们就可以很方便的写出AVL树的插入过程，
但是AVL树不仅有二叉搜索树的性质还有自己的一些特性：bf的绝对值不大于1，但是插入的过程中我们只考虑了搜索树的性质，因此在插入之后我们需要检查是否符合AVL树的特性，如果符合我们就不做修改，否则就需要进行旋转。
bf的计算我们采用右子树高度 减去 左子树高度
我们来理一理什么时候需要进行旋转：
插入节点后该节点一定是叶子结点没有左右子树，因此bf为0，
而插入节点后高度收到影响的就是它的所有祖先节点，因此我们需要从该节点开始往上检查它的祖先节点的bf；
如果插入之后该节点的祖先节点变成了1/-1， 说明该祖先节点原本是0，此时插入之后高度改变了，我们就需要继续往上更新其他祖先节点。
而如果插入之后该节点的祖先节点变成了0，说明该祖先节点之前是不平衡的（1/-1），插入之后变成了完全平衡，此时整棵树的高度并没有改变，那么我们就不需要往上更新了。
既然bf的绝对值不可以大于1，那么当插入一个新的节点后它的某个祖先节点的bf变成了±2，就说明出现了问题，我们需要进行旋转，
在正常情况下当bf变成±2时我们就要进行旋转，因此不会出现bf绝对值大于2的情况。
因为插入节点之后我们需要从该节点出发往上检查它的祖先节点，此处我们采用三叉链。
插入的操作同二叉搜索树，下面我们来将上面的分析过程通过代码实现出来：
struct AVLTreeNode
{
AVLTreeNode(const int& val)
:_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_bf(0)
,_val(val)
{}
AVLTreeNode* _left;
AVLTreeNode* _right;
AVLTreeNode* _parent; // 指向父亲
int _bf; // 平衡因子
int _val; // 数据
};
// insert中的调整操作
parent = cur->_parent;
while (parent)
{
if (cur == parent->_left) --parent->_bf;
else ++parent->_bf;
if (parent->_bf == 0) // 说明我们现在使得父亲的左右平衡了，整体h不变，结束调整
{
break;
}
else if (parent->_bf == 1 || parent->_bf == -1) // 父亲的h增加，继续向上调整
{
cur = parent;
parent = parent->_parent;
}
else if (parent->_bf == 2 || parent->_bf == -2) // 对父亲进行旋转，之后结束调整
{
// 判断如何旋转
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);
break;
}
else // 前面就出错了
{
assert(false);
}
}
旋转操作一共分为4种情况，上方是旋转操作的大框架，下面我们来对它们逐个击破。
右单旋：左子树高，将根节点向右旋转降低左子树的高度并且增加右子树的高度。
由下图我们可以看出 – 经过旋转后三个节点的bf都变为了0 – 根节点的变为了叶子结点，根节点的左子树变为了新的根并且右子树的高度+1。
那么通过上图我们是否可以尝试写出第一份代码？
void RotateR(Node* parent) // 左高，右单旋
{
Node* nodeL = parent->_left;
nodeL->_right = parent;
parent->_parent = nodeL;
_root = nodeL; // 更新根节点
nodeL->parent=nullptr;
parent->_bf = nodeL->_bf = 0;
}
好像这样就结束了，也没有多复杂嘛，甚至，异常的简单？针对上面的情况我们的确解决了，但是我们来看一看下面的情况：
此时需要旋转的是中间的部分节点，既然是中间的部分，我们就需要链接旧根节点的父节点与新根节点。
此时需要旋转的部分确实是根节点，不过他好像很特殊，新根节点左右子树都有，我们想要将旧根节点作为新根节点的右子树，就需要先保存新根节点的右子树。
上方的就是我们右旋过程过程中会遇到的所以情况，下面我们对右旋的情况进行总结并且写出完整代码。
右旋的步骤：
下图中的方块表示一颗颗子树，h为树的高度，希望朋友们可以自行尝试画一画h=0、1 、2。。。的情况，可以加深我们对右旋的理解。
void RotateR(Node* parent) // 左高，右单旋
{
Node* nodeL = parent->_left; // 旧根节点的左节点 -- 新根节点
Node* nodeLR = nodeL->_right; // 左子树的右子树
Node* nodePP = parent->_parent; // 旧根节点的父节点
parent->_left = nodeLR;
if (nodeLR != nullptr) // 左子树的右子树不为空
nodeLR->_parent = parent;
nodeL->_right = parent;
parent->_parent = nodeL;
nodeL->_parent = nodePP;
if (nodePP == nullptr) // 根
{
_root = nodeL;
}
else // 更新父节点的孩子
{
if (nodePP->_left == parent)
nodePP->_left = nodeL;
else
nodePP->_right = nodeL;
}
// 更新bf
parent->_bf = nodeL->_bf = 0;
}
动图图解:
左旋的步骤：
同右单旋基本一样，下方给出统一图形以及代码解析：
void RotateL(Node* parent) // 右高，左单旋 -- 或者说叫做右右高，左单旋
{
Node* nodeR = parent->_right;
Node* nodeRL = nodeR->_left;
Node* nodePP = parent->_parent;
parent->_right = nodeRL;
if (nodeRL) nodeRL->_parent = parent;
nodeR->_left = parent;
parent->_parent = nodeR;
if (nodePP) // 不是根节点
{
if (parent == nodePP->_left)
nodePP->_left = nodeR;
else
nodePP->_right = nodeR;
}
else
{
_root = nodeR;
}
nodeR->_parent = nodePP;
// 更改bf
parent->_bf = nodeR->_bf = 0;
}
在左单旋和右单旋的情况下，我们遇到的都是：根节点和它的孩子节点都是同一边高，如下图：
左：parent与nodeL都是左子树高
右：parent与nodeR都是右子树高
下边这种情况：
parent右子树高，nodeR左子树高，此时如果单单使用一次左旋或者右旋无法解决我们不平衡问题。
这种父亲和孩子高度差不在同一边的情况下我们可以将nodeR的方向转换一下，将nodeR右旋之后parent与nodeR的高度差就达到了统一，
此时再对根节点进行一次左旋就可以达到平衡的目的。
我们实际上会遇到的情况一共有以下三种：
只是看图的话好像看不出来点什么，那么我们看一看平衡之后 parent 与 nodeR的bf，新的根节点的bf一定为0，而parent与nodeR的bf却是不断变化的，那么为什么会有出现这三种情况？
这与nodeR的左孩子的孩子有关，它是否有孩子，以及有的是左孩子还是右孩子都会出现不一样的结果，
而单纯的左旋与右旋之后都会将parent与nodeR设置为0，因此这里需要我们进行特殊处理，
我们可以nodeR的左孩子的bf来判断parent与nodeR的bf。
具体代码如下：
void RotateRL(Node* parent) // 从下往上：左右高，先右旋再左旋
{
// 旋转
Node* nodeR = parent->_right;
Node* nodeRL = nodeR->_left;
int bf = nodeRL->_bf; // 用来判断
RotateR(nodeR); // 复用
RotateL(parent);
// 更改bf
nodeRL->_bf = 0;
if (bf == 1)
{
parent->_bf = -1;
nodeR->_bf = 0;
}
else if (bf == -1)
{
parent->_bf = 0;
nodeR->_bf = 1;
}
else if (bf == 0)
{
parent->_bf = 0;
nodeR->_bf = 0;
}
else // 走到这一步说明在插入新节点之前就出问题了
{
assert(false);
}
}
类比右左双旋。
注：小标题中的 RL指的是：nodeL的右子树高，parent的左子树高
左右双旋指的是：先左旋再右旋
void RotateLR(Node* parent) // 从下往上：右左高，先左旋再右旋
{
Node* nodeL = parent->_left;
Node* nodeLR = nodeL->_right;
int bf = nodeLR->_bf;
// 旋转
RotateL(nodeL);
RotateR(parent);
// 更改bf
nodeLR->_bf = 0;
if (bf == -1)
{
nodeL->_bf = 0;
parent->_bf = 1;
}
else if (bf == 1)
{
nodeL->_bf = -1;
parent->_bf = 0;
}
else if (bf == 0)
{
nodeL->_bf = 0;
parent->_bf = 0;
}
else
{
assert(false);
}
}
#pragma once
#include<iostream>
using namespace std;
#include<cassert>
class AVLTree
{
typedef AVLTreeNode Node;
public:
AVLTree()
:_root(nullptr)
{}
bool Insert(const int& p)
{
// 插入 -- 找好位置后需要更新bf
if (_root == nullptr)
{
_root = new Node(p);
return true;
}
Node* cur = _root;
Node* parent = nullptr;
while (cur)
{
if (cur->_val < p)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_val > p)
{
parent = cur;
cur = cur->_left;
}
else // 已经存在
return false;
}
cur = new Node(p);
if (cur->_kv.first < parent->_kv.first)
parent->_left = cur;
else
parent->_right = cur;
cur->_parent = parent;
// 开始向上调整bf，判断是否需要旋转 == 2/-2
while (parent)
{
if (cur == parent->_left) --parent->_bf;
else ++parent->_bf;
if (parent->_bf == 0) // 说明我们现在使得父亲的左右平衡了，整体h不变，结束调整
{
break;
}
else if (parent->_bf == 1 || parent->_bf == -1) // 父亲的h增加，继续向上调整
{
cur = parent;
parent = parent->_parent;
}
else if (parent->_bf == 2 || parent->_bf == -2) // 对父亲进行旋转，之后结束调整
{
// 判断如何旋转
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);
break;
}
else // 前面就出错了
{
assert(false);
}
}
return true;
}
void InOrder()
{
_InOrder(_root);
}
private:
void _InOrder(Node* root)
{
if (root == nullptr) return;
_InOrder(root->_left);
cout << root->_val << ", \t" << root->_bf << endl;
_InOrder(root->_right);
}
private:
Node* _root = nullptr;
};
有的朋友会有疑问：既然我们已经有了搜索二叉树，而且查找效率也十分不错，为什么还要专门来一个平衡二叉搜索树，这样有必要吗，
嗯~答案肯定是有的，而且，十分有，
在存储数据方面我们有了单链表与数组就已经足够了，之所以更加费事地设计二叉树这种结构并不是因为它长得更优美好看，而是想要利用它，通过对它的存储方式进行限制来达到快速查询的效果 – 二叉搜索树，二叉树在设计之初就不是为了插入和删除。
但是，实际情况下二叉搜索树的形态与插入数据的顺序有很大关系，乱序插入更有利于形成“健康的”二叉搜索树，
如果我的插入的数据是一组接近有序序列，那么得到的二叉树就是一棵“歪脖子树”，甚至是单链表：
这时对数据的查找效率接近O(N),基本上是遍历一整颗树，因此，在插入过程中我们需要对它进行调整，保证它是一棵“健康的”二叉树，
这样才可以保证查询的高效性：
旋转是为了在保持平衡树性质的前提下降低树的高度，右子树高就左旋，左子树高就右旋。
如果你还有一些疑问未得到解答，可以查看完整代码部分的旋转情况判断，这一些判断条件可以给你很好的启发，配合上自己动手画图，我相信你一定掌握它。
文章中的动图来源：AVL Tree测试