# AVL Tree library
作業網址: [https://hackmd.io/@chtsai/2020DS-homework-4](https://hackmd.io/@chtsai/2020DS-homework-4)
github: [https://github.com/erictsai1224tw/erictsai/tree/DS/AVL_Tree](https://github.com/erictsai1224tw/erictsai/tree/DS/AVL_Tree)
**AVL Tree 需要的節點結構:**
```c
typedef struct avl_node
{
struct avl_node *left;
struct avl_node *right;
int height;
} avl_node_t;
```
**實作的函式**
```c=
avl_node_t *insert(void *element, avl_node_t *root, int (*compare)(void *, void *));
avl_node_t *Delete(void *element, avl_node_t *root, int (*compare)(void *, void *));
avl_node_t *find(void *element, avl_node_t *root, int (*compare)(void *, void *));
static avl_node_t *rotateright(avl_node_t *);
static avl_node_t *rotateleft(avl_node_t *);
static avl_node_t *RR(avl_node_t *);
static avl_node_t *LL(avl_node_t *);
static avl_node_t *LR(avl_node_t *);
static avl_node_t *RL(avl_node_t *);
static int height(avl_node_t *);
static int balanceFactor(avl_node_t *);
```
## 前言
其實 AVL tree 就是 Binary Search Tree的一種，更精確地來說，其實就是先按BST的方式操作後，再依據每一點的balance factor來看要怎麼整理(RR, LL, RL, LR)。
這棵樹最厲害的地方就是，她維持了BST的特性，你會發現一顆整理前(也就是BST)與整理後(AVL Tree)，兩者的in order順序印出來是一樣的。
在各種情況下，時間複雜度都是logN，以及透過整理，讓這棵樹不會長歪，同時資料的排序也是維持跟BST一樣。
## static函式
外部無法存取這些函式，僅供內部使用
### 右旋(rotate right)
```c
static avl_node_t *rotateright(avl_node_t *node)
{
avl_node_t *temp = node->left;
node->left = temp->right;
temp->right = node;
node->height = height(node);
temp->height = height(temp);
return temp;
}
```
### 左旋(rotate left)
```c
static avl_node_t *rotateleft(avl_node_t *node)
{
avl_node_t *temp = node->right;
node->right = temp->left;
temp->left = node;
node->height = height(node);
temp->height = height(temp);
return temp;
}
```
### RR(插入在右子樹的右邊)
其實就是 rotate left
```c
static avl_node_t *RR(avl_node_t *node)
{
return rotateleft(node);
}
```
### LL(插入在左子樹的左邊)
```c
static avl_node_t *LL(avl_node_t *node)
{
return rotateright(node);
}
```
### LR(插入在左子樹的右邊)
先左轉再右轉...
```c
static avl_node_t *LR(avl_node_t *node)
{
node->left = rotateleft(node->left);
return rotateright(node);
}
```
### RL(插入在右子樹的左邊)
先右轉再左轉，這樣比較好記😆
```c
static avl_node_t *RL(avl_node_t *node)
{
node->right = rotateright(node->right);
return rotateleft(node);
}
```
### 點的高度
第18行的寫法稱為"三元運算子"，可以參考[這篇](https://shengyu7697.github.io/blog/2019/12/27/Cpp-ternary-operator/)
```c=
static int height(avl_node_t *node)
{
int height_left = 0;
int height_right = 0;
if (node == NULL)
{
return 0;
}
if (node->left)
{
height_left = height(node->left);
}
if (node->right)
{
height_right = height(node->right);
}
return height_right > height_left ? ++height_right : ++height_left;
}
```
### 更新樹根(root)以下所有點的高度
為了能夠更新樹根下所有點的高度，採用post-order(LRV)順序來更新
```c
static void update_node_height(avl_node_t *node)
{
if (node->left)
update_node_height(node->left);
if (node->right)
update_node_height(node->right);
node->height = height(node);
}
```
### Balance Factor
AVL Tree一直強調的就是要怎麼不讓這棵樹長歪，就是要透過balance factor來修剪
bf = 左子樹高度-右子樹高度
```c
static int balanceFactor(avl_node_t *node)
{
return height(node->left) - height(node->right);
}
```
## 使用者可以呼叫使用的函式
### Insert
在第4行可以看到，先用BST那邊的插入函式進行插入的動作
之後更新每個點的高度，以及balance factor
接著若在root有發現bf>1或bf<-1的情形，採用recursive的方式，往下尋找，若尋找到-1<bf<1的點時，就會停止。且上一層的bf若不在合法範圍內，就會進到下方的整理區(LL, RR, LR, RL)。這樣一直往上，就會沿路整理，自然頂點root的bf就能落在合法區間內。
```c=
avl_node_t *insert(void *element, avl_node_t *root, int (*compare)(void *elementA, void *elementB))
{
//BST insert node, note that the same value WILL NOT create the new node!!
avl_node_t *node = (avl_node_t *)insertNode(element, (node_t *)root, compare);
//Initial the height of node
update_node_height(node);
//Initial the parameter of balance factor
int bf = balanceFactor(node);
//for checking the element from bottom
if ((bf > 1) || (bf < -1))
{
if (node->left)
node->left = insert(NULL, node->left, compare);
if (node->right)
node->right = insert(NULL, node->right, compare);
}
//update the height of node
update_node_height(node);
//update the balance factor
bf = balanceFactor(node);
//LL
if ((bf > 1) && (compare(element, node->left) == -1))
{
// printf("LL\n");
return LL(node);
}
//RR
if ((bf < -1) && (compare(element, node->right) == 1))
{
// printf("RR\n");
return RR(node);
}
//LR
if ((bf > 1) && (compare(element, node->left) == 1))
{
// printf("LR\n");
return LR(node);
}
//RL
if ((bf < -1) && (compare(element, node->right) == -1))
{
// printf("RL\n");
return RL(node);
}
return node;
}
```
### Delete
跟BST一樣刪法，刪完之後檢查有沒有長歪，長歪的話就進行修剪
這邊下方決定要如何調整(如LL與LR)，是用node->left該點的傾斜情形(bf)，來決定如何調整
```c=
avl_node_t *Delete(void *element, avl_node_t *node, int (*compare)(void *, void *))
{
//BST delete node
if (deleteNode(element, (node_t *)node, compare) == NULL)
return NULL;
node->height = height(node);
int bf = balanceFactor(node);
if ((bf > 1) || (bf < -1))
{
if (node->left)
Delete(NULL, node->left, compare);
if (node->right)
Delete(NULL, node->right, compare);
}
//LL
if ((bf > 1) && (balanceFactor(node->left) >= 0))
return LL(node);
//RR
if ((bf < -1) && (balanceFactor(node->right) <= 0))
return RR(node);
//LR
if ((bf > 1) && (balanceFactor(node->left) <= 0))
{
return LR(node);
}
//RL
if ((bf < -1) && (balanceFactor(node->right) > 0))
{
return RL(node);
}
return node;
}
```
### Find
沒錯，find過程完全跟BST一樣，因為只是找點沒有動到結構，就不需特地整理了
如果想要幫他整理，那就用insert那邊，給他插入NULL(element欄位)就好了
```c
avl_node_t *find(void *element, avl_node_t *node, int (*compare)(void *elementA, void *elementB))
{
return (avl_node_t *)findNode(element, (node_t *)node, compare);
}
```
## Demo
### 自訂結構，比較函式與印出元素函式
```c
typedef struct myElement
{
avl_node_t node;
char ID[11];
int math;
int eng;
} student_t;
student_t *root = NULL;
int compareMath(void *elementA, void *elementB)
{
int mathA = ((student_t *)elementA)->math;
int mathB = ((student_t *)elementB)->math;
if (mathA > mathB)
{
return 1;
}
if (mathA < mathB)
{
return -1;
}
else
return 0;
}
void print(void *element)
{
student_t *temp = (student_t *)element;
printf("id=%s, math=%d, english=%d\n", temp->ID, temp->math, temp->eng);
}
```
### 宣告節點並將值輸入進去
```c
student_t node0, node1, node2, node3, node4, node5;
strcpy(node0.ID, "C120308001");
node0.math = 40;
node0.eng = 100;
strcpy(node1.ID, "B220406001");
node1.math = 20;
node1.eng = 90;
strcpy(node2.ID, "D120306001");
node2.math = 60;
node2.eng = 95;
strcpy(node3.ID, "A220407001");
node3.math = 10;
node3.eng = 90;
strcpy(node4.ID, "D220506001");
node4.math = 30;
node4.eng = 70;
strcpy(node5.ID, "A120406001");
node5.math = 25;
node5.eng = 90;
```
### 採用BST的印出結果
樹狀圖中的點都是數學成績
```graphviz
digraph Binary_Search_Tree{
graph[ordering=out]
null0 [shape=point]
40 -> 20
40 -> 60
20 -> 10
20 -> 30
30 -> 25
30 -> null0
}
```
### 採用AVL Tree的印出結果
```graphviz
digraph AVL_Tree{
graph[ordering=out]
null0 [shape=point]
30 -> 20
30 -> 40
20 -> 10
20 -> 25
40 -> null0
40 -> 60
}
```
## 後記
有沒有發現一件事，就是AVL tree與BST的inorder順序相同，且兩者都是按照數據由小排到大?
其實這件事是非常合理的，因為在BST的插入規則中明訂了
> 新增一個node時，會將其與parent節點比較大小，插入在其左/右方
>
也因此大小排序是: right child > parent > left child
而in order的順序為LVR，也就是先印出left child，再來parent，最後是left child，就是由小到大印出，而推廣到整棵樹時，當然就會照全部資料由小到大印出了。
另外，因AVL Tree是將左右平衡，也因此root剛好是最中間的那一點，自然也就成為了中位數(節點數量為基數下)
ok，這大概就是這學期資料結構的最後一個作業了，拜拜~
###### tags: `DS` `AVL Tree` `BST`
Sign in with Wallet
Connect another wallet