AVL tree/LaTeX: almost finished.

bhehir · Aug 15, 2011 · f153a36 · f153a36
1 parent e10a7e7
commit f153a36
Showing 1 changed file with 145 additions and 33 deletions.
diff --git a/datastruct/tree/AVL-tree/avltree-en.tex b/datastruct/tree/AVL-tree/avltree-en.tex
@@ -165,6 +165,7 @@ \section{Definition of AVL tree}
 
 \be
   h \leq log_{\phi}(N+1) = log_{\phi}(2) \cdot \lg (N+1) \approx 1.44 \lg (N+1)
+  \label{eq:AVL-height}
 \ee
 
 It tells that the height of AVL tree is proportion to $O(\lg N)$, which
@@ -531,6 +532,7 @@ \subsubsection*{Right-right lean case}
   \delta'(y) = 0 \\
   \delta'(z) = \delta(z)
   \end{array}
+  \label{eq:rr-result}
 \ee
 
 \subsubsection*{Right-left lean case}
@@ -746,6 +748,11 @@ \subsection{Pattern Matching}
 balance (t, d) = (t, d)
 \end{lstlisting}
 
+The insertion algortihm takes time proportion to the height of the
+tree, and according to the result we proved above, its performance
+is $O(\lg N)$ where $N$ is the number of elements stored in the AVL 
+tree.
+
 \subsubsection{Verification}
 \index{AVL tree!verification}
 One can easily create a function to verify a tree is AVL tree. 
@@ -852,26 +859,23 @@ \section{Imperative AVL tree algorithm $\star$}
       \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$}
+  \State \Return \Call{AVL-Insert-Fix}{$root, x$}
 \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.
+increase $\delta$ by 1, while insert on left side will decrease it. By 
+the end of this algorithm, we need perform bottom-up fixing from node $x$
+towards root.
 
 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}. 
@@ -887,66 +891,174 @@ \section{Imperative AVL tree algorithm $\star$}
             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)
+    return avl_insert_fix(root, x)
 \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.
+position and insert the new key as a leaf. By the end of this algorith, it calls fixing procedure, by passing the root and the new node inserted.
+
+Note that we reuse the same methods of set\_left() and set\_right() as
+we defined in chapter of red-black tree.
+
+In order to resume the AVL tree balance property by fixing, we first determine if the new node is inserted on left hand or right hand. If it is on left, the balancing factor $\delta$ decreases, otherwise it inicreases. If we denote the new value as $\delta'$, there are 3 cases of the relationship between $\delta$ and $\delta'$.
+
+\begin{itemize}
+\item If $|\delta| = 1$ and $|\delta'| = 0$, this means adding the new node makes the tree perfectly balanced, the height of the parent node doesn't change, the algorithm can be terminated.
+
+\item If $|\delta| = 0$ and $|\delta'| = 1$, it means that either the height of left sub tree or right sub tree increases, we need go on check the upper level of the tree.
+
+\item If $|\delta| = 1$ and $|\delta'| = 2$, it means the AVL tree property is violated due to the new insertion. We need perform rotation to fix it.
+\end{itemize}
 
 \begin{algorithmic}[1]
-\Function{AVL-Insert-Fix}{$T, x, \Delta$}
+\Function{AVL-Insert-Fix}{$T, x$}
   \While{\Call{Parent}{$x$} $\neq NIL$}
     \State $\delta \gets $ \textproc{$\delta$}(\Call{Parent}{$x$})
-    \State $\delta' \gets \delta + \Delta$
+    \If{$x = $ \textproc{Left}(\Call{Parent}{$x$})}
+      \State $\delta' \gets \delta - 1$
+    \Else
+      \State $\delta' \gets \delta + 1$
+    \EndIf
     \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.}
+    \If{$|\delta| = 1$ and $|\delta'| = 0$} \Comment{Height doesn't change, terminates.}
       \State \Return $T$
-    \ElsIf{$|\delta| = 0$ and $|\delta'| = 1$} \Comment{Height increases, go on bottom-up updating.}
+    \ElsIf{$|\delta| = 0$ and $|\delta'| = 1$} \Comment{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$}
+    \ElsIf{$|\delta| = 1$ and $|\delta'| = 2$}
+      \If{$\delta'=2$}
+        \If{$\delta(R) = 1$} \Comment{Right-right case}
+          \State $\delta(P) \gets 0$ \Comment{By (\ref{eq:rr-result})}
+          \State $\delta(R) \gets 0$
+          \State $T \gets $ \Call{Left-Rotate}{$T, P$}
         \EndIf
-      \Else \Comment{$\delta' = -2$}
-        \If{$\delta(L) = 1$} \Comment{Left-Right case}
-          \State \Call{Left-Rotate}{$T, L$}
+        \If{$\delta(R) = -1$} \Comment{Right-left case}
+          \State $\delta_y \gets $ \textproc{$\delta$}(\Call{Left}{$R$}) \Comment{By (\ref{eq:rl-result})}
+          \If{$\delta_y = 1$}
+            \State $\delta(P) \gets -1$
+          \Else
+            \State $\delta(P) \gets 0$
+          \EndIf
+          \State \textproc{$\delta$}(\Call{Left}{$R$}) $\gets 0$
+          \If{$\delta_y = -1$}
+            \State $\delta(R) \gets 1$
+          \Else
+            \State $\delta(R) \gets 0$
+          \EndIf
+          \State $T \gets $ \Call{Right-Rotate}{$T, R$}
+          \State $T \gets $ \Call{Left-Rotate}{$T, P$}
+        \EndIf
+      \EndIf
+      \If{$\delta' = -2$}
+        \If{$\delta(L) = -1$} \Comment{Left-left case}
+          \State $\delta(P) \gets 0$ 
+          \State $\delta(L) \gets 0$
           \State \Call{Right-Rotate}{$T, P$}
-        \Else \Comment{$\delta(L) = -1$, Left-Left case}
+        \Else \Comment{Left-Right case}
+          \State $\delta_y \gets $ \textproc{$\delta$}(\Call{Right}{$L$})
+          \If{$\delta_y = 1$}
+            \State $\delta(L) \gets -1$
+          \Else
+            \State $\delta(L) \gets 0$
+          \EndIf
+          \State \textproc{$\delta$}(\Call{Right}{$L$}) $\gets 0$
+          \If{$\delta_y = -1$}
+            \State $\delta(P) \gets 1$
+          \Else
+            \State $\delta(P) \gets 0$
+          \EndIf
+          \State \Call{Left-Rotate}{$T, L$}
           \State \Call{Right-Rotate}{$T, P$}
-          \State \Call{Right-Rotate}{$T, L$}
         \EndIf
       \EndIf
+      \State break
     \EndIf
   \EndWhile
   \State \Return $T$
 \EndFunction
 \end{algorithmic}
 
+Here we reuse the rotation algorithms mentioned in red-black tree chapter.
+Rotation operation doesn't update balancing factor $\delta$ at all,
+However, since rotation changes (actually improves) the balance situation
+we should update these factors. Here we refer the results from above section. Among the four cases, right-right case and left-left case only need one rotation, while right-left case and left-right case need two rotations.
+
+The relative python program is shown as the following.
+
+\begin{lstlisting}
+def avl_insert_fix(t, x):
+    while x.parent is not None:
+        d2 = d1 = x.parent.delta
+        if x == x.parent.left:
+            d2 = d2 - 1
+        else:
+            d2 = d2 + 1
+        x.parent.delta = d2
+        (p, l, r) = (x.parent, x.parent.left, x.parent.right)
+        if abs(d1) == 1 and abs(d2) == 0:
+            return t
+        elif abs(d1) == 0 and abs(d2) == 1:
+            x = x.parent
+        elif abs(d1)==1 and abs(d2) == 2:
+            if d2 == 2:
+                if r.delta == 1:  # Right-right case
+                    p.delta = 0
+                    r.delta = 0
+                    t = left_rotate(t, p)
+                if r.delta == -1: # Right-Left case
+                    dy = r.left.delta
+                    if dy == 1: 
+                        p.delta = -1
+                    else:
+                        p.delta = 0
+                    r.left.delta = 0
+                    if dy == -1:
+                        r.delta = 1
+                    else:
+                        r.delta = 0
+                    t = right_rotate(t, r)
+                    t = left_rotate(t, p)
+            if d2 == -2:
+                if l.delta == -1: # Left-left case
+                    p.delta = 0
+                    l.delta = 0
+                    t = right_rotate(t, p)
+                if l.delta == 1: # Left-right case
+                    dy = l.right.delta
+                    if dy == 1:
+                        l.delta = -1
+                    else:
+                        l.delta = 0
+                    l.right.delta = 0
+                    if dy == -1:
+                        p.delta = 1
+                    else:
+                        p.delta = 0
+                    t = left_rotate(t, l)
+                    t = right_rotate(t, p)
+            break
+    return t
+\end{lstlisting}
+
+We skip the AVL tree deletion algorithm and left this as an exercise to the reader.
+
 \section{Chapter note}
 AVL tree was invented in 1962 by Adelson-Velskii and Landis\cite{wiki}, 
-\cite{TFATP}. The name AVL tree comes from the two inventors's name.
+\cite{TFATP}. The name AVL tree comes from the two inventors's name. It's earlier than red-black tree.
+
+It's very common to compare AVL tree and red-black tree, both are self-balancing binary search trees, and for all the major operations, they both consume $O(\lg N)$ time. From the result of (\ref{eq:AVL-height}), AVL tree is more rigidly balanced hence they are faster than red-black tree in looking up intensive applications \cite{wiki}. However, red-blackt trees could perform better in frequently insertion and removal cases.
 
-TODO: compare with Red-black tree.
+Many popular self-balancing binary search tree libraries are implemented on top of red-black tree such as STL etc. However, AVL tree provides an intuitive and effective solution to the balance problem as well.
 
-  TODO: short summary and introduction to the following chatpers.
+After this chapter we'll extend the tree data structure from storing data in node to stroing information on edges, which leads to Trie and Patrica, etc. If we extend the number of children from two to multiple cases, we can get B-tree. These data structures will be introduced next.
 
 \begin{thebibliography}{99}