手写AVL树（赠源码）

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);

• 添加结点

AVL树插入结点可能会破坏树的平衡，所以需要我们在每次插入结点后进行维护平衡的操作，插入结点破坏平衡性的情况有如下四种。

• 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