avl_tree impl

8 files changed, 213 insertions, 9 deletions

diff --git a/Computer_Science/data_structures/chapter_4/avl_tree b/Computer_Science/data_structures/chapter_4/avl_tree
new file mode 100755
index 0000000..1d5d102
--- /dev/null
+++ b/Computer_Science/data_structures/chapter_4/avl_tree
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;
+}
diff --git a/Computer_Science/data_structures/chapter_4/avl_tree.h b/Computer_Science/data_structures/chapter_4/avl_tree.h
new file mode 100644
index 0000000..1be3cd6
--- /dev/null
+++ b/Computer_Science/data_structures/chapter_4/avl_tree.h
@@ -0,0 +1,27 @@
+#ifndef _AVL_TREE_H
+#define _AVL_TREE_H
+
+struct AvlNode;
+typedef struct AvlNode *Position;
+typedef struct AvlNode *AvlTree;
+typedef int elem_t;
+
+AvlTree make_empty(AvlTree t);
+Position find(elem_t x, AvlTree t);
+Position find_min(AvlTree t);
+Position find_max(AvlTree t);
+AvlTree insert(elem_t x, AvlTree t);
+AvlTree delete(elem_t x, AvlTree t);
+elem_t retrieve(Position p);
+
+/* for print node, place impl in header file */
+struct AvlNode
+{
+    elem_t elem;
+    AvlTree left;
+    AvlTree right;
+    int height;
+};
+typedef AvlTree Tree;
+
+#endif
diff --git a/Computer_Science/data_structures/chapter_4/binary_search_tree b/Computer_Science/data_structures/chapter_4/binary_search_tree
new file mode 100755
index 0000000..7c74886
--- /dev/null
+++ b/Computer_Science/data_structures/chapter_4/binary_search_tree
diff --git a/Computer_Science/data_structures/chapter_4/binary_search_tree.c b/Computer_Science/data_structures/chapter_4/binary_search_tree.c
index fb61e7b..b498d54 100644
--- a/Computer_Science/data_structures/chapter_4/binary_search_tree.c
+++ b/Computer_Science/data_structures/chapter_4/binary_search_tree.c
@@ -5,13 +5,6 @@
 #include "binary_search_tree.h"
 #include "print_ascii_tree.h"
 
-struct TreeNode
-{
-    elem_t elem;
-    SearchTree left;
-    SearchTree right;
-};
-
 SearchTree make_empty(SearchTree t)
 {
     if(t != NULL) {
@@ -125,6 +118,8 @@ void test()
     insert(3, t);
     insert(2, t);
     insert(10, t);
+    insert(12, t);
+    insert(-1, t);
 
     print_tree_pre_order(t);
     printf("\n");
diff --git a/Computer_Science/data_structures/chapter_4/binary_search_tree.h b/Computer_Science/data_structures/chapter_4/binary_search_tree.h
index da128f8..2d9425e 100644
--- a/Computer_Science/data_structures/chapter_4/binary_search_tree.h
+++ b/Computer_Science/data_structures/chapter_4/binary_search_tree.h
@@ -14,4 +14,12 @@ SearchTree insert(elem_t x, SearchTree t);
 SearchTree delete(elem_t x, SearchTree t);
 elem_t retrieve(Position p);
 
+struct TreeNode
+{
+    elem_t elem;
+    SearchTree left;
+    SearchTree right;
+};
+typedef SearchTree Tree;
+
 #endif  /* _BINARY_SEARCH_TREE_H */
diff --git a/Computer_Science/data_structures/chapter_4/print_ascii_tree.c b/Computer_Science/data_structures/chapter_4/print_ascii_tree.c
index f2e9839..7b71d27 100644
--- a/Computer_Science/data_structures/chapter_4/print_ascii_tree.c
+++ b/Computer_Science/data_structures/chapter_4/print_ascii_tree.c
@@ -2,7 +2,7 @@
 #include <string.h>
 #include <stdlib.h>
 
-#include "binary_search_tree.h"
+#include "avl_tree.h"
 #include "print_ascii_tree.h"
 
 struct asciinode_struct
@@ -256,6 +256,7 @@ void print_ascii_tree(Tree t)
   asciinode *proot;
   int xmin, i;
   if (t == NULL) return;
+  printf("\n");
   proot = build_ascii_tree(t);
   compute_edge_lengths(proot);
   for (i=0; i<proot->height && i < MAX_HEIGHT; i++)
diff --git a/Computer_Science/data_structures/chapter_4/print_ascii_tree.h b/Computer_Science/data_structures/chapter_4/print_ascii_tree.h
index 12eed6a..1ddfa3b 100644
--- a/Computer_Science/data_structures/chapter_4/print_ascii_tree.h
+++ b/Computer_Science/data_structures/chapter_4/print_ascii_tree.h
@@ -1,12 +1,21 @@
+/*
+** !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
+** !!!Code originally from /http://www.openasthra.com/c-tidbits/printing-binary-trees-in-ascii/
+** !!! Just saved it, cause the website is down.
+** !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
+** I use it here for learning.
+*/
 #ifndef _PRINT_ASCII_TREE_H
 #define _PRINT_ASCII_TREE_H
 
 struct asciinode_struct;
 typedef struct asciinode_struct asciinode;
-typedef SearchTree Tree;
 
 #define MAX_HEIGHT 1000
+
+#ifndef INFINITY
 #define INFINITY (1 << 20)
+#endif
 
 int MIN (int X, int Y);
 int MAX (int X, int Y);