数据结构之平衡二叉树（AVL树）
一、平衡二叉树
1.1 什么是平衡二叉树
平衡二叉树（AVL树）是二叉搜索树的一种，它是一种高度平衡的二叉树，树中的每一个节点，两个子节点的高度差最多为1。
在最坏的情况下，BST树高度差可以达到n，查找操作时间复杂度也会达到O(n)，此时树是一个链式形状，如下图所示：
对这棵树而言，它和链表几乎没有差别，反而比链表多了一些内存占用。而AVL树的出现就是为了解决这种情况，在AVL树中，这些元素将会被排布成：
此时查找一个元素的时间复杂度就是O(lgn)，节省了大量的时间。
AVL树所包含的操作和BST树一样：
SEARCH：查找某个节点在树中的位置，实现和BST完全一致MINIMUM：求以指定节点为根的树中的最小元素，实现和BST完全一致MAXIMUM：求以指定节点为根的树中的最大元素，实现和BST完全一致PREDECESSOR：求指定节点的前驱节点，实现和BST完全一致SUCCESSOR：求指定节点的后继节点，实现和BST完全一致INSERT：在树中插入节点，实现在BST基础上修改DELETE：删除节点，实现在BST基础上修改
网上绝大部分AVL树的实现都是通过递归来的，为了秉持《算法导论》中的优良传统，也不打算使用递归来实现。而算法导论又没有针对AVL的章节，只在红黑树的课后习题13-3中提到了，并没有实现。除了INSERT和DELETE操作以外，其他操作都和BST树一致，下面就专门针对这两个操作对AVL树进行分析。
1.2 AVL树节点
相对BST树的节点来说，AVL树节点内部多了一个height成员，表示当前节点的高度。每当某个节点的左右子节点高度差超过1时（这个高度差被称为平衡因子，一般是右子节点的高度减去左子节点的高度），就需要对该节点进行旋转调整。
struct avl_tree_node_st {
int key;
int height; // 当前节点的高度
struct avl_tree_node_st *parent;
struct avl_tree_node_st *lchild;
struct avl_tree_node_st *rchild;
};关于初始时节点的高度为0还是为1的问题
大部分情况下，新建一个节点，会将它的高度设置为0，这比较符合主观的逻辑，因为它没有任何子节点。
这种情况下计算一个节点的高度的步骤为：
- 如果该节点是叶子节点，得到高度为0
- 如果该节点不是叶子节点，得到高度是左右子节点中高度更高的加1
这里要处理的一个特殊情况就是规则1：判断节点是否为叶节点，不是叶节点才能通过规则2计算。如果直接按照规则2来计算的话叶子节点高度是1，和预定条件相违背。
而如果初始化时，设置节点的高度为1，此时计算一个节点的高度就只有一个操作：
- 它的高度等于其左右子节点中高度更大的加1
不用判断是否为叶子节点，在程序处理中更好处理一点。而实际上，高度对我们来说不重要，重要的是平衡因子。
因此，AVL树节点的高度初始时设置为1更好一点。
二、左旋和右旋
AVL树最重要的操作就是左旋和右旋，当一个节点不平衡后，都需要通过这两个操作达到平衡：
对左旋和右旋的描述：
- 对节点y右旋：y将变成其左子节点x的右子节点，原来x的右子节点β变成y的左子节点。
- 对节点x左旋：x将变成其右子节点y的左子节点，原来的y的左子节点β变成x的右节点
两个操作是相反的，彼此旋转都可以得到对方，以下是一个左旋的例子：
左旋的代码实现：
static void _left_rotate(struct avl_tree_st *t, struct avl_tree_node_st *node) {
struct avl_tree_node_st *x, *y;
// x表示左旋节点，y表示x的右子节点
x = node;
y = x->rchild;
// 修改x节点的右子节点指向
x->rchild = y->lchild;
if (y->lchild)
y->lchild->parent = x;
// 修改父节点使其子节点指向新的x节点
y->parent = x->parent;
if (x->parent == NULL)
t->root = y;
else if (x->parent->lchild == x)
x->parent->lchild = y;
else
x->parent->rchild = y;
// 重新设置x和y的关系
y->lchild = x;
x->parent = y;
// 修改旋转后节点的高度
x->height = NEW_HEIGHT(x);
y->height = NEW_HEIGHT(y);
}右旋和左旋基本一致，只是指针方向相反了。
三、二叉树操作
3.1 计算节点高度
获得一个节点的高度是O(1)的，因为节点内部已经有一个height成员，直接拿就行了。
static inline int _node_height(struct avl_tree_node_st *node) {
if (node == NULL)
return 0;
return node->height;
}而当一个节点更新之后，从这个节点往上的根节点高度都有可能更新，需要重新设置高度，此时更新的操作就是比较左右子节点的高度，在更高的基础上加1，C语言中可以直接使用宏定义完成：
#define NEW_HEIGHT(node) \
max(_node_height(node->rchild), _node_height(node->lchild)) + 1计算某个节点的平衡因子:
static inline int _get_balance(struct avl_tree_node_st *node) {
if (node == NULL)
return 0;
return _node_height(node->rchild) - _node_height(node->lchild);
}3.2 增加节点
增加节点的前置操作和BST一致，给节点找到一个合适的位置先插入。然后再判断其是否满足平衡的条件，如果不满足，对它进行调整。增加节点有会有下面四种不平衡的情况。
3.2.1 LL型
下面的树中插入元素5导致树失衡，此时元素30的平衡因子为-2：
这种情况属于LL型不平衡状态，只要对不平衡的节点30执行右旋操作即可解决不平衡。
3.3.2 LR型
下面的树中插入元素15，此时元素30失衡，平衡因子为-2：
这种情况属于LR型不平衡状态，要先对插入元素的父节点10进行左旋，转换成LL型再对30右旋解决平衡。
3.3.3 RR型
下面的树中插入元素55，元素30失衡，平衡因子为2：
这种情况属于RR型不平衡状态，对30执行左旋即可恢复平衡。
3.3.4 RL型
在下面的树中，插入45导致30失衡，平衡因子为2：
这种情况属于RL型不平衡状态，先对50右旋，转换成RR型再对30左旋，恢复平衡。
3.3.5 插入操作实现
插入操作和BST的插入操作一模一样，只是在插入完成后，新增了一步对节点的平衡操作。
void avl_tree_insert(struct avl_tree_st *t, struct avl_tree_node_st *node) {
struct avl_tree_node_st *x, *y;
x = t->root;
y = x;
while (x != NULL) {
y = x;
if (node->key < x->key)
x = x->lchild;
else
x = x->rchild;
}
node->parent = y;
if (y == NULL)
t->root = node;
else if (node->key < y->key)
y->lchild = node;
else
y->rchild = node;
// 平衡节点
if (y != NULL)
avl_tree_insert_balance(t, node);
}3.3.6 插入平衡
上面说过：插入节点后，有可能导致其父节点甚至祖父节点的高度变化。因此，平衡节点时，要从新增节点的父节点开始，一直到根节点，重新更新路径上每个节点的高度并计算平衡因子，一旦平衡因子不符合条件，则按照上面的四种情况旋转。
void avl_tree_insert_balance(struct avl_tree_st *t, struct avl_tree_node_st *node) {
struct avl_tree_node_st *x, *y;
// is_modify用来表示是否被旋转过了，如果旋转过了，旋转操作里面已经更新了高度，无需再更新高度
int height, balance, is_modify;
// x是新增节点
x = node;
// y是新增节点的父节点，从父节点开始，重新更新节点高度
y = node->parent;
while (y) {
is_modify = 0;
balance = _get_balance(y);
if (balance > 1) {
// 右子树高度高于左子树高度
x = y->rchild;
if (x->key < node->key) {
// RR
_left_rotate(t, y);
} else {
// RL
_right_rotate(t, x);
_left_rotate(t, y);
}
is_modify = 1;
}
if (balance < -1) {
// 左子树高度高于右子树高度
x = y->lchild;
if (x->key > node->key) {
// LL
_right_rotate(t, y);
} else {
// LR
_left_rotate(t, x);
_right_rotate(t, y);
}
is_modify = 1;
}
if (is_modify == 0) {
// 没有执行旋转，判断高度是否有改变
height = NEW_HEIGHT(y);
if (height != y->height)
y->height = height;
else
break; // 如果节点高度没有改变的话，也不会再影响父节点的高度，直接跳出循环
}
y = y->parent;
}
}3.3 删除节点
删除节点的操作比插入操作要复杂，同样也是先利用BST中的删除操作，执行元素删除。然后再对删除后的节点进行平衡操作。删除一个元素也是四种失衡场景，也是LL/LR/RR/RL，恢复平衡的方式和增加一致：
3.3.1 LL型
3.3.2 LR型
3.3.3 RR型
3.3.4 RL型
3.3.5 如何确认是哪种类型的旋转
删除节点失衡后，对失衡节点的旋转和调整和新增节点一模一样。
但是和新增节点不同，新增节点通过判断父节点的高度和平衡因子很容易就能分辨出旋转类型。删除节点后，当发现失衡时当前节点已经是失衡节点了，并不能直接确定属于哪种失衡。
处理办法：假设失衡节点是z，令y是z的子节点中高度更高的一个，令x是y的子节点中高度更高的一个，例如：
通过比较三者的key值就可以确定旋转的类型，此处y.key > z.key，属于R型，而x.key > y.key，也是R型。两者结合起来就是RR型，元素30应该执行左旋。
特殊情况
当z失衡时，左右子节点的高度必定不同。但是y的两个子节点高度有可能相同，这样就会产生两组特殊情况：
此时y的左右节点高度都是一致的，而实际上这种情况属于LL型，应该对30右旋。
相反的，下面这种情况应该属于RR型，要对30左旋：
3.3.6 删除节点后如何更新高度
增加节点后，从增加节点的父节点开始更新高度。但是删除和新增不同，删除都是通过叶子节点替代的方式来处理的，直接从删除节点的父节点开始更新高度不准确。此时可以分为以下几种情形：
删除节点只有一个节点
使用子节点L替换父节点后，L的高度不会增加，但是原来z的父节点高度减少了，要从z的父节点开始更新高度。
删除节点有两个节点且后继节点是删除节点的右儿子
在BST删除一个节点z时，如果节点有两个儿子，那么就要在右子树中找到最小的元素y替换被删除元素的位置。这个最小的元素y有两种情况：y是z的右儿子和y不是z的右儿子
当y是z的右儿子时：
y替代z后，y和x的高度都不会变化，同样只要从z的父节点开始更新高度就行了。
但是当y不是z的右儿子时，删除节点z后，x的高度不会变化，从x的新父亲r开始的节点就有可能发生变化，例如下图中的r的高度就减少了1：
此时要从y的原始父节点开始更新高度。并且还要注意的是：被删除节点z的父节点的高度也变化了，修改r的高度之后还要继续向上修改其祖先节点的高度。
3.3.7 删除代码
AVL删除和BST类似，只是多了一个x记录删除后需要开始更新高度的起始节点。
void avl_tree_delete(struct avl_tree_st *t, struct avl_tree_node_st *node) {
struct avl_tree_node_st *x, *y;
// x记录节点删除后需要开始更新高度的起始节点
x = node;
// y是实际要进行替换删除的节点
y = node->parent;
if (node->lchild == NULL || node->rchild == NULL) {
y = node->lchild ? node->lchild : node->rchild;
_transplant(t, node, y);
// 只有一个子节点，需要更新高度的节点是被删除节点的父节点
x = node->parent;
} else {
y = tree_minimum(node->rchild);
x = y;
if (y != node->rchild) {
// 不是右子节点，需要更新高度的节点是y的父节点r
x = y->parent;
_transplant(t, y, y->rchild);
y->rchild = node->rchild;
y->rchild->parent = y;
}
_transplant(t, node, y);
y->lchild = node->lchild;
y->lchild->parent = y;
}
// 删除完成之后，修改各节点高度，调整平衡
if (x != NULL)
avl_tree_delete_balance(t, x);
}3.3.8 更新节点高度和平衡
根据章节3.3.1-3.3.5可以得到删除节点后的平衡处理代码：
void avl_tree_delete_balance(struct avl_tree_st *t, struct avl_tree_node_st *node) {
struct avl_tree_node_st *x, *y, *z;
int height, balance, is_modify;
// z是被删除节点后需要开始更新高度的起始节点
// z失衡后，y是z的子节点中高度最高的，x是y的子节点中高度较高的
z = node;
while (z) {
is_modify = 0;
balance = _get_balance(z);
if (balance > 1) {
// R型
y = _node_height(z->rchild) > _node_height(z->lchild) ? z->rchild : z->lchild;
// 注意>=符号，不是>号
x = _node_height(y->rchild) >= _node_height(y->lchild) ? y->rchild : y->lchild;
if (x->key > y->key) {
// RR
_left_rotate(t, z);
} else {
// RL
_right_rotate(t, y);
_left_rotate(t, z);
}
is_modify = 1;
}
if (balance < -1) {
y = _node_height(z->rchild) > _node_height(z->lchild) ? z->rchild : z->lchild;
x = _node_height(y->rchild) > _node_height(y->lchild) ? y->rchild : y->lchild;
if (x->key < node->key) {
// LL
_right_rotate(t, z);
} else {
// LR
_left_rotate(t, y);
_right_rotate(t, z);
}
is_modify = 1;
}
if (is_modify == 0) {
height = NEW_HEIGHT(z);
z->height = height;
}
z = z->parent;
}
}四、关于节点增加或删除后更新祖先节点高度的终止条件
当插入或者删除节点的时候，会引起其祖先节点的高度修改，从而产生不平衡。因此，每次增加或者修改元素之后，需要从该节点的父节点开始，在去往根节点的路径上，逐个对每个节点的高度更新。
由于树的高度是左右子节点的高度决定的，那么可以得到一个结论：如果左右子节点的高度没有变化的话，其祖先节点的高度一定不会变化，其平衡因子也不会变化。因此，对于增加节点而言，如果在到根路径上的某个节点高度没有变化的话，就无需再继续向上更新了。例如：
增加25和35元素并没有引起其父节点高度的变化，因此其祖父节点的高度也不会变化，在更新完其父节点的高度后就可以终止循环了。
在增加和删除操作中，都有一个is_modify变量来记录该节点是否失衡被旋转了。如果这个字段的值是0，表示该节点没有失衡，没有执行旋转操作，需要更新该节点的高度。如果这个字段是1，表示节点被旋转了，旋转之后的节点高度已经被重新赋值了，无需再次修改。这也就是为什么把计算平衡因子放在计算节点高度之后了，避免重复更新高度。
而height的作用就是判断节点高度是否变化了，如果没有变化，根据上面的出的结论，就无需继续遍历祖先节点了，祖先节点的高度一定不会变化，跳出循环即可。
