Skip to content

Commit

Permalink
AVL tree latex: figures of 4 cases added.
Browse files Browse the repository at this point in the history
  • Loading branch information
@liuxinyu95
liuxinyu95 committed Aug 8, 2011
1 parent a213188 commit ee70ffc
Show file tree
Hide file tree
Showing 8 changed files with 345 additions and 3 deletions.
79 changes: 78 additions & 1 deletion datastruct/tree/AVL-tree/avltree-en.tex
View file
Original file line number Diff line number Diff line change
Expand Up @@ -425,7 +425,84 @@ \subsection{Balancing adjustment}
As the pattern matching approach is adopted in doing rebalancing.
We need consider what kind of patterns violate the AVL tree property.

TODO: add figures here.
Figure \ref{fig:insert-fix} shows the 4 cases which need fix. For all
these 4 cases the balacing factors are either -2, or +2 which exceed
the range of $[-1, 1]$. After balancing adjustment, this factor turns
to be 0, which means the height of left sub tree is equal to the right
sub tree.

\begin{figure}[htbp]
\begin{center}
\setlength{\unitlength}{1cm}
\begin{picture}(15, 15)
% arrows
\put(4.5, 9.5){\vector(1, -1){1}}
\put(4.5, 5){\vector(1, 1){1}}
\put(10, 9.5){\vector(-1, -1){1}}
\put(10, 5){\vector(-1, 1){1}}
% delta values
\put(5, 13){$\delta(z) = -2$}
\put(2.5, 12){$\delta(y) = -1$}
\put(10, 13){$\delta(x) = 2$}
\put(11.5, 11.5){$\delta(y) = 1$}
\put(1.5, 5.5){$\delta(z) = -2$}
\put(3.5, 4){$\delta(x) = 1$}
\put(12, 5.5){$\delta(x) = 2$}
\put(10.5, 4){$\delta(z) = -1$}
\put(7.5, 10){$\delta'(y) = 0$}
% graphics
\put(0, 7){\includegraphics[scale=0.5]{img/insert-ll.ps}}
\put(0, 0){\includegraphics[scale=0.5]{img/insert-lr.ps}}
\put(7, 7){\includegraphics[scale=0.5]{img/insert-rr.ps}}
\put(8.5, 0){\includegraphics[scale=0.5]{img/insert-rl.ps}}
\put(2, 5){\includegraphics[scale=0.5]{img/insert-fixed.ps}}
\end{picture}
\caption{4 cases for balancing a AVL tree after insertion} \label{fig:insert-fix}
\end{center}
\end{figure}

We call these four cases left-left lean, right-right lean, right-left lean,
and left-right lean cases in clock-wise direction from top-left. We denote
the balancing factor before fixing as $\delta(x), \delta(y)$, and $\delta(z)$, while after fixing, they changes to $\delta'(x), \delta'(y)$, and
$\delta'(z)$ respectively.

We'll next prove that, after fixing, we have $\delta(y)=0$ for all
four cases, and we'll provide the result values of $\delta'(x)$ and
$\delta'(z)$.

\subsubsection*{Left-left lean case}

As the structure of sub tree $x$ doesn't change due to fixing, we immediately get
$\delta'(x) = \delta(x)$.

Since $\delta(y) = -1$ and $\delta(z) = -2$, we have

\be
\begin{array}{l}
\delta(y) = |C| - |x| = -1 \Rightarrow |C| = |x| - 1 \\
\delta(z) = |D| - |y| = -2 \Rightarrow |D| = |y| - 2
\end{array}
\label{eq:ll-cd}
\ee

After fixing.

\be
\begin{array}{rll}
\delta'(z) & = |D| - |C| & \{ From (\ref{eq:ll-cd}) \}\\
& = |y| - 2 - (|x| - 1) & \\
& = |y| - |x| - 1 & \{ x \text{ is child of } y \Rightarrow |y|-|x| = 1\} \\
& = 1 - 1 & = 0
\end{array}
\ee

TODO: prove $\delta'(y) = 0$

\subsubsection*{Right-right lean case}

\subsubsection*{Right-left lean case}

\subsubsection*{Left-right lean case}

TODO:
Traditional insertion
Expand Down
2 changes: 1 addition & 1 deletion datastruct/tree/AVL-tree/img/Makefile
View file
Original file line number Diff line number Diff line change
@@ -1,5 +1,5 @@
IMG_OBJECTS =
DOT_OBJECTS = Nh-lvr
DOT_OBJECTS = Nh-lvr insert-ll insert-lr insert-rl insert-rr insert-fixed
DOT_SOURCES = $(foreach file, $(DOT_OBJECTS), $(file).dot)

#suffix replacement, replace .dot with .png
Expand Down
53 changes: 53 additions & 0 deletions datastruct/tree/AVL-tree/img/insert-fixed.dot
View file
Original file line number Diff line number Diff line change
@@ -0,0 +1,53 @@
digraph G{
node[shape=circle]
ay[label="y", style=filled, fillcolor=white, fontcolor=black];
ax[label="x", style=filled, fillcolor=white, fontcolor=black];
aA[label="A", style=filled, color=white];
nilaAl[label="", style=invis];
nilaAr[label="", style=invis];
nilaAm[label="", style=invis];
aA->nilaAl[style=invis];
aA->nilaAm[style=invis];
aA->nilaAr[style=invis];
{rank=same nilaAl->nilaAm->nilaAr[style=invis]}
aB[label="B", style=filled, color=white];
nilaBl[label="", style=invis];
nilaBr[label="", style=invis];
nilaBm[label="", style=invis];
aB->nilaBl[style=invis];
aB->nilaBm[style=invis];
aB->nilaBr[style=invis];
{rank=same nilaBl->nilaBm->nilaBr[style=invis]}
nilaxm[label="", style=invis];
ax->aA
ax->nilaxm[style=invis];
ax->aB
{rank=same aA->nilaxm->aB[style=invis]}
az[label="z", style=filled, fillcolor=white, fontcolor=black];
aC[label="C", style=filled, color=white];
nilaCl[label="", style=invis];
nilaCr[label="", style=invis];
nilaCm[label="", style=invis];
aC->nilaCl[style=invis];
aC->nilaCm[style=invis];
aC->nilaCr[style=invis];
{rank=same nilaCl->nilaCm->nilaCr[style=invis]}
aD[label="D", style=filled, color=white];
nilaDl[label="", style=invis];
nilaDr[label="", style=invis];
nilaDm[label="", style=invis];
aD->nilaDl[style=invis];
aD->nilaDm[style=invis];
aD->nilaDr[style=invis];
{rank=same nilaDl->nilaDm->nilaDr[style=invis]}
nilazm[label="", style=invis];
az->aC
az->nilazm[style=invis];
az->aD
{rank=same aC->nilazm->aD[style=invis]}
nilaym[label="", style=invis];
ay->ax
ay->nilaym[style=invis];
ay->az
{rank=same ax->nilaym->az[style=invis]}
}
53 changes: 53 additions & 0 deletions datastruct/tree/AVL-tree/img/insert-ll.dot
View file
Original file line number Diff line number Diff line change
@@ -0,0 +1,53 @@
digraph G{
node[shape=circle]
az[label="z", style=filled, fillcolor=white, fontcolor=black];
ay[label="y", style=filled, fillcolor=white, fontcolor=black];
ax[label="x", style=filled, fillcolor=white, fontcolor=black];
aA[label="A", style=filled, color=white];
nilaAl[label="", style=invis];
nilaAr[label="", style=invis];
nilaAm[label="", style=invis];
aA->nilaAl[style=invis];
aA->nilaAm[style=invis];
aA->nilaAr[style=invis];
{rank=same nilaAl->nilaAm->nilaAr[style=invis]}
aB[label="B", style=filled, color=white];
nilaBl[label="", style=invis];
nilaBr[label="", style=invis];
nilaBm[label="", style=invis];
aB->nilaBl[style=invis];
aB->nilaBm[style=invis];
aB->nilaBr[style=invis];
{rank=same nilaBl->nilaBm->nilaBr[style=invis]}
nilaxm[label="", style=invis];
ax->aA
ax->nilaxm[style=invis];
ax->aB
{rank=same aA->nilaxm->aB[style=invis]}
aC[label="C", style=filled, color=white];
nilaCl[label="", style=invis];
nilaCr[label="", style=invis];
nilaCm[label="", style=invis];
aC->nilaCl[style=invis];
aC->nilaCm[style=invis];
aC->nilaCr[style=invis];
{rank=same nilaCl->nilaCm->nilaCr[style=invis]}
nilaym[label="", style=invis];
ay->ax
ay->nilaym[style=invis];
ay->aC
{rank=same ax->nilaym->aC[style=invis]}
aD[label="D", style=filled, color=white];
nilaDl[label="", style=invis];
nilaDr[label="", style=invis];
nilaDm[label="", style=invis];
aD->nilaDl[style=invis];
aD->nilaDm[style=invis];
aD->nilaDr[style=invis];
{rank=same nilaDl->nilaDm->nilaDr[style=invis]}
nilazm[label="", style=invis];
az->ay
az->nilazm[style=invis];
az->aD
{rank=same ay->nilazm->aD[style=invis]}
}
53 changes: 53 additions & 0 deletions datastruct/tree/AVL-tree/img/insert-lr.dot
View file
Original file line number Diff line number Diff line change
@@ -0,0 +1,53 @@
digraph G{
node[shape=circle]
az[label="z", style=filled, fillcolor=white, fontcolor=black];
ax[label="x", style=filled, fillcolor=white, fontcolor=black];
aA[label="A", style=filled, color=white];
nilaAl[label="", style=invis];
nilaAr[label="", style=invis];
nilaAm[label="", style=invis];
aA->nilaAl[style=invis];
aA->nilaAm[style=invis];
aA->nilaAr[style=invis];
{rank=same nilaAl->nilaAm->nilaAr[style=invis]}
ay[label="y", style=filled, fillcolor=white, fontcolor=black];
aB[label="B", style=filled, color=white];
nilaBl[label="", style=invis];
nilaBr[label="", style=invis];
nilaBm[label="", style=invis];
aB->nilaBl[style=invis];
aB->nilaBm[style=invis];
aB->nilaBr[style=invis];
{rank=same nilaBl->nilaBm->nilaBr[style=invis]}
aC[label="C", style=filled, color=white];
nilaCl[label="", style=invis];
nilaCr[label="", style=invis];
nilaCm[label="", style=invis];
aC->nilaCl[style=invis];
aC->nilaCm[style=invis];
aC->nilaCr[style=invis];
{rank=same nilaCl->nilaCm->nilaCr[style=invis]}
nilaym[label="", style=invis];
ay->aB
ay->nilaym[style=invis];
ay->aC
{rank=same aB->nilaym->aC[style=invis]}
nilaxm[label="", style=invis];
ax->aA
ax->nilaxm[style=invis];
ax->ay
{rank=same aA->nilaxm->ay[style=invis]}
aD[label="D", style=filled, color=white];
nilaDl[label="", style=invis];
nilaDr[label="", style=invis];
nilaDm[label="", style=invis];
aD->nilaDl[style=invis];
aD->nilaDm[style=invis];
aD->nilaDr[style=invis];
{rank=same nilaDl->nilaDm->nilaDr[style=invis]}
nilazm[label="", style=invis];
az->ax
az->nilazm[style=invis];
az->aD
{rank=same ax->nilazm->aD[style=invis]}
}
53 changes: 53 additions & 0 deletions datastruct/tree/AVL-tree/img/insert-rl.dot
View file
Original file line number Diff line number Diff line change
@@ -0,0 +1,53 @@
digraph G{
node[shape=circle]
ax[label="x", style=filled, fillcolor=white, fontcolor=black];
aA[label="A", style=filled, color=white];
nilaAl[label="", style=invis];
nilaAr[label="", style=invis];
nilaAm[label="", style=invis];
aA->nilaAl[style=invis];
aA->nilaAm[style=invis];
aA->nilaAr[style=invis];
{rank=same nilaAl->nilaAm->nilaAr[style=invis]}
az[label="z", style=filled, fillcolor=white, fontcolor=black];
ay[label="y", style=filled, fillcolor=white, fontcolor=black];
aB[label="B", style=filled, color=white];
nilaBl[label="", style=invis];
nilaBr[label="", style=invis];
nilaBm[label="", style=invis];
aB->nilaBl[style=invis];
aB->nilaBm[style=invis];
aB->nilaBr[style=invis];
{rank=same nilaBl->nilaBm->nilaBr[style=invis]}
aC[label="C", style=filled, color=white];
nilaCl[label="", style=invis];
nilaCr[label="", style=invis];
nilaCm[label="", style=invis];
aC->nilaCl[style=invis];
aC->nilaCm[style=invis];
aC->nilaCr[style=invis];
{rank=same nilaCl->nilaCm->nilaCr[style=invis]}
nilaym[label="", style=invis];
ay->aB
ay->nilaym[style=invis];
ay->aC
{rank=same aB->nilaym->aC[style=invis]}
aD[label="D", style=filled, color=white];
nilaDl[label="", style=invis];
nilaDr[label="", style=invis];
nilaDm[label="", style=invis];
aD->nilaDl[style=invis];
aD->nilaDm[style=invis];
aD->nilaDr[style=invis];
{rank=same nilaDl->nilaDm->nilaDr[style=invis]}
nilazm[label="", style=invis];
az->ay
az->nilazm[style=invis];
az->aD
{rank=same ay->nilazm->aD[style=invis]}
nilaxm[label="", style=invis];
ax->aA
ax->nilaxm[style=invis];
ax->az
{rank=same aA->nilaxm->az[style=invis]}
}
53 changes: 53 additions & 0 deletions datastruct/tree/AVL-tree/img/insert-rr.dot
View file
Original file line number Diff line number Diff line change
@@ -0,0 +1,53 @@
digraph G{
node[shape=circle]
ax[label="x", style=filled, fillcolor=white, fontcolor=black];
aA[label="A", style=filled, color=white];
nilaAl[label="", style=invis];
nilaAr[label="", style=invis];
nilaAm[label="", style=invis];
aA->nilaAl[style=invis];
aA->nilaAm[style=invis];
aA->nilaAr[style=invis];
{rank=same nilaAl->nilaAm->nilaAr[style=invis]}
ay[label="y", style=filled, fillcolor=white, fontcolor=black];
aB[label="B", style=filled, color=white];
nilaBl[label="", style=invis];
nilaBr[label="", style=invis];
nilaBm[label="", style=invis];
aB->nilaBl[style=invis];
aB->nilaBm[style=invis];
aB->nilaBr[style=invis];
{rank=same nilaBl->nilaBm->nilaBr[style=invis]}
az[label="z", style=filled, fillcolor=white, fontcolor=black];
aC[label="C", style=filled, color=white];
nilaCl[label="", style=invis];
nilaCr[label="", style=invis];
nilaCm[label="", style=invis];
aC->nilaCl[style=invis];
aC->nilaCm[style=invis];
aC->nilaCr[style=invis];
{rank=same nilaCl->nilaCm->nilaCr[style=invis]}
aD[label="D", style=filled, color=white];
nilaDl[label="", style=invis];
nilaDr[label="", style=invis];
nilaDm[label="", style=invis];
aD->nilaDl[style=invis];
aD->nilaDm[style=invis];
aD->nilaDr[style=invis];
{rank=same nilaDl->nilaDm->nilaDr[style=invis]}
nilazm[label="", style=invis];
az->aC
az->nilazm[style=invis];
az->aD
{rank=same aC->nilazm->aD[style=invis]}
nilaym[label="", style=invis];
ay->aB
ay->nilaym[style=invis];
ay->az
{rank=same aB->nilaym->az[style=invis]}
nilaxm[label="", style=invis];
ax->aA
ax->nilaxm[style=invis];
ax->ay
{rank=same aA->nilaxm->ay[style=invis]}
}
2 changes: 1 addition & 1 deletion datastruct/tree/red-black-tree/rbtree-en.tex
View file
Original file line number Diff line number Diff line change
Expand Up @@ -404,7 +404,7 @@ \section{Insertion}
\put(0, 7){\includegraphics[scale=0.5]{img/insert-ll.ps}}
\put(0, 0){\includegraphics[scale=0.5]{img/insert-lr.ps}}
\put(7, 7){\includegraphics[scale=0.5]{img/insert-rr.ps}}
\put(8.5, 0){\includegraphics[scale=0.5]{img/insert-rl.ps}}
\put(7.5, 0){\includegraphics[scale=0.5]{img/insert-rl.ps}}
\put(2, 5){\includegraphics[scale=0.5]{img/insert-fixed.ps}}
\end{picture}
\caption{4 cases for balancing a red-black tree after insertion} \label{fig:insert-fix}
Expand Down

0 comments on commit ee70ffc

Please sign in to comment.