01
—
认识AVL树
二叉平衡搜索树又称AVL树，且具有以下性质：它是一颗空树或它的两个左右子树高度相差绝对值不超过1，并且左右子树是一颗平衡二叉搜索树。
平衡因子：某结点的左子树和右子树高度差即为该结点的平衡因子，一个平衡二叉树平衡因子只能是0，-1和1，平衡因子绝对值大于1则说明该二叉树是不平衡的。
02—
AVL树原理和实现
为了便于计算平衡因子，我们为每个结点赋予height属性，表示结点的高度。于是AVL树结点定义和AVL树操作函数声明如下：typedef struct tree_node{
struct tree_node *left;
struct tree_node *right;
int height;
int data;
}tree_node_t;
extern tree_node_t *new_avl_tree_node(int data);
extern void free_avl_tree_node(tree_node_t *node);
extern void avl_tree_height_update(tree_node_t *root);
extern void avl_tree_insert_node(tree_node_t **root, int data);
extern void avl_tree_delete_node(tree_node_t **root, int data);
extern void avl_tree_print(tree_node_t *root);添加结点
- LL
LL的意思是新结点插入左子树（L）的左孩子（L），这种情况需要右旋，为了方便理解，我们作了下图，后续我们也会采用类似的描述。
结点z是新插入结点，此时x结点的左孩子和右孩子高度差绝对值大于1，破坏了平衡，需要进行右旋操作维护平衡。对应的C代码实现如下：
/**
* @brief get_balance_factor
* @param node
* @return
*/
int get_balance_factor(tree_node_t *node){
if(node == NULL){
return 0;
}
int left_factor = 0;
int right_factor = 0;
if(node->left != NULL){
left_factor = node->left->height;
}
if(node->right != NULL){
right_factor = node->right->height;
}
return left_factor - right_factor;
}
/**
* @brief avl_tree_right_rotate
* @param x
* @return
*/
tree_node_t *avl_tree_right_rotate(tree_node_t *x){
tree_node_t *y = x->left;
tree_node_t *t2 = y->right;
y->right = x;
x->left = t2;
//右旋后必须先求出x的高度再求出y的高度
int max_height = get_max_height(x);
x->height = max_height + 1;
max_height = get_max_height(y);
y->height = max_height + 1;
return y;
}get_balance_factor获取平衡因子，无非就是计算左孩子和右孩子高度差。从图中我们可以看出进行右旋后结点x和y的高度发生了变化，因此每进行一次右旋要调整结点x和y的高度，而且结点y的高度可能会受到结点x高度的影响，因此必须先调整x的高度，再调整y的高度。get_max_height则是获取某个结点的孩子的最大高度，再加1则是某结点的最终高度。- RR
RR的意思是新结点插入右子树（R）的右孩子（R），这种情况需要左旋，如下图所示。
z是新插入结点，此时x结点的左右孩子高度差绝对值大于1，破坏了平衡，需要左旋操作维护平衡。对应C代码实现如下：
/**
* @brief avl_tree_left_rotate
* @param x
* @return
*/
tree_node_t *avl_tree_left_rotate(tree_node_t *x){
tree_node_t *y = x->right;
tree_node_t *t2 = y->left;
y->left = x;
x->right = t2;
//右旋后必须先求出x的高度再求出y的高度
int max_height = get_max_height(x);
x->height = max_height + 1;
max_height = get_max_height(y);
y->height = max_height + 1;
return y;
}从图中我们可以看出，进行左旋操作后，结点x和y的高度发生了变化，因此每进行一次左旋要调整结点x和y的高度，而且结点y的高度可能会受到结点x高度的影响，因此必须先调整x的高度，再调整y的高度。
- RL
RL的意思是新结点插入右子树（R）的左孩子（L），这种情况下需要先右旋再左旋，如下图所示。
z是新插入结点，x的左右孩子高度差绝对值大于1，但是这里需要进行2次旋转才能维护平衡，判断是否满足这种情况的条件如下：
1、左子树和右子树高度差小于-1。
2、右子树的左孩子高度大于右孩子的高度。
- LR
LR的意思是新结点插入左子树（L）的右孩子（R），这种情况下需要先左旋再右旋，如下图所示。
z是新插入结点，x的左右孩子高度差绝对值大于1，但是这里需要进行2次旋转才能维护平衡，判断是否满足这种情况的条件如下：
1、左子树和右子树高度差大于1。
2、左子树的右孩子高度大于左孩子的高度。
综上考虑四种结点插入情况后，C代码实现如下：
/**
* @brief avl_tree_balance_adjust
* @param root_node
* @return
*/
tree_node_t *avl_tree_balance_adjust(tree_node_t *root_node){
if(root_node == NULL){
return NULL;
}
avl_tree_height_update(root_node); //更新结点高度
int balance_factor = get_balance_factor(root_node);
if(balance_factor > 1 && get_balance_factor(root_node->left) > 0){
//左子树-右子树高度差大于1且root_node左孩子的平衡因子大于0，则是LL场景，需要右旋
printf("need ll\n");
return avl_tree_right_rotate(root_node);
} else if(balance_factor > 1 && get_balance_factor(root_node->left) < 0){
//左子树-右子树高度差大于1且root_node左孩子的平衡影子小于0，则是LR场景，需要先左旋再右旋
printf("need lr\n");
root_node->left = avl_tree_left_rotate(root_node->left);
return avl_tree_right_rotate(root_node);
}else if(balance_factor < -1 && get_balance_factor(root_node->right) < 0){
//左子树-右子树高度差小于-1且root_node右孩子平衡因子大于0，则是RR场景，需要左旋
printf("need rr\n");
return avl_tree_left_rotate(root_node);
}else if(balance_factor < -1 && get_balance_factor(root_node->right) > 0){
//左子树-右子树高度差小于-1且root_node右孩子平衡因子小于0，则是RL场景，需要先右旋再左旋
printf("need rl\n");
root_node->right = avl_tree_right_rotate(root_node->right);
return avl_tree_left_rotate(root_node);
}
return root_node;
}
/**
* @brief sub_tree_add_node
* @param root_node
* @param new_node
* @return
*/
tree_node_t *sub_tree_add_node(tree_node_t *root_node, int data){
if(root_node == NULL){
return new_avl_tree_node(data);
}
//找到新结点适合插入的位置
if(data < root_node->data){
root_node->left = sub_tree_add_node(root_node->left, data);
}else{
root_node->right = sub_tree_add_node(root_node->right, data);
}
//printf("insert node: %d\n", data);
//printf("current node: %d, height = %d\n", root_node->data, root_node->height);
return avl_tree_balance_adjust(root_node); //调节avl树
}
/**
* @brief avl_tree_insert_node
* @param tree root
* @param data
*/
void avl_tree_insert_node(tree_node_t **root, int data){
if(root == NULL){
return;
}
tree_node_t *tree_root = *root;
tree_root = sub_tree_add_node(tree_root, data); //将新结点放入某个合适位置，后面要调整平衡性
*root = tree_root;
}删除结点
AVL树删除结点和二叉搜索树删除结点的不同点在于删除结点后需要维护平衡。
/**
* @brief sub_tree_delete_node
* @param root_node
* @param data
* @return
*/
tree_node_t *sub_tree_delete_node(tree_node_t *root_node, int data){
if(root_node == NULL){
return NULL;
}
tree_node_t *node = NULL;
if(data < root_node->data){
root_node->left = sub_tree_delete_node(root_node->left, data);
}else if(data > root_node->data){
root_node->right = sub_tree_delete_node(root_node->right, data);
}else{
//找到要删除的结点
if(root_node->left == NULL && root_node->right != NULL){
//左子树为空，则用右子树结点代替被删除结点
tree_node_t *right = root_node->right;
root_node->right = NULL;
free_avl_tree_node(root_node);
return right;
}else if(root_node->right == NULL && root_node->left != NULL){
//右子树为空，则用左子树结点代替被删除结点
tree_node_t *left = root_node->left;
root_node->left = NULL;
free_avl_tree_node(root_node);
return left;
}else if(root_node->right == NULL && root_node->left == NULL){
free_avl_tree_node(root_node);
return NULL;
}
else{
//左右子树不为空的情况
tree_node_t *temp_node = NULL;
if(get_balance_factor(root_node) >= 0){
//左子树高度大于等于右子树高度，采用左子树结点代替原结点
node = root_node->left;
temp_node = node->right;
node->right = root_node->right;
free_avl_tree_node(root_node);
return sub_tree_add_node(node, temp_node);
}else{
//右子树高度大于左子树，采用右子树结点代替原结点
node = root_node->right;
temp_node = node->left;
node->left = root_node->left;
return sub_tree_add_node(node, temp_node);
}
}
}
return root_node;
}
/**
* @brief avl_tree_balance_adjust_all
* @param node
* @return
*/
tree_node_t *avl_tree_balance_adjust_all(tree_node_t *node){
if(node == NULL){
return NULL;
}
avl_tree_balance_adjust_all(node->left);
avl_tree_balance_adjust_all(node->right);
return avl_tree_balance_adjust(node);
}
/**
* @brief avl_tree_delete_node
* @param root
* @param data
*/
void avl_tree_delete_node(tree_node_t **root, int data){
if(root == NULL){
return;
}
if(*root == NULL){
return;
}
*root = sub_tree_delete_node(*root, data);
tree_node_t *root_node = *root;
*root = avl_tree_balance_adjust_all(root_node);
}执行删除结点操作后平衡性被破坏后，不能仅仅在删除的地方进行调整，而是遍历整棵二叉树进行调整，平衡性的调整必须从下到上进行，回想下二叉树遍历的方式我们知道，只有后续遍历能满足这个条件，因此每进行一次删除，就需要后序遍历平衡二叉树维护平衡性。
- 结点输出
AVL树本质上还是一颗二叉树，所以二叉树的遍历方式对于AVL树都适用，现在我们用先序遍历AVL树所有结点。对应C代码实现如下：
/**
* @brief avl_tree_print
* @param root
*/
void avl_tree_print(tree_node_t *root){
if(root == NULL){
return;
}
printf("%d, ", root->data);
avl_tree_print(root->left);
avl_tree_print(root->right);
}03—
结果验证
为了验证代码的正确性，取一组数据{7, 2, 3, 5, 1, 78, 9}，这组数据构成AVL树如下图所示：
采用先序遍历输出如下：3，2，1，7，5，78，9，现在删除结点2后二叉平衡树变为如下图所示：
采用先序遍历输出如下：7、3、1、5、78、9。现在我们写一个小程序验证是否正确。
#include <stdio.h>
#include "avl_tree.h"
int main()
{
int arr[7] = {7, 2, 3, 5, 1, 78, 9};
int i = 0;
tree_node_t *avl_tree = NULL;
for(i = 0; i < 7; i++){
avl_tree_insert_node(&avl_tree, arr[i]);
}
avl_tree_print(avl_tree);
printf("\n");
printf("删除结点2\n");
avl_tree_delete_node(&avl_tree, 2);
avl_tree_print(avl_tree);
printf("\n");
printf("hello avl\n");
return 0;
}编译运行输出如下：need lr
3，2，1，7，5，78，9，
删除结点2
need rr
7，3，1，5，78，9，
hello avl输出结果完全正确！
往期推荐