01

—

認(rèn)識(shí)AVL樹(shù)

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

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

02—

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

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

AVL樹(shù)插入結(jié)點(diǎn)可能會(huì)破壞樹(shù)的平衡，所以需要我們?cè)诿看尾迦虢Y(jié)點(diǎn)后進(jìn)行維護(hù)平衡的操作，插入結(jié)點(diǎn)破壞平衡性的情況有如下四種。

• LL
  

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

結(jié)點(diǎn)z是新插入結(jié)點(diǎn)，此時(shí)x結(jié)點(diǎn)的左孩子和右孩子高度差絕對(duì)值大于1，破壞了平衡，需要進(jìn)行右旋操作維護(hù)平衡。對(duì)應(yīng)的C代碼實(shí)現(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獲取平衡因子，無(wú)非就是計(jì)算左孩子和右孩子高度差。從圖中我們可以看出進(jìn)行右旋后結(jié)點(diǎn)x和y的高度發(fā)生了變化，因此每進(jìn)行一次右旋要調(diào)整結(jié)點(diǎn)x和y的高度，而且結(jié)點(diǎn)y的高度可能會(huì)受到結(jié)點(diǎn)x高度的影響，因此必須先調(diào)整x的高度，再調(diào)整y的高度。get_max_height則是獲取某個(gè)結(jié)點(diǎn)的孩子的最大高度，再加1則是某結(jié)點(diǎn)的最終高度。

• RR

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

z是新插入結(jié)點(diǎn)，此時(shí)x結(jié)點(diǎn)的左右孩子高度差絕對(duì)值大于1，破壞了平衡，需要左旋操作維護(hù)平衡。對(duì)應(yīng)C代碼實(shí)現(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;
}

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

• RL

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

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

1、左子樹(shù)和右子樹(shù)高度差小于-1。

2、右子樹(shù)的左孩子高度大于右孩子的高度。

• LR

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

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

1、左子樹(shù)和右子樹(shù)高度差大于1。

2、左子樹(shù)的右孩子高度大于左孩子的高度。

綜上考慮四種結(jié)點(diǎn)插入情況后，C代碼實(shí)現(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é)點(diǎn)高度
????int balance_factor = get_balance_factor(root_node);
????if(balance_factor > 1?