# <center><font size=10>AVL_tree.a</font><br><font size=5>AVL樹使用說明書</font><br><font size=4>by 李奕承</font></center>
# <center>摘要</center>
本library提供的結構如下
```c
typedef struct avl_node {
struct avl_node *left;
struct avl_node *right;
int height;
} avl_node_t;
```
本 library 提供以下幾種函數
- 節點初始化
- 印出樹
- 插入節點
- 尋找節點
- 尋找最小節點
- 尋找最大節點
- 刪除節點
# <center>使用方法</center>
### 1.帶入標頭檔
```c
#include"AVLSpec.h"
```
### 2.創造AVL tree
宣告一個 avl_node_t 的空指標用來指向樹的root，此處以 avl_root_a 為例
```c
avl_node_t * avl_root_a = NULL;
```
### 3.將 avl_node_t 作為成員包入自己的結構中
例如：
```c
typedef struct test_avl{
char name;
int value;
avl_node_t node; //作為成員
}test_avl_t;
```
### 4.提供用來比較的回調函數指標
以下幾個需要使用者編寫並提供用來比較的回調函數指標
```c
AVL_insert
AVL_find
AVL_delete
```
### 5.搭配巨集使用
使用 AVLSpec.h 中提供的巨集，可以在回調函數中依據 avl_node_t 的記憶體位置反向求得使用者結構的記憶體起始位置，轉型後就可以用來讀取要比較的資料。
```c
#define return_to_user_struct_pointer(USER_STRUCT_TYPE, MEMBER_NAME, MEMBER_POINT)
```
### 6.編譯
- AVLSpec.h 要記得放在引用標頭檔的路徑下
- 編譯時記得加入 AVL_tree.a
```
gcc -I include -Wall -o ./bin/test test.c AVL_tree.a
```
# <center>函數介紹與範例</center>
## 範例使用的結構
下面是範例用到的結構
```c
typedef struct test_avl{
char name;
int value;
avl_node_t node;
}test_avl_t;
```
下面的回調函數用來比較兩個 test_avl_t 節點中的 value 值
```c
int compare_value(void * elementA, void * elementB)
{
if(return_to_user_struct_pointer(test_avl_t, node, elementA)->value <
return_to_user_struct_pointer(test_avl_t, node, elementB)->value)
{
return -1;
}
else if(return_to_user_struct_pointer(test_avl_t, node, elementA)->value ==
return_to_user_struct_pointer(test_avl_t, node, elementB)->value)
{
return 0;
}
else if(return_to_user_struct_pointer(test_avl_t, node, elementA)->value >
return_to_user_struct_pointer(test_avl_t, node, elementB)->value)
{
return 1;
}
else
{
return 2;
}
}
```
下面的回調函數用給定的值來比較 test_avl_t 節點中的value值
```c
int compare_key(int key, void * in_tree_element)
{
if(key <
return_to_user_struct_pointer(test_avl_t, node, in_tree_element)->value)
{
return -1;
}
else if(key ==
return_to_user_struct_pointer(test_avl_t, node, in_tree_element)->value)
{
return 0;
}
else
{
return 1;
}
}
```
下面的回調函數用 avl_node_t 指標取得 test_avl_t 中的value值
```c
int get_value(avl_node_t * element)
{
return return_to_user_struct_pointer(test_avl_t, node, element)->value;
}
```
下面的回調函數用 avl_node_t 指標取得 test_avl_t 中的name值
```c
int get_name(avl_node_t * element)
{
return return_to_user_struct_pointer(test_avl_t, node, element)->name;
}
```
下面的回調函數用 avl_node_t 指標取得該節點的樹高
```c
int get_height(avl_node_t * element)
{
return element->height;
}
```
## 節點初始化
```c
void AVL_init(avl_node_t * node);
```
當你宣告一個包含 avl_node_t 的結構之後，可以使用這個函數來初始化 avl_node_t 中的值
以下是範例中創建的root指標及結構
```c
avl_node_t * avl_root_a = NULL;
test_avl_t a;
a.name = 'A';
a.value = 20;
AVL_init(&a.node);
test_avl_t b;
b.name = 'B';
b.value = 4;
AVL_init(&b.node);
test_avl_t c;
c.name = 'C';
c.value = 26;
AVL_init(&c.node);
test_avl_t d;
d.name = 'D';
d.value = 3;
AVL_init(&d.node);
test_avl_t e;
e.name = 'E';
e.value = 9;
AVL_init(&e.node);
test_avl_t f;
f.name = 'F';
f.value = 21;
AVL_init(&f.node);
test_avl_t g;
g.name = 'G';
g.value = 30;
AVL_init(&g.node);
test_avl_t h;
h.name = 'H';
h.value = 2;
AVL_init(&h.node);
test_avl_t i;
i.name = 'I';
i.value = 7;
AVL_init(&i.node);
test_avl_t j;
j.name = 'J';
j.value = 11;
AVL_init(&j.node);
test_avl_t k;
k.name = 'K';
k.value = 15;
AVL_init(&k.node);
test_avl_t l;
l.name = 'L';
l.value = 8;
AVL_init(&l.node);
```
## 印出樹
```c
void printf_AVL_tree(avl_node_t * root, int(*get_data)(avl_node_t * queue_member),
int ascii);
```
使用這個函數可以印出AVL tree ，在之後的範例會用到
## 插入節點
```c
void AVL_insert(avl_node_t * element, avl_node_t ** root,
int(*compare)(void * element, void * in_tree_element));
```
使用這個函數可以在 AVL tree 中插入節點
```c
printf("\n--------------------------------------");
printf("\ncase a");
printf("\n--------------------------------------");
AVL_insert(&a.node, &avl_root_a, compare_value);
AVL_insert(&b.node, &avl_root_a, compare_value);
printf_AVL_tree(avl_root_a, get_value);
AVL_init(&a.node);
AVL_init(&b.node);
avl_root_a = NULL;
printf("\n----- case a insert 15 -----\n");
AVL_insert(&a.node, &avl_root_a, compare_value);
AVL_insert(&b.node, &avl_root_a, compare_value);
AVL_insert(&k.node, &avl_root_a, compare_value);
printf_AVL_tree(avl_root_a, get_value);
AVL_init(&a.node);
AVL_init(&b.node);
AVL_init(&k.node);
avl_root_a = NULL;
```
終端機的輸出
```
--------------------------------------
case a
--------------------------------------
20
/
/
4
----- case a insert 15 -----
15
/ \
/ \
4 20
----- case a insert 8 -----
8
/ \
/ \
4 20
```
## 尋找節點
```c
avl_node_t * AVL_find(int key, avl_node_t ** root,
int(*compare)(int key, void * in_tree_element));
```
使用這個函數可以在 AVL tree 中尋找符合key值的節點，以下是範例
```c
printf_AVL_tree(avl_root_a, get_value, 0);
printf("\n");
printf_AVL_tree(avl_root_a, get_name, 1);
printf("\n");
avl_node_t * found = AVL_find(8, &avl_root_a, compare_key);
printf("%d\n", return_to_user_struct_pointer(test_avl_t, node, found)->value);
```
終端機的輸出
```
9
/ \
/ \
/ \
/ \
/ \
/ \
/ \
4 20
/ \ / \
/ \ / \
/ \ / \
3 7 11 26
/ \ / \
/ \ / \
2 8 21 30
E
/ \
/ \
/ \
/ \
/ \
/ \
/ \
B A
/ \ / \
/ \ / \
/ \ / \
D I J C
/ \ / \
/ \ / \
H L F G
who's value is 8 ? : L
```
## 尋找最小節點
```c
avl_node_t * AVL_find_minimum(avl_node_t * root);
```
使用這個函數可以在 AVL tree 中尋找key值最小的節點，以下是範例
```c
found = AVL_find_minimum(avl_root_a);
printf("who's value is minimum ? : %c\n",
return_to_user_struct_pointer(test_avl_t, node, found)->name);
```
終端機的輸出
```
9
/ \
/ \
/ \
/ \
/ \
/ \
/ \
4 20
/ \ / \
/ \ / \
/ \ / \
3 7 11 26
/ \ / \
/ \ / \
2 8 21 30
E
/ \
/ \
/ \
/ \
/ \
/ \
/ \
B A
/ \ / \
/ \ / \
/ \ / \
D I J C
/ \ / \
/ \ / \
H L F G
who's value is minimum ? : H
```
## 尋找最大節點
```c
avl_node_t * AVL_find_maximum(avl_node_t * root);
```
使用這個函數可以在 AVL tree 中尋找key值最大的節點，以下是範例
```c
found = AVL_find_maximum(avl_root_a);
printf("who's value is maximum ? : %c\n",
return_to_user_struct_pointer(test_avl_t, node, found)->name);
```
終端機的輸出
```
9
/ \
/ \
/ \
/ \
/ \
/ \
/ \
4 20
/ \ / \
/ \ / \
/ \ / \
3 7 11 26
/ \ / \
/ \ / \
2 8 21 30
E
/ \
/ \
/ \
/ \
/ \
/ \
/ \
B A
/ \ / \
/ \ / \
/ \ / \
D I J C
/ \ / \
/ \ / \
H L F G
who's value is maximum ? : G
```
## 刪除節點
```c
void AVL_delete(avl_node_t * delete_element, avl_node_t ** root,
int (*compare)(void * delete_element, void * in_tree_element));
```
使用這個函數可以在 AVL tree 中刪除指定key值的節點，以下是範例
```c
found = AVL_find(8, &avl_root_a, compare_key);
printf("delete %d\n", return_to_user_struct_pointer(test_avl_t, node, found)->value);
AVL_delete(found, &avl_root_a, compare_value);
printf_AVL_tree(avl_root_a, get_value, 0);
printf("\n");
printf("--------------------------------\n");
found = AVL_find(7, &avl_root_a, compare_key);
printf("delete %d\n", return_to_user_struct_pointer(test_avl_t, node, found)->value);
AVL_delete(found, &avl_root_a, compare_value);
printf_AVL_tree(avl_root_a, get_value, 0);
printf("\n");
printf("--------------------------------\n");
found = AVL_find(11, &avl_root_a, compare_key);
printf("delete %d\n", return_to_user_struct_pointer(test_avl_t, node, found)->value);
AVL_delete(found, &avl_root_a, compare_value);
printf_AVL_tree(avl_root_a, get_value, 0);
printf("\n");
printf("--------------------------------\n");
found = AVL_find(26, &avl_root_a, compare_key);
printf("delete %d\n", return_to_user_struct_pointer(test_avl_t, node, found)->value);
AVL_delete(found, &avl_root_a, compare_value);
printf_AVL_tree(avl_root_a, get_value, 0);
printf("\n");
printf("--------------------------------\n");
found = AVL_find(21, &avl_root_a, compare_key);
printf("delete %d\n", return_to_user_struct_pointer(test_avl_t, node, found)->value);
AVL_delete(found, &avl_root_a, compare_value);
printf_AVL_tree(avl_root_a, get_value, 0);
printf("\n");
printf("--------------------------------\n");
found = AVL_find(30, &avl_root_a, compare_key);
printf("delete %d\n", return_to_user_struct_pointer(test_avl_t, node, found)->value);
AVL_delete(found, &avl_root_a, compare_value);
printf_AVL_tree(avl_root_a, get_value, 0);
printf("\n");
printf("--------------------------------\n");
found = AVL_find(2, &avl_root_a, compare_key);
printf("delete %d\n", return_to_user_struct_pointer(test_avl_t, node, found)->value);
AVL_delete(found, &avl_root_a, compare_value);
printf_AVL_tree(avl_root_a, get_value, 0);
printf("\n");
printf("--------------------------------\n");
found = AVL_find(20, &avl_root_a, compare_key);
printf("delete %d\n", return_to_user_struct_pointer(test_avl_t, node, found)->value);
AVL_delete(found, &avl_root_a, compare_value);
printf_AVL_tree(avl_root_a, get_value, 0);
printf("\n");
```
終端機的輸出
```
9
/ \
/ \
/ \
/ \
/ \
/ \
/ \
4 20
/ \ / \
/ \ / \
/ \ / \
3 7 11 26
/ \ / \
/ \ / \
2 8 21 30
--------------------------------
delete 8
9
/ \
/ \
/ \
/ \
/ \
/ \
/ \
4 20
/ \ / \
/ \ / \
/ \ / \
3 7 11 26
/ / \
/ / \
2 21 30
--------------------------------
delete 7
9
/ \
/ \
/ \
/ \
/ \
/ \
/ \
3 20
/ \ / \
/ \ / \
/ \ / \
2 4 11 26
/ \
/ \
21 30
--------------------------------
delete 11
9
/ \
/ \
/ \
/ \
/ \
/ \
/ \
3 26
/ \ / \
/ \ / \
/ \ / \
2 4 20 30
\
\
21
--------------------------------
delete 26
9
/ \
/ \
/ \
3 21
/ \ / \
/ \ / \
2 4 20 30
--------------------------------
delete 21
9
/ \
/ \
/ \
3 30
/ \ /
/ \ /
2 4 20
--------------------------------
delete 30
9
/ \
/ \
/ \
3 20
/ \
/ \
2 4
--------------------------------
delete 2
9
/ \
/ \
/ \
3 20
\
\
4
--------------------------------
delete 20
4
/ \
/ \
3 9
```
Sign in with Wallet
Connect another wallet