update

1 files changed, 61 insertions, 7 deletions

diff --git a/Computer_Science/data_structures/chapter_4/avl_tree.c b/Computer_Science/data_structures/chapter_4/avl_tree.c
index da6ab0d..f84db7b 100644
--- a/Computer_Science/data_structures/chapter_4/avl_tree.c
+++ b/Computer_Science/data_structures/chapter_4/avl_tree.c
@@ -134,6 +134,63 @@ AvlTree insert(elem_t x, AvlTree t)
     return t;
 }
 
+AvlTree insert_nonrecursive(elem_t x, AvlTree t)
+{
+    Position tmp;
+    Position prev[100] ;
+    Position p = t;
+    int i = 0;
+    int j;
+
+    /* index 0 not used */
+    prev[i] = p;
+    while(p) {
+        if(x < p->elem) {
+            prev[++i] = p;
+            p = p->left;
+        } else if(x > p->elem) {
+            prev[++i] = p;
+            p = p->right;
+        } else
+            return t;
+    }
+
+    tmp = malloc(sizeof(struct AvlNode));
+    tmp->elem = x;
+    tmp->left = tmp->right = NULL;
+    tmp->height = 0;
+
+    if(!prev[i]) {
+        return tmp;
+    } else if(x < prev[i]->elem) {
+        prev[i]->left = tmp;
+        prev[i]->height++;
+        if(i - 1 > 0) {
+            if(prev[i - 1]->left == prev[i]
+                    && prev[i]->height - height(prev[i - 1]->right) == 2)
+                prev[i - 2] = single_rotate_with_left(prev[i - 1]);
+            else if(prev[i - 1]->right == prev[i]
+                    && prev[i]->height - height(prev[i - 1]->left) == 2)
+                prev[i - 2] = double_rotate_with_left(prev[i - 1]);
+        }
+    }
+    else {
+        prev[i]->right = tmp;
+        prev[i]->height++;
+        if(i - 1 > 0) {
+            if(prev[i - 1]->right == prev[i]
+			   && prev[i]->height - height(prev[i - 1]->left) == 2)
+                prev[i - 2] = single_rotate_with_right(prev[i - 1]);
+            else if(prev[i - 1]->left == prev[i]
+                    && prev[i]->height - height(prev[i - 1]->right) == 2) {
+                prev[i - 2] = double_rotate_with_right(prev[i - 2]);
+            }
+        }
+    }
+
+    return t;
+}
+
 /* lazy delete ? */
 AvlTree delete(elem_t x, AvlTree t)
 {
@@ -142,18 +199,15 @@ AvlTree delete(elem_t x, AvlTree t)
 
 void test()
 {
+    int i;
     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);
+    for(i = 0; i < 3; i++) {
+        t = insert_nonrecursive(i + 1, 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);
 }