1 files changed, 164 insertions, 0 deletions
diff --git a/Computer_Science/data_structures/chapter_4/avl_tree.c b/Computer_Science/data_structures/chapter_4/avl_tree.c
new file mode 100644
index 0000000..da6ab0d
--- /dev/null
+++ b/Computer_Science/data_structures/chapter_4/avl_tree.c
@@ -0,0 +1,164 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <math.h>
+
+#include "avl_tree.h"
+#include "print_ascii_tree.h"
+
+AvlTree make_empty(AvlTree t)
+{
+    if(t != NULL) {
+        make_empty(t->left);
+        make_empty(t->right);
+        free(t);
+    }
+
+    return NULL;
+}
+
+Position find(elem_t x, AvlTree t)
+{
+    if(t == NULL)
+        return NULL;
+    else if(x == t->elem)
+        return t;
+    else if(x > t->elem)
+        return find(x, t->right);
+    else if(x < t->elem)
+        return find(x, t->left);
+}
+
+Position find_min(AvlTree t)
+{
+    if(t == NULL)
+        return NULL;
+    else if(t->left == NULL)
+        return t;
+    else
+        return find_min(t->left);
+}
+
+Position find_max(AvlTree t)
+{
+    if(t == NULL)
+        return NULL;
+    else if(t->right == NULL)
+        return t;
+    else
+        return find_max(t->right);
+}
+
+static int height(Position p)
+{
+    return p == NULL ? -1 : p->height;
+}
+
+static Position single_rotate_with_left(Position p)
+{
+    Position p_left;
+
+    p_left = p->left;
+    p->left = p_left->right;
+    p_left->right = p;
+
+    /* derectly use ->height may case some problem */
+    p->height = MAX(height(p->left), height(p->right)) + 1;
+    p_left->height = MAX(height(p_left->left), p->height) + 1;
+
+    /* return new Node */
+    return p_left;
+}
+
+static Position single_rotate_with_right(Position p)
+{
+    Position p_right;
+
+    p_right = p->right;
+    p->right = p_right->left;
+    p_right->left = p;
+
+    p->height = MAX(height(p->left), height(p->right)) + 1;
+    p_right->height = MAX(height(p_right->right), p->height) + 1;
+
+    /* return new node */
+    return p_right;
+
+}
+
+static Position double_rotate_with_left(Position p)
+{
+    p->left = single_rotate_with_right(p->left);
+
+    return single_rotate_with_left(p);
+}
+
+
+static Position double_rotate_with_right(Position p)
+{
+
+    p->right = single_rotate_with_left(p->right);
+
+    return single_rotate_with_right(p);
+}
+
+AvlTree insert(elem_t x, AvlTree t)
+{
+    if(t == NULL) {
+        t = malloc(sizeof(struct AvlNode));
+        t->elem = x;
+        t->height = 0;
+        t->left = t->right = NULL;
+    } else if(x > t->elem) {
+        t->right = insert(x, t->right);
+        /* > 1 or == 2? */
+        if(height(t->right) - height(t->left) > 1) {
+            if(x > t->right->elem)
+                t = single_rotate_with_right(t);
+            if(x < t->right->elem)
+                t = double_rotate_with_right(t);
+        }
+    } else if(x < t->elem) {
+        t->left = insert(x, t->left);
+
+        if(height(t->left) - height(t->right) == 2) {
+            if(x < t->left->elem)
+                t = single_rotate_with_left(t);
+            if(x > t->left->elem)
+                t = double_rotate_with_left(t);
+        }
+    }
+
+    /* else do nothing, but update the height */
+    t->height = MAX(height(t->left), height(t->right)) + 1;
+
+    return t;
+}
+
+/* lazy delete ? */
+AvlTree delete(elem_t x, AvlTree t)
+{
+
+}
+
+void test()
+{
+    AvlTree t = NULL;
+
+    t = insert(4, t);
+    t = insert(3, t);
+    t = insert(2, t);
+    t = insert(1, t);
+    t = insert(8, t);
+    t = insert(9, t);
+
+    printf("min:%d\n", find_min(t)->elem);
+    printf("max:%d\n", find_max(t)->elem);
+    printf("find 2:%d\n", find(2, t)->elem);
+    print_ascii_tree(t);
+}
+
+int main()
+{
+    test();
+    return 0;
+}