01

—

認識AVL樹

二叉平衡搜索樹又稱AVL樹，且具有以下性質(zhì)：它是一顆空樹或它的兩個左右子樹高度相差絕對值不超過1，并且左右子樹是一顆平衡二叉搜索樹。

平衡因子：某結(jié)點的左子樹和右子樹高度差即為該結(jié)點的平衡因子，一個平衡二叉樹平衡因子只能是0，-1和1，平衡因子絕對值大于1則說明該二叉樹是不平衡的。

02—

AVL樹原理和實現(xiàn)

為了便于計算平衡因子，我們?yōu)槊總€結(jié)點賦予height屬性，表示結(jié)點的高度。于是AVL樹結(jié)點定義和AVL樹操作函數(shù)聲明如下：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);

• 添加結(jié)點

AVL樹插入結(jié)點可能會破壞樹的平衡，所以需要我們在每次插入結(jié)點后進行維護平衡的操作，插入結(jié)點破壞平衡性的情況有如下四種。

• LL
  

LL的意思是新結(jié)點插入左子樹（L）的左孩子（L），這種情況需要右旋，為了方便理解，我們作了下圖，后續(xù)我們也會采用類似的描述。

結(jié)點z是新插入結(jié)點，此時x結(jié)點的左孩子和右孩子高度差絕對值大于1，破壞了平衡，需要進行右旋操作維護平衡。對應(yīng)的C代碼實現(xiàn)如下：

/**
?* @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獲取平衡因子，無非就是計算左孩子和右孩子高度差。從圖中我們可以看出進行右旋后結(jié)點x和y的高度發(fā)生了變化，因此每進行一次右旋要調(diào)整結(jié)點x和y的高度，而且結(jié)點y的高度可能會受到結(jié)點x高度的影響，因此必須先調(diào)整x的高度，再調(diào)整y的高度。get_max_height則是獲取某個結(jié)點的孩子的最大高度，再加1則是某結(jié)點的最終高度。

• RR

RR的意思是新結(jié)點插入右子樹（R）的右孩子（R），這種情況需要左旋，如下圖所示。

z是新插入結(jié)點，此時x結(jié)點的左右孩子高度差絕對值大于1，破壞了平衡，需要左旋操作維護平衡。對應(yīng)C代碼實現(xiàn)如下：

/**
?* @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;
}

從圖中我們可以看出，進行左旋操作后，結(jié)點x和y的高度發(fā)生了變化，因此每進行一次左旋要調(diào)整結(jié)點x和y的高度，而且結(jié)點y的高度可能會受到結(jié)點x高度的影響，因此必須先調(diào)整x的高度，再調(diào)整y的高度。

• RL

RL的意思是新結(jié)點插入右子樹（R）的左孩子（L），這種情況下需要先右旋再左旋，如下圖所示。

z是新插入結(jié)點，x的左右孩子高度差絕對值大于1，但是這里需要進行2次旋轉(zhuǎn)才能維護平衡，判斷是否滿足這種情況的條件如下：

1、左子樹和右子樹高度差小于-1。

2、右子樹的左孩子高度大于右孩子的高度。

• LR

LR的意思是新結(jié)點插入左子樹（L）的右孩子（R），這種情況下需要先左旋再右旋，如下圖所示。

z是新插入結(jié)點，x的左右孩子高度差絕對值大于1，但是這里需要進行2次旋轉(zhuǎn)才能維護平衡，判斷是否滿足這種情況的條件如下：

1、左子樹和右子樹高度差大于1。

2、左子樹的右孩子高度大于左孩子的高度。

綜上考慮四種結(jié)點插入情況后，C代碼實現(xiàn)如下：

/**
?* @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); //更新結(jié)點高度
????int balance_factor = get_balance_factor(root_node);
????if(balance_factor > 1?