Found bugs in avltree.py, need fixing.

bhehir · Aug 12, 2011 · af22998 · af22998
1 parent 51d52fb
commit af22998
Show file tree

Hide file tree

Showing 2 changed files with 126 additions and 7 deletions.
diff --git a/datastruct/tree/AVL-tree/avltree-en.tex b/datastruct/tree/AVL-tree/avltree-en.tex
@@ -834,6 +834,111 @@ \section{Imperative AVL tree algorithm $\star$}
 However, it neccessary to show the traditional insert-and-rotate
 approach as the comparator to pattern matching algortihm.
 
+Similar as the imperative red-black tree algorithm, the strategy
+is first to do the insertion as same as for binary search tree,
+then fix the balance problem by rotation and return the final result.
+
+\begin{algorithmic}[1]
+\Function{Insert}{$T, k$}
+  \State $root \gets T$
+  \State $x \gets$ \Call{Create-Leaf}{$k$}
+  \State \Call{$\delta$}{$x$} $\gets 0$
+  \State $parent \gets NIL$
+  \While{$T \neq NIL$}
+    \State $parent \gets T$
+    \If{$k <$ \Call{Key}{$T$}}
+      \State $T \gets $ \Call{Left}{$T$}
+    \Else
+      \State $T \gets $ \Call{Right}{$T$}
+    \EndIf
+  \EndWhile
+  \State $\Delta \gets 0$
+  \State \Call{Parent}{$x$} $\gets parent$
+  \If{$parent = NIL$} \Comment{tree $T$ is empty}
+    \State \Return $x$
+  \ElsIf{$k <$ \Call{Key}{$parent$}}
+    \State \Call{Left}{$parent$} $\gets x$
+    \State $\Delta \gets -1$
+  \Else
+    \State \Call{Right}{$parent$} $\gets x$
+    \State $\Delta \gets 1$
+  \EndIf
+  \State \Return \Call{AVL-Insert-Fix}{$root, x, \Delta$}
+\EndFunction
+\end{algorithmic}
+
+Note that after insertion, the height of the tree may increase, so that
+the balancing factor $\delta$ may also change, insert on right side will
+increase $\delta$ by 1, while insert on left side will decrease it. In
+the algorithm, a variable $\Delta$ is used to record the difference of
+$\delta$ after insertion.
+
+We can translate the pseudo code to real programming language, such as 
+Python \footnote{C and C++ source code are available along with this book}. 
+\lstset{language=Python}
+\begin{lstlisting}
+def avl_insert(t, key):
+    root = t
+    x = Node(key)
+    parent = None
+    while(t):
+        parent = t
+        if(key < t.key):
+            t = t.left
+        else:
+            t = t.right
+    delta = 0
+    if parent is None: #tree is empty
+        root = x
+    elif key < parent.key:
+        parent.set_left(x)
+        delta = - 1
+    else:
+        parent.set_right(x)
+        delta = 1
+    return avl_insert_fix(root, x, delta)
+\end{lstlisting}
+
+This is a top-down algorithm search the tree from root down to the proper
+position and insert the new key as a leaf. By the end of this algorith, it calls fixing procedure, which performs a bottom-up process to update 
+the balancing factor $delta$ along the parent field.
+
+\begin{algorithmic}[1]
+\Function{AVL-Insert-Fix}{$T, x, \Delta$}
+  \While{\Call{Parent}{$x$} $\neq NIL$}
+    \State $\delta \gets $ \textproc{$\delta$}(\Call{Parent}{$x$})
+    \State $\delta' \gets \delta + \Delta$
+    \State \textproc{$\delta$}(\Call{Parent}{$x$}) $\gets \delta'$
+    \State $P \gets $ \Call{Parent}{$x$}
+    \State $L \gets $ \Call{Left}{$x$}
+    \State $R \gets $ \Call{Right}{$x$}
+    \If{$|\delta| = 1$ and $|\delta'| = 0$} \Comment{Height doesn't change, algorithm terminates.}
+      \State \Return $T$
+    \ElsIf{$|\delta| = 0$ and $|\delta'| = 1$} \Comment{Height increases, go on bottom-up updating.}
+      \State $x \gets P$
+    \Else \Comment{$|\delta| = 1$ and $|\delta'| = 2$, need fixing}
+      \If{$|\delta'|=2$}
+        \If{$\delta(R) = -1$} \Comment{Right-Left case}
+          \State \Call{Right-Rotate}{$T, R$}
+          \State \Call{Left-Rotate}{$T, P$}
+        \Else \Comment{$\delta(R) = 1$, Right-Right case}
+          \State \Call{Left-Rotate}{$T, P$}
+          \State \Call{Left-Rotate}{$T, R$}
+        \EndIf
+      \Else \Comment{$\delta' = -2$}
+        \If{$\delta(L) = 1$} \Comment{Left-Right case}
+          \State \Call{Left-Rotate}{$T, L$}
+          \State \Call{Right-Rotate}{$T, P$}
+        \Else \Comment{$\delta(L) = -1$, Left-Left case}
+          \State \Call{Right-Rotate}{$T, P$}
+          \State \Call{Right-Rotate}{$T, L$}
+        \EndIf
+      \EndIf
+    \EndIf
+  \EndWhile
+  \State \Return $T$
+\EndFunction
+\end{algorithmic}
 
 \section{Chapter note}
 AVL tree was invented in 1962 by Adelson-Velskii and Landis\cite{wiki}, 

diff --git a/datastruct/tree/AVL-tree/src/avltree.py b/datastruct/tree/AVL-tree/src/avltree.py
@@ -107,7 +107,7 @@ def avl_insert(t, key):
     else:
         parent.set_right(x)
         delta = 1
-    return avl_insert_fix(root, x, delta)
+    return avl_insert_fix(root, x.parent, delta)
 
 # bottom-up update delta and fixing
 def avl_insert_fix(t, x, delta):
@@ -124,14 +124,20 @@ def avl_insert_fix(t, x, delta):
     # case 3: |d| == 1, |d'| == 2, AVL violation,
     #    we need fixing by rotation.
     #
-    while x.parent is not None:
-        d1 = x.parent.delta
-        d2 = x.parent.delta + delta
-        x.parent.delta = d2
-        (p, l, r) = (x.parent, x.parent.left, x.parent.right)
+    while x is not None:
+        d1 = x.delta
+        d2 = x.delta + delta
+        x.delta = d2
+        (p, l, r) = (x, x.left, x.right)
         if abs(d1) == 1 and abs(d2) == 0:
             return t
         elif abs(d1) == 0 and abs(d2) == 1:
+            if x.parent is None:
+                break
+            if x == x.parent.left:
+                delta = -1
+            else:
+                delta = 1
             x = x.parent
         else: # abs(d1) == 1 and abs(d2) == 2
             if d2 == 2:
@@ -148,6 +154,8 @@ def avl_insert_fix(t, x, delta):
                 else: # l.delta == -1, Left-left case
                     right_rotate(t, p)
                     right_rotate(t, l)
+            break
+    return t
 
 # helpers
 
@@ -158,7 +166,13 @@ def to_list(t):
         return to_list(t.left)+[t.key]+to_list(t.right)
 
 def to_tree(l):
-    return reduce(avl_insert, l, None)
+    #t = reduce(avl_insert, l, None)
+    t = None
+    for x in l:
+        t = avl_insert(t, x)
+    print "xs=", l
+    print "t=", to_str(t)
+    assert(False)
 
 def to_str(t):
     if t is None: