\documentclass[11pt]{article}

\usepackage{fullpage} % to save some trees
\usepackage{hyperref} % for links within document
\usepackage{amsmath,amssymb} % general-purpose useful
\usepackage{ifthen} % for if-then-else inside tikz
\usepackage{xcolor,colortbl} % needed for coloring table entries

\usepackage{tikz}
%\usetikzlibrary{positioning,fit,shadows,trees}
\usetikzlibrary{calc} % for numerous calculations within tikz
\usetikzlibrary{shapes} % for split circles etc.
\usetikzlibrary{chains} % for lists and arrays and such
\usetikzlibrary{arrows} % for interesting arrow decorations
\usetikzlibrary{patterns} % for shading rectangles in interesting ways
\usetikzlibrary{automata} % for DFA-automata and the like
\usetikzlibrary{shadows,fit} % the EMM picture uses these for special illustration

\title{Some figures from the cs240 textbook}
\author{T. Biedl}

\begin{document}
\maketitle
\begin{abstract}
This is a list of figures from the textbook, with the express intent on making the latex available so students can use similar styles.
Disclaimer: The {\tt tikz} used for these figures ranges from "absolute
hack" to "using advanced features" (many different instructors have
contributed to them over the years). No claims are made that this is
the most elegant way to get the picture, but at least it should work.
\end{abstract}

\listoffigures

\newpage
\begin{figure}[ht]
\hspace*{\fill}
\begin{minipage}{0.4\linewidth}
\begin{tikzpicture}
      \draw[->] (-0.5,0) -- (4.2,0) node[right] {$n$};
      \draw[->] (0,-0.5) -- (0,4.2) node[above] {$y$};
      \draw[scale=0.5,domain=0:6,smooth,variable=\x,blue] plot ({\x},{0.2*\x*\x}); 
      \draw[scale=0.5,domain=0:3,smooth,variable=\y,red,dashed]  plot ({\y*\y},{\y});

      \draw[dotted] (1.7,0) node[below] {$n_0$} -- (1.5,4);
      \node[right,color=blue] at (3,4) {$g(n)=n^2$};
      \node[right,color=red] at (3,1) {$f(n)=\sqrt{n}$};
\end{tikzpicture}
\end{minipage}
\hspace*{\fill}
\begin{minipage}{0.55\linewidth}
\begin{tikzpicture}[scale=0.2]
      \draw[->] (-0.5,0) -- (24,0) node[right] {$n$};
      \draw[->] (0,-0.5) -- (0,20) node[above] {$y$};
      \draw[domain=0:23,smooth,variable=\x,blue] plot ({\x},{0.015*\x*\x}); 
      \draw[domain=0:23,smooth,variable=\x,blue,thick,dotted] plot ({\x},{0.044*\x*\x}); 
      \draw[domain=0:23,smooth,variable=\x,red,dashed] plot ({\x},{0.03*\x*\x+0.15*\x}); 
      \draw[dotted] (15,0) node[below] {$n_0$} -- (15,20);
      \node[right,color=blue] at (23.5,9) {$g(n)=n^2$};
      \node[right,color=blue] at (23.5,24) {$3\cdot g(n)$};
      \node[right,color=red] at (23.5,19) {$f(n)=2n^2+10n$};
\end{tikzpicture}
\end{minipage}
\caption{Two function graphs.}
\end{figure}


\begin{figure}[ht] \centering
\begin{tikzpicture}[
list/.style={rectangle split, rectangle split parts=2, draw, rectangle split horizontal}, >=stealth, start chain
]

\node[on chain,rectangle split, rectangle split parts=2,rectangle split horizontal] (h) {$P$:};
\node[list,on chain] (A) {12};
\node[list,on chain] (B) {99};
\node[list,on chain] (C) {37};
\draw[*->] let \p1 = (h.two), \p2 = (h.center) in (\x1,\y2) -- (A);
\draw[*->] let \p1 = (A.two), \p2 = (A.center) in (\x1,\y2) -- (B);
\draw[*->] let \p1 = (B.two), \p2 = (B.center) in (\x1,\y2) -- (C);
\node[on chain] {{\it size}: 3};
\end{tikzpicture}
\caption{A list.}
\end{figure}

\begin{figure}[ht] \centering
\begin{tikzpicture}[
list/.style={rectangle, draw, minimum width=2em, minimum height=14pt}, >=stealth, start chain,node distance=-0.5pt,
every label/.style={draw=none,minimum width=0pt,text=blue,font=\tt\footnotesize},
label distance=0mm,
]
\node[on chain] (h) {$P$:};
\node[on chain] (h) {};
\node[list,right=20pt,on chain,label={above:0}] (A) {12};
\node[list,on chain,label={above:1}] (B) {99};
\node[list,on chain,label={above:2}] (C) {37};
\node[list,on chain,label={above:3}] (D) {};
\node[list,on chain,label={above:4}] (E) {};
\node[on chain,right=10pt] {{\it size}: 3};
\end{tikzpicture}
\caption{An array.}
\end{figure}

\begin{figure}[ht] \centering
\begin{tikzpicture}[level distance=32pt,
every node/.style={circle,draw,inner sep=1pt, minimum size=2em},
dummy/.style={rectangle,draw=none,minimum width=1em},
level 1/.style={sibling distance=128pt},
level 2/.style={sibling distance=64pt},
level 3/.style={sibling distance=32pt},
level 4/.style={sibling distance=16pt}
]
\node {50}
    child {node {29} 
        child {node {27}
            child {node {23} 
                child {node[dummy] {$\emptyset$}}
                child {node[dummy] {$\emptyset$}}
            }
            child {node {26} 
                child {node[dummy] {$\emptyset$}}
                child {node[dummy] {$\emptyset$}}
            }
        }
        child {node {15}
            child {node[dummy] {$\emptyset$}}
            child {node[dummy] {$\emptyset$}}
        }
    }
    child {node {34}
        child {node {8}
            child {node[dummy] {$\emptyset$}}
            child {node[dummy] {$\emptyset$}}
        }
        child {node {10}
            child {node[dummy] {$\emptyset$}}
            child {node[dummy] {$\emptyset$}}
        }
    }
;
\end{tikzpicture}
\caption{A binary tree.  Style also useful for heaps and binary search trees.} 
\end{figure}

\begin{figure}[ht] \centering
  \begin{tikzpicture}[level distance=32pt,
    every node/.style={circle,draw,inner sep=2pt, minimum size=2em},
    chain node/.style={rectangle,draw,minimum width=10mm,minimum height=6mm},
    level 1/.style={sibling distance=50pt},
    level 2/.style={sibling distance=40pt},
    level 3/.style={sibling distance=30pt},
    start chain=going right,node distance=-1pt,
    every label/.style={draw=none,minimum width=0pt,text=blue,font=\tt\footnotesize},
    label distance=0mm
]
\node[chain node,on chain,label={above:0}] (0) {$\bullet$};
\node[chain node,on chain,label={above:1}] {};
\node[chain node,on chain,label={above:2}] (2) {$\bullet$};
\node[chain node,on chain,label={above:3}] (3) {$\bullet$};
\node[chain node,on chain,label={above:4}] (4) {};
\node [left=10pt of 0,draw=none] (B) {$B:$};


\node [below=20pt of B] (r2) {12};
\node [right=50pt of r2] (r1) {19}
    child {node {8}
        child {node {5}}
        child {node {10}}
    }
    child {edge from parent[draw=none]}
;
\node [right=70pt of r1,fill=white] (r3) {18}
    child {node {14}
        child {node [left=2pt] {11}
            child {node {7}}
            child {node {4}}
        }
        child {node [right=2pt] {15} 
            child {node {13}}
            child {node {6}}
        }
    }
    child {edge from parent[draw=none]}
;
\draw[>=stealth,->,dotted] (0.center)--(r2);
\draw[>=stealth,->,dotted] (2.center)--(r1);
\draw[>=stealth,->,dotted] (3.center)--(r3);
\end{tikzpicture}
\caption{A binomial heap.}
\end{figure}

\begin{figure}[ht] \centering
\begin{tikzpicture}[level distance=32pt,
every node/.style={rounded rectangle,draw,font=\footnotesize,inner sep=2pt, minimum width=3em},
starred/.style={rounded rectangle,thick, draw,label=right:{\hspace*{-7mm}*},font=\footnotesize,inner sep=2pt, minimum width=3em},
level 1/.style={sibling distance=60pt},
level 2/.style={sibling distance=90pt},
level 3/.style={sibling distance=80pt},
level 4/.style={sibling distance=60pt}
]
\node (r2) {$n$}
    child {node {$n_1\leq n/2$}
        child {node [dashed] {returned} }
        child {node {$n_2 \leq n_1\leq n/2$} 
            child {node [starred] {$\geq (n_2{-}1)/2$} }
            child {node {$n_3 \leq n_2/2 \leq n/4$} 
                child {node [draw=none] {}  }
                child {node [draw=none] {}  }
            }
        }
    }
    child {node [starred] {$\geq (n{-}1)/2$} }
;
\end{tikzpicture}
\caption{A recursion tree.}
\end{figure}

\begin{figure}[ht] \centering
\begin{tikzpicture}[
    xscale=.05,yscale=.06,
    auto,semithick,
    every node/.style={font=\footnotesize},
    cmp/.style={rectangle,draw,rounded corners=7pt,fill=blue!10},
    perms/.style={font=\tiny,align=center,fill=black!10},
    leaf/.style={rectangle,draw,fill=red!10},
]

\node[cmp]  (0)  at (0,100) {$x_0 : x_1$};
\node[cmp]  (10) at (-60,70) {$x_1 : x_2$};
\node[cmp]  (11) at ( 60,70) {$x_1 : x_2$};
\node[cmp]  (20) at (-36,40) {$x_0 : x_2$};
\node[cmp]  (21) at ( 36,40) {$x_0 : x_2$};
\node[leaf] (l0) at (-95,40) {0,1,2};
\node[perms,below= 4pt] at (l0.south) {$x_0{<}x_1{<}x_2$};
\node[leaf] (l5) at ( 95,40) {2,1,0};
\node[perms,below= 4pt] at (l5.south) {$x_2{\leq}x_1{\leq}x_0$};
\node[leaf] (l1) at (-55,10) {0,2,1};
\node[perms,below= 4pt] at (l1.south) {$x_0{<}x_2{\leq}x_1$};
\node[leaf] (l2) at (-17,10) {2,0,1};
\node[perms,below= 4pt] at (l2.south) {$x_2{\leq}x_0{\leq}x_1$};
\node[leaf] (l3) at ( 17,10) {1,0,2};
\node[perms,below= 4pt] at (l3.south) {$x_1{\leq}x_0{<}x_2$};
\node[leaf] (l4) at ( 55,10) {1,2,0};
\node[perms,below= 4pt] at (l4.south) {$x_1{<}x_2{\leq}x_0$};


\draw (0)  to node[swap]{$<$} (10) ;
\draw (0)  to node      {$\ge$}   (11) ;
\draw (10) to node[swap]{$<$} (l0) ;
\draw (10) to node      {$\ge$}   (20) ;
\draw (20) to node[swap]{$<$} (l1) ;
\draw (20) to node      {$\ge$}   (l2) ;
\draw (11) to node      {$\ge$}   (l5) ;
\draw (11) to node[swap]{$<$} (21) ;
\draw (21) to node[swap]{$<$} (l3) ;
\draw (21) to node      {$\ge$}   (l4) ;

\node[perms,below= 10pt] (p0) at (0) {$x_0{\leq} x_1{\leq} x_2$\\$x_0{\leq} x_2{\leq} x_1$\\$x_1{\leq}x_0{\leq}x_2$\\$x_1{\leq}x_2{\leq}x_0$\\$x_2{\leq}x_0{\leq}x_1$\\$x_2{\leq}x_1{\leq}x_0$};
\node[perms,above left= 1pt] (p10) at (10.north west) {$x_0{<}x_1{\leq}x_2$\\$x_0{\leq}x_2{\leq}x_1$\\$x_2{\leq}x_0{<}x_1$};
\node[perms,above right= 1pt] (p11) at (11.north east) {$x_1{\leq}x_0{\leq}x_2$\\$x_1{\leq}x_2{\leq}x_0$\\$x_2{\leq}x_1{\leq}x_0$};
\node[perms,above right= 4pt] (p20) at (20.north) {$x_0{\leq}x_2{\leq}x_1$\\$x_2{\leq}x_0{<}x_1$};
\node[perms,above left= 4pt] (p21) at (21.north) {$x_1{\leq}x_0{\leq}x_2$\\$x_1{<}x_2{\leq}x_0$};

\end{tikzpicture}
\caption{A decision tree.}
\end{figure}

\begin{figure}[ht] \centering
\begin{tikzpicture}
  [
    grow'                    = right,
    scale =            0.9,
    sibling distance        = 3em,
        level 1/.style={sibling distance=5em},
        level 2/.style={sibling distance=3em},
    level distance          = 8em,
    edge from parent/.style = {draw, -latex},
    every node/.style       = {font=\footnotesize},
    array/.style={rectangle,draw,inner sep=-0.5,minimum width=12mm},
    sloped
  ]
\node (r) [array] 
        { \begin{tabular}{c}\underline{1}23 \\ \hline \underline{2}32 \\  \hline \underline{0}21 \\ \hline \underline{3}20 \\ \hline \underline{2}10 \\ \hline \underline{2}30 \\ \hline \underline{1}01 \end{tabular} }
    child { node [below=0.8em,fill=green,array] 
        { \begin{tabular}{c}021 \end{tabular} } 
    edge from parent [edge from parent path={(\tikzparentnode)--(\tikzchildnode.west)}] node[above] {0}
    }
    child { node [array] 
        { \begin{tabular}{c}1\underline{2}3 \\ \hline 1\underline{0}1 \end{tabular} }
        child { node [fill=green,array] 
            { \begin{tabular}{c}101 \end{tabular} } 
                edge from parent [edge from parent path={(\tikzparentnode)--(\tikzchildnode.west)}]  node[above] {0}
        }
        child { node [fill=green,array] 
            { \begin{tabular}{c}123 \end{tabular} } 
        edge from parent [edge from parent path={(\tikzparentnode)--(\tikzchildnode.west)}] node[above] {2}
        }
    edge from parent [edge from parent path={(\tikzparentnode)--(\tikzchildnode.west)}] node[above] {1}
    } 
    child { node [array] 
        { \begin{tabular}{c}2\underline{3}2 \\ \hline 2\underline{1}0 \\ \hline 2\underline{3}0 \end{tabular} }
        child { node [fill=green,array] 
            { \begin{tabular}{c}210 \end{tabular} } 
        edge from parent [edge from parent path={(\tikzparentnode)--(\tikzchildnode.west)}] node[above] {1}
        }
        child { node [array] 
            { \begin{tabular}{c}23\underline{2} \\ \hline 23\underline{0} \end{tabular} } 
            child { node [fill=green,array] 
                { \begin{tabular}{c}230 \end{tabular} } 
            edge from parent [edge from parent path={(\tikzparentnode)--(\tikzchildnode.west)}] node[above] {1}
            }
            child { node [fill=green,array] 
                { \begin{tabular}{c}232 \end{tabular} } 
            edge from parent [edge from parent path={(\tikzparentnode)--(\tikzchildnode.west)}] node[above] {3}
            }
        edge from parent [edge from parent path={(\tikzparentnode)--(\tikzchildnode.west)}] node[above] {3}
        }
    edge from parent [edge from parent path={(\tikzparentnode)--(\tikzchildnode.west)}] node[above] {2}
    } 
    child { node [above=0.5em,fill=green,array] 
        { \begin{tabular}{c}320 \end{tabular} } 
    edge from parent [edge from parent path={(\tikzparentnode)--(\tikzchildnode.west)}]  node[above] {3}
    }
;
\end{tikzpicture}
\caption{An trace of MSD radix sort.}
\end{figure}


\begin{figure}[ht] \centering
\begin{tikzpicture}[level distance=48pt,scale=.7,
every node/.style={font=\small,circle split,draw,inner sep=2pt},
level 1/.style={sibling distance=130pt},
level 2/.style={sibling distance=80pt},
level 3/.style={sibling distance=40pt},
level 4/.style={sibling distance=40pt},
every lower node part/.style={blue}]
\node {22\nodepart{lower}4}
    child {node {10\nodepart{lower}3}
        child {node {4\nodepart{lower}1}
            child {edge from parent[draw=none]}
            child {node {6\nodepart{lower}0}}
        }
        child {node {14\nodepart{lower}2}
            child {node {13\nodepart{lower}0}}
            child {node {18\nodepart{lower}1}
                child {node {16\nodepart{lower}0}}
                child {edge from parent[draw=none]}
            }
        }
    }
    child {node (b) {31\nodepart{lower}2}
        child {node {28\nodepart{lower}0}}
        child {node {37\nodepart{lower}1}
            child {edge from parent[draw=none]}
            child {node {46\nodepart{lower}0}}
        }
    }
;
\end{tikzpicture}
\caption{An AVL-tree.  Style also useful for scapegoat trees and treaps.}
\end{figure}

\begin{figure}[ht] \centering
\begin{tikzpicture}[level distance=32pt,
every node/.style={circle,draw,minimum size=20pt},
level 1/.style={sibling distance=64pt},
level 2/.style={sibling distance=64pt},
level 3/.style={sibling distance=32pt},
subtree/.style={ isosceles triangle, shape border rotate=90, anchor=apex, minimum width=25pt },
to subtree/.style={ edge from parent path={(\tikzparentnode) -- (\tikzchildnode.north)}}]
\node (a) {$z$} %[child anchor=center]
    child{node {$y$}
        child{node {$x$}
            child{node [subtree] {$A$}
            edge from parent[to subtree] 
            }
            child{node [subtree] {$B$}
            edge from parent[to subtree] 
            }
        }
        child{node [subtree] {$C$}
        edge from parent[to subtree] 
        }
    }
    child{node [subtree] (e) {$D$}
    edge from parent[to subtree] 
    }
;
\tikzset{level 2/.style={sibling distance=32pt}}
\node [right=150pt of a] (b) {$y$} 
    child{node {$x$}
        child{node [subtree] {$A$}
        edge from parent[to subtree] 
        }
        child{node [subtree] {$B$}
        edge from parent[to subtree] 
        }
    }
    child{node (c) {$z$}
        child{node [subtree] (d) {$C$}
        edge from parent[to subtree] 
        }
        child{node [subtree] {$D$}
        edge from parent[to subtree] 
        }
    }
;
\coordinate [right=30pt of e.north] (arrl);
\draw[thick,->] (arrl) arc (180:0:20pt);
\end{tikzpicture}
\caption{A right rotation.} 
\end{figure}

\begin{figure}[ht] \centering
\begin{tikzpicture}[line width=0.5pt,
   start chain=going right,node distance=5pt,
   every node/.style={draw,minimum width=4.5ex,font=\scriptsize,minimum height=2ex,inner sep=1pt},
   chainnode/.style={draw,minimum width=1cm,minimum height=4mm},
   every join/.style={->},
  every label/.style={draw=none,minimum width=0pt,text=blue,font=\tt\footnotesize},
  label distance=0mm]
%%%%%%%%%%% layer S0 %%%%%%%%
  \node[on chain,join,label={left:$S_0$}] (l-0) {$-\infty$};
    \node[on chain,join] (23) {(23,v)}; 
    \node[on chain,join] (37) {(37,v)};
    \node[on chain,join] (44) {(44,v)};
    \node[on chain,join] (65) {(65,v)};
    \node[on chain,join] (69) {(69,v)};
    \node[on chain,join] (79) {(79,v)};
    \node[on chain,join] (83) {(83,v)};
    \node[on chain,join] (87) {(87,v)};
    \node[on chain,join] (94) {(94,v)};
    \node[on chain,join] (r-0) {$\infty$};

%%%%%%%%%%% layer S1 %%%%%%%%
    \node[on chain, above=1ex of l-0,label={left:$S_1$}] (l-1) {$-\infty$} edge[->] (l-0);
    \node[on chain, join, above=1ex of 37] (37-1) {37} edge[->] (37);
    \node[on chain, join, above=1ex of 65] (65-1) {65} edge[->] (65);
    \node[on chain, join, above=1ex of 83] (83-1) {83} edge[->] (83);
    \node[on chain, join, above=1ex of 94] (94-1) {94} edge[->] (94);
    \node[on chain, join, above=1ex of r-0] (r-1) {$\infty$} edge[->] (r-0);

%%%%%%%%%%% layer S2 %%%%%%%%
    \node[on chain, above=1ex of l-1,label={left:$S_2$}] (l-2) {$-\infty$} edge[->] (l-1);
    \node[on chain, join, above=1ex of 65-1] (65-2) {65} edge[->] (65-1);
    \node[on chain, join, above=1ex of r-1] (r-2) {$\infty$} edge[->] (r-1);

%%%%%%%%%%% layer S3 %%%%%%%%
    \node[on chain, above=1ex of l-2,label={left:$S_3$}] (l-3) {$-\infty$} edge[->] (l-2);
    \node[on chain, join, above=1ex of r-2] (r-3) {$\infty$} edge[->] (r-2);
{
\draw [dashed,blue] ([xshift=-3ex,yshift=-3pt]65.south) -- ([xshift=-3ex,yshift=3pt]65-2.north); 
\draw [dashed,blue] ([xshift=3ex,yshift=-3pt]65.south) -- ([xshift=3ex,yshift=3pt]65-2.north); 
\draw [dashed,blue] ([xshift=-3ex,yshift=-3pt]65.south) -- ([xshift=3ex,yshift=-3pt]65.south); 
\draw [dashed,blue] ([xshift=-3ex,yshift=3pt]65-2.north) -- ([xshift=3ex,yshift=3pt]65-2.north); 
\draw [blue,<-] (l-3.north) arc (10:80:0.8);
}
\end{tikzpicture}
\caption{A skip list.}
\end{figure}

\begin{figure}[ht] \centering
\begin{tikzpicture}[
 scale=1.5,font=\footnotesize,
 bullet/.style={ circle,draw,inner sep=1.5,fill=black },
 leaf/.style={ rectangle,draw,inner sep=1.5,fill=white },
 triee/.style={draw=none,fill=white,inner sep=1pt,font=\scriptsize},
 level 1/.style={level distance=3mm,sibling distance=30mm},
 level 2/.style={level distance=5mm,sibling distance=20mm},
 level 3/.style={level distance=5mm,sibling distance=8mm},
 level 4/.style={level distance=5mm,sibling distance=6mm}
]
\node(r)[bullet]{} 
    child{ node(0)[bullet]{}
        child{ node(00)[bullet]{}%
            child{ node(00E)[leaf]{00\$}%
            edge from parent node[triee]{$\$$}
            }
            child{ node(000)[bullet]{}%
                child{ node(0001)[bullet]{}%
                    child{ node(0001E)[leaf]{0001\$}%
                    edge from parent node[triee]{$\$$}
                    }
                edge from parent node[triee]{$1$}
                }
            edge from parent node[triee]{$0$}
            }
            child{ node(001)[bullet]{}%
                child{ node(001E)[leaf]{001\$}%
                edge from parent node[triee]{$\$$}
                }
            edge from parent node[triee]{$1$}
            }
        edge from parent node[triee]{$0$}
        }
        child{ node(01)[bullet]{}%
            child{ node(010)[bullet]{}%
                child{ node(0100)[bullet]{}%
                    child{ node(0100E)[leaf]{0100\$}%
                    edge from parent node[triee]{$\$$}
                    }
                edge from parent node[triee]{$0$}
                }
            edge from parent node[triee]{$0$}
            }
            child{ node(011)[bullet]{}%
                child{ node(011E)[leaf]{011\$}%
                edge from parent node[triee]{$\$$}
                }
                child{ node(0110)[bullet]{}%
                    child{ node(01101E)[leaf]{011\$}%
                    edge from parent node[triee]{$\$$}
                    }
                edge from parent node[triee]{$0$}
                }
            edge from parent node[triee]{$1$}
            }
        edge from parent node[triee]{$1$}
        }
    edge from parent node[triee]{$0$}
    }
    child{ node(1)[bullet]{}%
        child{ node(11)[bullet]{}%
            child{ node(110)[bullet]{}%
                child{ node(110E)[leaf]{110\$}%
                edge from parent node[triee]{$\$$}
                }
                child{ node(1101)[bullet]{}%
                    child{ node(1101E)[leaf]{1101\$}%
                    edge from parent node[triee]{$\$$}
                    }
                edge from parent node[triee]{$1$}
                }
            edge from parent node[triee]{$0$}
            }
            child{ node(111)[bullet]{}%
                child{ node(111E)[leaf]{111\$}%
                edge from parent node[triee]{$\$$}
                }
            edge from parent node[triee]{$1$}
            }
        edge from parent node[triee]{$1$}
        }
    edge from parent node[triee]{$1$}
    }
;
\end{tikzpicture}
\caption{A trie.} 
\end{figure}

\begin{figure}[ht] \centering
\begin{tikzpicture}[
 scale=0.6,font=\footnotesize,
 triee/.style={draw=none,fill=white,inner sep=1pt,font=\scriptsize},
 level 1/.style={level distance=13mm,sibling distance=70mm},
 level 2/.style={level distance=13mm,sibling distance=40mm},
 level 3/.style={level distance=13mm,sibling distance=16mm},
 level 4/.style={level distance=13mm,sibling distance=20mm},
 internal node/.style={ inner sep=1pt,draw,circle,fill=black!15,minimum size=12pt},
 leaf/.style={ rectangle,draw,inner sep=1.5,fill=white }
]
\node(r)[internal node]{0} 
    child{ node(0)[internal node]{1}
        child{ node(00)[internal node]{2}%
            child{ node(00E)[leaf]{00\$}%
            edge from parent node[triee]{$\$$}
            }
            child{ node(0001E)[leaf]{0001\$}%
            edge from parent node[triee]{$0$}
            }
            child{ node(001E)[leaf]{001\$}%
            edge from parent node[triee]{$1$}
            }
        edge from parent node[triee]{$0$}
        }
        child{ node(01)[internal node]{2}%
            child{ node(01001E)[leaf]{01001\$}%
            edge from parent node[triee]{$0$}
            }
            child{ node(011)[internal node]{3}%
                child{ node(011E)[leaf]{011\$}%
                edge from parent node[triee]{$\$$}
                }
                child{ node(01101E)[leaf]{01101\$}%
                edge from parent node[triee]{$0$}
                }
            edge from parent node[triee]{$1$}
            }
        edge from parent node[triee]{$1$}
        }
    edge from parent node[triee]{$0$}
    }
    child{ node(11)[internal node]{2}%
        child{ node(110)[internal node]{3}%
            child{ node(110E)[leaf]{110\$}%
            edge from parent node[triee]{$\$$}
            }
            child{ node(1101E)[leaf]{1101\$}%
            edge from parent node[triee]{$1$}
            }
        edge from parent node[triee]{$0$}
        }
        child{ node(111E)[leaf]{111\$}%
        edge from parent node[triee]{$1$}
        }
    edge from parent node[triee]{$1$}
    }
;
\end{tikzpicture}%
\caption{A compressed trie.}
\end{figure}

\begin{figure}[ht] \centering
\begin{tikzpicture}[scale=0.8,line width=1pt,
start chain=going below,node distance=-1pt,
every node/.style={draw,minimum width=1cm,minimum height=6mm},
chainnode/.style={draw,minimum width=1.3cm,minimum height=4mm},
every label/.style={draw=none,minimum width=0pt,text=blue,font=\tt\footnotesize},
label distance=0mm]
%%%%%%%%% 0 %%%%%%%%%%%%%
\node[on chain,label={left:0}] (0) {};
\node[draw=none,above=1pt of 0] {$T$};
%%%%%%%%% 1 %%%%%%%%%%%%%
\node[on chain,label={left:1}] (one) {};
\node[right=1cm of one,chainnode] {45} edge [<-] (one);
%%%%%%%%% 2 %%%%%%%%%%%%%
\node[on chain,label={left:2}] (two) {};
\node[chainnode,right=1cm of two] (newtwo) {79} edge [<-] (two);
\node[chainnode,right=1cm of newtwo]  (newnewtwo) {46} edge [<-] (newtwo);
\node[chainnode,right=1cm of newnewtwo] {13} edge [<-] (newnewtwo);
%%%%%%%%% 3 %%%%%%%%%%%%%
\node[on chain,label={left:3}] {};
%%%%%%%%% 4 %%%%%%%%%%%%%
\node[on chain,label={left:4}] (four) {};
\node[right=1cm of four,chainnode] {92} edge [<-] (four);
%%%%%%%%% 5 %%%%%%%%%%%%%
\node[on chain,label={left:5}] (five) {};
\node[right=1cm of five,chainnode] (newfive) {16} edge [<-] (five);
\node[right=1cm of newfive,chainnode] {49} edge [<-] (newfive);
%%%%%%%%% 6 %%%%%%%%%%%%%
\node[on chain,label={left:6}] {};
%%%%%%%%% 7 %%%%%%%%%%%%%
\node[on chain,label={left:7}] (seven) {};
\node[right=1cm of seven,chainnode] {7} edge [<-] (seven);
%%%%%%%%% 8 %%%%%%%%%%%%%
\node[on chain,label={left:8}] (eight) {};
\node[right=1cm of eight,chainnode] {41} edge [<-] (eight);
%%%%%%%%% 9 %%%%%%%%%%%%%
\node[on chain,label={left:9}] {};
%%%%%%%%% 10 %%%%%%%%%%%%%
\node[on chain,label={left:10}] (ten) {};
\node[right=1cm of ten,chainnode] {43} edge [<-] (ten);
\end{tikzpicture}
\caption{A hash-table with chaining.} 
\end{figure}

\begin{figure}[ht] \centering
\begin{minipage}{0.45\linewidth}
  \begin{tikzpicture}[scale=.3,font=\footnotesize]
    \fill (2,6.5) circle (4pt) node [below] {$p_0$};
    \fill (2.5,8) circle (4pt) node [above =1mm] {$p_1$};
    \draw [dotted,->] (2.5,8) -- (2.5,8.7);
    \fill (3.5,3.5) circle (4pt) node [below left] {$p_2$};
    \fill (1,10) circle (4pt) node [above=1mm] {$p_3$};
    \draw [dotted,->] (1,10) -- (1,10.7);
    \fill (9,11.5) circle (4pt) node [right] {$p_4$};
    \fill (10,4.5) circle (4pt) node [above right] {$p_5$};
    \fill (5,5) circle (4pt) node [above] {$p_6$};
    \fill (4,3) circle (4pt) node [below right] {$p_7$};
    \draw [dotted,->] (4,3) -- (4.7,3);
    \fill (6,9) circle (4pt) node [right] {$p_8$};
    \fill (3,11) circle (4pt) node [above] {$p_9$};

    \draw (0,0) -- (0,16);
    \draw (16,0) -- (16,16);
    \draw (0,16) -- (16,16);
    \draw (0,0) -- (16,0);

    \draw [ultra thick] (8,0) -- (8,16);
    \draw [ultra thick] (0,8) -- (16,8);

    \draw [thick] (4,0) -- (4,16);
    \draw [thick] (0,4) -- (8,4);
    \draw [thick] (0,12) -- (8,12);
    
    \draw (2,8) -- (2,12);
    \draw (0,10) -- (4,10);

  \end{tikzpicture}
\end{minipage}
\begin{minipage}{0.4\linewidth}
\begin{tikzpicture}[scale=0.8,level distance=40pt,
level 1/.style={sibling distance=80pt},
level 2/.style={sibling distance=20pt},
level 3/.style={sibling distance=20pt},
inner/.style={rectangle,rounded corners,font=\tiny,draw},
leaf/.style={circle,inner sep=1.5,draw},
font = \footnotesize
]
\node [inner] {$[0,16){\times}[0,16)$}
    child {node [leaf,right=30pt] {$p_4$} }
    child {node [inner] {~~~}
        child {node [leaf] {$\emptyset$}}
        child {node [leaf] {$\emptyset$}}
        child  {node [inner] {~~~}
            child {node [leaf] {$p_9$} }
            child {node [leaf] {$p_3$} }
            child {node [leaf] {$\emptyset$}}
            child {node [leaf] {$p_1$} }
        }
        child {node [leaf] {$p_8$} }
    }
    child {node [inner] {~~~}
        child {node [leaf] {$p_6$} }
        child {node [leaf] {$p_0$} }
        child {node [leaf] {$p_2$} }
        child {node [leaf] {$p_7$} }
    }
    child {node [leaf,left=30pt] {$p_5$} }
;
\end{tikzpicture}
\end{minipage}
\caption{A point set and its quad-tree.}
\end{figure}

\begin{figure}[ht] \centering
\begin{tikzpicture}[scale=0.8,level distance=40pt,
level 1/.style={sibling distance=160pt},
level 2/.style={sibling distance=80pt},
level 3/.style={sibling distance=40pt},
level 4/.style={sibling distance=30pt},
edgelabel/.style={draw=none,fill=white,inner sep=0.5,font=\scriptsize},
inner/.style={rectangle split,rectangle split parts=2,rounded corners,inner sep=1.5,minimum width=15mm,draw,font=\scriptsize},
every second node part/.style={blue},
leaf/.style={circle,inner sep=1.5,draw},
font = \footnotesize
]

\begin{scope}[scale=0.5]
\fill (1,4) circle (4pt) node [above right] {$p_0$};
\fill (2.5,6) circle (4pt) node [above right] {$p_1$};
\fill (3,2) circle (4pt) node [above right] {$p_2$};
\fill (0,8) circle (4pt) node [right] {$p_3$};
\fill (8,9.5) circle (4pt) node [above right] (p4) {$p_4$};
\fill (9,3) circle (4pt) node [below right] {$p_5$};
\fill (7,3.5) circle (4pt) node [above right] {$p_6$};
\fill (6,1) circle (4pt) node [above right] {$p_7$};
\fill (5,7) circle (4pt) node [above right] {$p_8$};
\fill (2,9) circle (4pt) node [above right] {$p_9$};

\draw [ultra thick] (4.9,0) -- (4.9,10);
\draw [thick] (-1,5.9) -- (5,5.9);
\draw [thick] (4.9,3.4) -- (10,3.4);
\draw (1.9,6) -- (1.9,10); % through p1
\draw (2.9,0) -- (2.9,6); % through p2
\draw (6.9,3.4) -- (6.9,10);  % through p6
\draw (8.9,0) -- (8.9,3.4);  % through p5
\draw [thick, dotted] (2,8.9) -- (5,8.9); % through p9
\draw [thick, dotted] (5,6.9) -- (6.9,6.9); % through p8
\draw [thick, dotted] (6.9,9.4) -- (11,9.4); % through p4
\end{scope}

\node [right=60mm of p4,inner] {$\mathbb{R}^2$\nodepart{second}$x{<}p_8.x$?}
    child {node [inner] {$\{(x,y): x{<}p_8.x\}$\nodepart{second}$y{<}p_1.y$?}
        child {node [inner,left=-40pt] {$({-}\infty,p_8.x){\times}({-}\infty,p_1.y)$\nodepart{second}$x{<} p_2.x$?}
            child {node [leaf] {$p_0$}
            edge from parent node[edgelabel]{Y} 
            }
            child {node [leaf] {$p_2$}
            edge from parent node[edgelabel]{N} 
            }
        edge from parent node[edgelabel]{Y}
        }
        child {node [inner] {$\cdots$\nodepart{second}$x{<} p_9.x$?}
            child {node [leaf] {$p_3$}
            edge from parent node[edgelabel]{Y}
            }
            child {node [inner] {$\cdots$\nodepart{second}$y{<} p_9.y$?}
                child {node [leaf] {$p_1$}
                edge from parent node[edgelabel]{Y} 
                }
                child {node [leaf] {$p_9$}
                edge from parent node[edgelabel]{N} 
                }
            edge from parent node[edgelabel]{N}
            }
        edge from parent node[edgelabel]{N}
        }
    edge from parent node[edgelabel]{Y}
    }
    child {node [inner] {$\{(x,y): x{\geq}p_8.x\}$\nodepart{second}$y{<}p_6.y$?}
        child {node [inner] {$\cdots$\nodepart{second}$x{<} p_5.x$?}
            child {node [leaf] {$p_7$}
            edge from parent node[edgelabel]{Y} 
            }
            child {node [leaf] {$p_5$}
            edge from parent node[edgelabel]{N} 
            }
        edge from parent node[edgelabel]{Y}
        }
        child {node [inner] {$\cdots$\nodepart{second}$x{<} p_6.x$?}
            child {node [leaf] {$p_8$}
            edge from parent node[edgelabel]{Y} 
            }
            child {node [inner] {$\cdots$\nodepart{second}$y{<} p_4.y$?}
                child {node [leaf] {$p_6$}
                edge from parent node[edgelabel]{Y} 
                }
                child {node [leaf] {$p_4$}
                edge from parent node[edgelabel]{N} 
                }
            edge from parent node[edgelabel]{N}
            }
        edge from parent node[edgelabel]{N}
        }
    edge from parent node[edgelabel]{N}
    }
;
\end{tikzpicture}
\caption{A point set and its kd-tree.}
\end{figure}

\begin{figure}[ht] \centering
\begin{tikzpicture}[
scale=.5,
inRange/.style={ultra thick,draw=green!70!black},
path node/.style={fill=blue!50!white},
outside node/.style={fill=red!50!white},
returned/.style={fill=yellow},
top inside/.style={fill=green!50!white}
]
\pgfdeclarelayer{background}
\pgfdeclarelayer{foreground}
\pgfsetlayers{background,main,foreground}
    \draw (0,0) rectangle (17,17) ;
    \foreach \x/\y/\v/\w/\s in {
              1/5/0/ /outside node,%
              2/7/1/ /path node,%
              3/1/0/ /path node,%
              4/4/3/ /path node,%
             5/13/1/2/,%
             6/15/2/1/top inside,%
             7/11/0/0/,%
             8/10/1/1/,%
              9/6/0/0/,%
            10/12/5//path node,%
             11/8/1/1/,%
            12/14/2/0/top inside,%
             13/2/1/0/,%
             14/9/3/ /path node,%
            15/16/1/ /path node,%
             16/3/2/ /path node%
    } {
        \tikzset{ret/.style={}}
        \ifthenelse{\x > 3 \AND \x < 16 \AND \y > 8 \AND \y < 12}{
            \tikzset{ret/.style={ultra thick}}
        }{}
        \node[circle,draw,inner sep=0pt,minimum size=7pt,fill=white,\s,ret] 
            (x\x) at (\x,17.5+\v) {\scalebox{.4}{\x}};
        \tikzset{topin/.style={}}
        \ifthenelse{ \(\x > 4 \AND \x < 10\) \OR \(\x > 10 \AND \x < 14\) }{
            {\tikzset{topin/.style={thick,returned!50!red!50!black}}}
        }{}
        { \draw[very thin,black!50,topin,<-,shorten <=2pt, >=stealth] (\x,\y) -- (x\x) ; }
        
            \ifthenelse{ \x > 4 \AND \x < 10 }{
                \node[circle,draw,inner sep=0pt,minimum size=7pt,fill=white,ret] (y\y) at (-1-\w,\y) {\scalebox{.4}{\y}};
                \draw[topin,<-,shorten <=2pt, >=stealth] (\x,\y) -- (y\y) ;
            }{}
            \fill[black] (\x,\y) circle (6pt) node[above right=-2pt] {\scalebox{.4}{$(\x,\y)$}};
            \ifthenelse{ \x > 10 \AND \x < 14 }{
                \node[circle,draw,inner sep=0pt,minimum size=7pt,fill=white,ret] (y\y) at (18+\w,\y) {\scalebox{.4}{\y}};
                \draw[topin,<-,shorten <=2pt, >=stealth] (\x,\y) -- (y\y) ;
            }{}
        \fill[black] (\x,\y) circle (6pt) node[above right=-2pt] {\scalebox{.4}{$(\x,\y)$}};
    }
        \draw 
            (x10) -- (x4) -- (x2) -- (x1)
            (x2) -- (x3)
            (x4) -- (x6) -- (x5)
            (x6) -- (x8) -- (x7)
            (x8) -- (x9)
            (x10) -- (x14) -- (x12) -- (x11)
            (x14) -- (x16) -- (x15)
            (x12) -- (x13)
        ;
        \draw 
            (y13) -- (y10) -- (y6)
            (y13) -- (y15)
            (y10) -- (y11)
        ;
        \draw 
            (y8) -- (y2)
            (y8) -- (y14)
        ;
    \begin{pgfonlayer}{background}
        { \fill[gray,opacity=.3] (3.5,0) rectangle (15.5,23); }
        { \fill[gray,opacity=.3] (-4,8.5) rectangle (19.5,11.5); }
        \draw[gray] (3.5,8.5) rectangle (15.5,11.5) ;
            \fill[yellow!50!red!50!black!50,rounded corners =3pt] 
                (6,20.5) -- (4.5,19) -- (4.25,17) -- (10,17) -- (9,18.7)-- cycle
                [rounded corners=6pt]
                (12,20.75) -- (10,17.8) -- (14,17.8) -- cycle
            ;
            \path[pattern color=yellow!50!red!50!black!50,pattern=crosshatch dots] 
                (4.5,0) rectangle (9.5,17)
                (10.5,0) rectangle (13.5,18)
            ;
    \end{pgfonlayer}
        \draw[dashed,thick,blue,->,>=stealth] (x6) to[out=180,in=115,looseness=1.6] 
            node[pos=.99,left,align=center,font=\scriptsize] {$T(6)$} (y13) ;
        \draw[dashed,thick,blue,->,>=stealth] (x12) to[out=0,in=60,looseness=1.3] 
            node[pos=.97,right,align=center,font=\scriptsize] {$T(12)$} (y8) ;
    \node at (13,22.5) {\scriptsize ~ primary tree $T$} ;
\end{tikzpicture}
\caption{Range search in a range-tree.}
\end{figure}


\begin{figure}[ht] \centering
\begin{tikzpicture}[%
level 1/.style={sibling distance=120pt},
level 2/.style={sibling distance=60pt},
level 3/.style={sibling distance=30pt},
edgelabel/.style={draw=none,fill=white,inner sep=1pt,font=\scriptsize},
inner/.style={rectangle split,rectangle split parts=2,rounded corners,inner sep=1.5,minimum width=10mm,draw,font=\scriptsize},
boundary/.style={fill=blue!50!white},
outside/.style={fill=red!50!white},
inside/.style={fill=green!50!white},
returned/.style={font=\bfseries\scriptsize},
every second node part/.style={blue,font=\rmfamily,font=\scriptsize},
leaf/.style={rectangle,rounded corners,inner sep=1.5,draw,font=\scriptsize},
]
\pgfdeclarelayer{background}
\pgfdeclarelayer{foreground}
\pgfsetlayers{background,main,foreground}
\node[inner,boundary,returned] (r) {(15,16)\nodepart{second}$x<9$?}
    child {node[inner,boundary,returned] {(6,15)\nodepart{second}$x<5$?}
        child {node[inner,boundary] {(2,7)\nodepart{second}$x<2$?}
            child {node[leaf,outside] {(1,5)} 
            edge from parent node[edgelabel,above=-1pt]{Y} 
            }
            child {node[inner,boundary] {(4,4)\nodepart{second}$x<4$?}
                child {node[leaf,boundary] {(3,1)}
                edge from parent node[edgelabel]{Y} 
                }
                child {edge from parent[draw=none]}
            edge from parent node[edgelabel]{N} 
            }
        edge from parent node[edgelabel]{Y} 
        }
        child {node[inner,inside,returned] (x5) {(5,13)\nodepart{second}$x<8$?}
            child {node[leaf,returned] (x7) {(7,11)} 
            edge from parent node[edgelabel,fill=yellow!50!red!50!black!50]{Y} 
            }
            child {node[leaf,returned] (x8) {(8,10)} 
            edge from parent node[edgelabel,fill=yellow!50!red!50!black!50]{N} 
            }
        edge from parent node[edgelabel]{N} 
        }
    edge from parent node[edgelabel]{Y} 
    }
    child {node[inner,boundary,returned] {(12,14)\nodepart{second}$x<13$?}
        child {node[inner,inside,returned] (x10) {(10,12)\nodepart{second}$x<10$?}
            child {node[leaf] (x9) {(9,6)} 
            edge from parent node[edgelabel,fill=yellow!50!red!50!black!50]{Y} 
            }
            child {node[leaf] (x11) {(11,8)} 
            edge from parent node[edgelabel,fill=yellow!50!red!50!black!50]{N} 
            }
        edge from parent node[edgelabel]{Y} 
        }
        child {node[inner,boundary,returned] {(14,9)\nodepart{second}$x<13$?}
            child {node[leaf,inside] (x13) {(13,2)} 
            edge from parent node[edgelabel]{Y} 
            }
            child {node[leaf,boundary] {(16,3)} 
            edge from parent node[edgelabel]{N} 
            }
        edge from parent node[edgelabel]{N} 
        }
    edge from parent node[edgelabel]{N} 
    }
;
\begin{pgfonlayer}{background}
\fill[yellow!50!red!50!black!50,rounded corners =3pt] 
            (x5.north west) -- (x5.north east) -- (x8.south east) -- (x7.south west) -- cycle
            (x10.north west) -- (x10.north east) -- (x11.south east) -- (x9.south west) -- cycle
            ([yshift=1pt,xshift=-1pt]x13.north west) -- ([yshift=1pt,xshift=1pt]x13.north east) -- ([yshift=-2pt,xshift=1pt]x13.south east) -- ([yshift=-2pt,xshift=-1pt]x13.south west) -- cycle
            ;
\end{pgfonlayer}
\end{tikzpicture}
\caption{A 3-sided search in a priority-search tree.}
\end{figure}

\begin{figure}[ht] \centering
\newcommand{\alert}[1]{{\color{red}#1}}
\newcommand{\correct}[1]{{\color{green}#1}}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|}
\multicolumn{1}{c}{\texttt{a}} & \multicolumn{1}{c}{\texttt{b}} & 
\multicolumn{1}{c}{\texttt{b}} & \multicolumn{1}{c}{\texttt{b}} &
\multicolumn{1}{c}{\texttt{a}} & \multicolumn{1}{c}{\texttt{b}} &
\multicolumn{1}{c}{\texttt{a}} & \multicolumn{1}{c}{\texttt{b}} &
\multicolumn{1}{c}{\texttt{b}} & \multicolumn{1}{c}{\texttt{a}} &
\multicolumn{1}{c}{\texttt{b}} \\ \hline
\cellcolor{lightgray}a & \cellcolor{lightgray}b & \cellcolor{lightgray}b & \cellcolor{lightgray}\alert{a} &  &  &  &  &  &  & \\ \hline
& \cellcolor{lightgray}\alert{a} &  \cellcolor{lightgray} &  \cellcolor{lightgray} &  \cellcolor{lightgray} &  &  &  &  &  & \\ \hline
&  & \cellcolor{lightgray}\alert{a} &  \cellcolor{lightgray} &  \cellcolor{lightgray} &  \cellcolor{lightgray} &  &  &  &  & \\ \hline
&  &  & \cellcolor{lightgray}\alert{a} &  \cellcolor{lightgray} &  \cellcolor{lightgray} &  \cellcolor{lightgray} &  &  &  & \\ \hline
&  &  &  & \cellcolor{lightgray}{a} & \cellcolor{lightgray}{b} & \cellcolor{lightgray}\alert{b} & \cellcolor{lightgray}  &  &  & \\ \hline
&  &  &  &  & \cellcolor{lightgray}\alert{a} &  \cellcolor{lightgray} &  \cellcolor{lightgray} &  \cellcolor{lightgray} &  & \\ \hline
&  &  &  &  &  & \cellcolor{lightgray}\correct{a} & \cellcolor{lightgray}\correct{b} & \cellcolor{lightgray}\correct{b} & \cellcolor{lightgray}\correct{a} & \\ \hline
\end{tabular}
\caption{A table for pattern matching.}
\end{figure}

\begin{figure}[ht] \centering
\begin{tikzpicture}[->,>=stealth',auto,node distance=1.5cm, minimum size=0.1cm, thick, initial text=]
  \tikzstyle{every state}=[fill=none,draw=black,text=black]
  \node[state,initial,minimum size=3pt]         (0)                {$0$};
  \node[state,minimum size=3pt]         (1) [right of=0] {$1$};
  \node[state,minimum size=3pt]         (2) [right of=1] {$2$};
  \node[state,minimum size=3pt]         (3) [right of=2] {$3$};
  \node[state,minimum size=3pt]         (4) [right of=3] {$4$};
  \node[state,minimum size=3pt]         (5) [right of=4] {$5$};
  \node[state,minimum size=3pt]         (6) [right of=5] {$6$};
  \node[state,accepting,minimum size=3pt]         (7) [right of=6] {$7$};

  \draw (0) edge              node {a} (1);
  \draw (0) edge [loop above] node {$\Sigma-${\tt a}} (0);
  \draw (1) edge              node {b} (2);
  \draw (1) edge [bend left]  node[below=-2pt,pos=0.2] {$\times$} (0.south);
  \draw (2) edge              node {a} (3);
  \draw (2) edge [bend left=40]  node[pos=0.2,right=3pt] {$\times$} (0.south);
  \draw (3) edge              node {b} (4);
  \draw (3) edge [bend right=50]  node[swap,pos=0.7,above=-2pt] {$\times$} (1);
  \draw (4) edge              node {a} (5);
  \draw (4) edge [bend left=50]  node[pos=0.2,right=3pt] {$\times$} (2.south);
  \draw (5) edge              node {c} (6);
  \draw (5) edge [bend right=50] node[swap,pos=0.7,above=-2pt] {$\times$} (3);
  \draw (6) edge              node {a} (7);
  \draw (6) edge [bend left=40]  node[pos=0.2,right=3pt] {$\times$} (0.south);
  \draw (7) edge [loop above] node {$\Sigma$} (0);
\end{tikzpicture}
\caption{A KMP-automaton.}
\end{figure}


\begin{figure}[ht] \centering
\begin{tabular}{c|r|*{13}{c|}c|c}
&& \multicolumn{13}{c|}{$P^*[{-}m..m{-}2]$}  && \\
&&
\multicolumn{1}{c}{\scriptsize {-}7} &
\multicolumn{1}{c}{\scriptsize {-}6} &
\multicolumn{1}{c}{\scriptsize {-}5} &
\multicolumn{1}{c}{\scriptsize {-}4} &
\multicolumn{1}{c}{\scriptsize {-}3} &
\multicolumn{1}{c}{\scriptsize {-}2} &
\multicolumn{1}{c}{\scriptsize {-}1} &
\multicolumn{1}{c}{\scriptsize 0} &
\multicolumn{1}{c}{\scriptsize 1} &
\multicolumn{1}{c}{\scriptsize 2} &
\multicolumn{1}{c}{\scriptsize 3} &
\multicolumn{1}{c}{\scriptsize 4} &
\multicolumn{1}{c|}{\scriptsize 5} &
match starts &
\\
\cline{3-15}
$j$ & $P[j{+}1..m{-}1]$ & 
{\tt *} &
{\tt *} &
{\tt *} &
{\tt *} &
{\tt *} &
{\tt *} &
{\tt *} &
{\tt b} &
{\tt o} &
{\tt o} &
{\tt b} &
{\tt o} &
{\tt b} &
at index &
$S[j]$ \\
\hline
\hline
5 & {\tt o} &&&&&&&&&&&& {\tt o} && 4 & 3 \\
\hline
4 & {\tt bo} &&&&&&&&&&& {\tt b} & {\tt o} && 3 & 2 \\
\hline
3 & {\tt obo} &&&&&&&&&& {\tt o} & {\tt b} & {\tt o} && 2 & 1 \\
\hline
2 & {\tt bobo} &&&&&& {\tt b} & {\tt o} & {\tt b} & {\tt o} &&&&& -2 & -3 \\
\hline
1 & {\tt obobo} &&&&& {\tt o} & {\tt b} & {\tt o} & {\tt b} & {\tt o} &&&&& -3 & -4 \\
\hline
0 & {\tt oobobo} &&&& {\tt o} & {\tt o} & {\tt b} & {\tt o} & {\tt b} & {\tt o} &&&&& -4 & -5 \\
\hline
\end{tabular}
\caption{Finding the good-suffix array $S$ for pattern $P={\tt boobobo}$.}
\end{figure}

\begin{figure}[ht]
\begin{minipage}[t]{40mm}
\begin{tabular}{r|c|c|c|c|c|c|c|c|c|c|}
\multicolumn{1}{c}{~}
& \multicolumn{1}{c}{\scriptsize 0}
& \multicolumn{1}{c}{\scriptsize 1}
& \multicolumn{1}{c}{\scriptsize 2}
& \multicolumn{1}{c}{\scriptsize 3}
& \multicolumn{1}{c}{\scriptsize 4}
& \multicolumn{1}{c}{\scriptsize 5}
& \multicolumn{1}{c}{\scriptsize 6}
& \multicolumn{1}{c}{\scriptsize 7}
& \multicolumn{1}{c}{\scriptsize 8}
& \multicolumn{1}{c}{\scriptsize 9}
\\ \cline{2-11}
$T=$ & b & a & n & a & n & a & b & a & n & \$ \\ \cline{2-11}
\end{tabular}
\end{minipage}
\begin{minipage}[t]{80mm}
\begin{tikzpicture} [
grow'                    = right,
scale =            0.9,
solid/.style={circle,draw,inner sep=1.5},
leaf/.style={rectangle,draw,inner sep=1.5,fill=white},
sibling distance        = 3em,
level 1/.style={sibling distance=4.5em},
level 2/.style={sibling distance=3em},
level distance          = 6em,
edge from parent/.style = {draw, -latex},
every node/.style       = {font=\footnotesize},
sloped
]
\node [solid] {0}
    child { node [leaf] {$T$[9..9]}
    edge from parent node [above] {\$} 
    }
    child { node [solid,above=1em] {1}
        child { node [leaf] {$T$[5..9]}
        edge from parent node [above] {b} 
        }
        child { node [solid] {2}
            child { node [leaf] {$T$[7..9]}
            edge from parent node [above] {\$} 
            }
            child { node [solid] {3}
                child { node [leaf] {$T$[3..9]}
                edge from parent node [above] {b} 
                }
                child { node [leaf] {$T$[1..9]}
                edge from parent node [above] {n} 
                }
            edge from parent node [above] {a} 
            }
        edge from parent node [above] {n} 
        }
    edge from parent node [below] {a} 
    }
    child { node [solid] {3}
        child { node [leaf] {$T$[6..9]}
        edge from parent node [above] {\$} 
        }
        child { node [leaf] {$T$[0..9]}
        edge from parent node [above] {a} 
        }
    edge from parent node [above] {b} 
    }
    child { node [solid] {1}
        child { node [leaf] {$T$[8..9]}
        edge from parent node [above] {\$} 
        }
        child { node [solid] {2}
            child { node [leaf] {$T$[4..9]}
            edge from parent node [above] {b} 
            }
            child { node [leaf] {$T$[2..9]}
            edge from parent node [above] {n} 
            }
        edge from parent node [above] {a} 
        }
    edge from parent node [above] {n} 
    }
;
\end{tikzpicture}
\end{minipage}
\caption{A suffix tree. }
\end{figure}

\begin{figure}[ht] \centering
    \begin{tikzpicture}[
            scale=.3,
            object/.style={draw,rounded corners=5pt,drop shadow,fill=white,inner sep=8pt},
    ]
\pgfdeclarelayer{foreground}
\pgfsetlayers{main,foreground}
        \begin{scope}[shift={(0,5)}]
            \begin{pgfonlayer}{foreground}
            \draw (-8,0) grid (8,1);
            \node (reg label) at (0,-1) {internal memory -- size $M$};
            \end{pgfonlayer}
            \node[object,fit={(-8,0) (8,1) (reg label)},draw] (reg) {} ;
        \end{scope}
    
        \begin{scope}[shift={(0,15)}]
            \begin{pgfonlayer}{foreground}
            \draw (-19,0) grid (18,1);
            \node at (19,.5) {\dots};
            \node (ram label) at (0,-1) {external memory -- size unbounded};
            \end{pgfonlayer}
            \node[object,fit={(-19,0) (19,1) (ram label)},draw] (ram) {} ;
        \end{scope}
        
        \node[object,minimum width=6em,minimum height=6ex] (cpu) at (0,-3) {Central processing unit (CPU)} ;
        \draw[line width=3em,black!50] (cpu) -- node[right,black] {random access (fast)} (reg);
        \draw[line width=.3em,black,<->] (cpu) -- (reg);
        
        \begin{scope}[shift={(1,-1.25)},scale=.7] \draw[fill=white,rotate=30] (0,0) rectangle ++(1,1); \end{scope}
        \begin{scope}[shift={(-.8,0)},scale=.7] \draw[fill=white,rotate=60] (0,0) rectangle ++(1,1); \end{scope}
        
        \draw[line width=1.5em,black!50] (reg) -- node[right=5pt,black,align=left] 
                {transfer in blocks of $B$ cells (slow)} (ram) ;
        \draw[line width=.15em,black,<->] (reg) -- (ram);
        
        \begin{scope}[shift={(-.8,7.5)},scale=.7,rotate=55] 
            \fill[white] (0,0) rectangle ++(5,1);
            \draw (0,0) grid ++(5,1); 
        \end{scope}
        
    \end{tikzpicture}
\caption{The external memory model.}
\end{figure}

\begin{figure}[ht] \centering
\newcommand{\threenode}[1]{\begin{tabular}{@{\vrule width 1pt\,}c@{\,\vrule width 1pt\,}c@{\,\vrule width 1pt\,}c@{\,\vrule width 1pt}}\noalign{\hrule height 1pt}#1\\\noalign{\hrule height 1pt}\end{tabular}}
\newcommand{\twonode}[1]{\begin{tabular}{@{\vrule width 1pt\,}c@{\,\vrule width 1pt\,}c@{\,\vrule width 1pt}}\noalign{\hrule height 1pt}#1\\\noalign{\hrule height 1pt}\end{tabular}}
\newcommand{\onenode}[1]{\begin{tabular}{@{\vrule width 1pt\,}c@{\,\vrule width 1pt}}\noalign{\hrule height 1pt}#1\\\noalign{\hrule height 1pt}\end{tabular}}
\begin{tikzpicture}[level distance=30pt,
every node/.style={inner sep=0pt},
dummy/.style={rectangle,minimum width=15mm},
level 1/.style={sibling distance=60pt},
level 2/.style={level distance = 20pt, sibling distance=20pt}]
\node {\threenode{5&10&12}}
    child {node {\onenode{3}}
        child {node[dummy] {$\emptyset$}
        edge from parent [edge from parent path={($(\tikzparentnode.south west)!0.01!(\tikzparentnode.south east)$)--(\tikzchildnode)}] 
        }
        child {node[dummy] {$\emptyset$}
        edge from parent [edge from parent path={($(\tikzparentnode.south west)!0.99!(\tikzparentnode.south east)$)--(\tikzchildnode)}] 
        }
    edge from parent [edge from parent path={($(\tikzparentnode.south west)!0.01!(\tikzparentnode.south east)$)--(\tikzchildnode)}] 
    }
    child {node {\twonode{6&8}}
        child {node[dummy] {$\emptyset$}
        edge from parent [edge from parent path={($(\tikzparentnode.south west)!0.01!(\tikzparentnode.south east)$)--(\tikzchildnode)}] 
        }
        child {node[dummy] {$\emptyset$}}
        child {node[dummy] {$\emptyset$}
        edge from parent [edge from parent path={($(\tikzparentnode.south west)!0.99!(\tikzparentnode.south east)$)--(\tikzchildnode)}] 
        }
    edge from parent [edge from parent path={($(\tikzparentnode.south west)!0.33!(\tikzparentnode.south east)$)--(\tikzchildnode)}] 
    }
    child {node {\onenode{11}}
        child {node[dummy] {$\emptyset$}
        edge from parent [edge from parent path={($(\tikzparentnode.south west)!0.01!(\tikzparentnode.south east)$)--(\tikzchildnode)}] 
        }
        child {node[dummy] {$\emptyset$}
        edge from parent [edge from parent path={($(\tikzparentnode.south west)!0.99!(\tikzparentnode.south east)$)--(\tikzchildnode)}] 
        }
    edge from parent [edge from parent path={($(\tikzparentnode.south west)!0.66!(\tikzparentnode.south east)$)--(\tikzchildnode)}] 
    }
    child {node {\threenode{13&14&15}}
        child {node[dummy] {$\emptyset$}
        edge from parent [edge from parent path={($(\tikzparentnode.south west)!0.01!(\tikzparentnode.south east)$)--(\tikzchildnode)}] 
        }
        child {node[dummy] {$\emptyset$}
        edge from parent [edge from parent path={($(\tikzparentnode.south west)!0.33!(\tikzparentnode.south east)$)--(\tikzchildnode)}] 
        }
        child {node[dummy] {$\emptyset$}
        edge from parent [edge from parent path={($(\tikzparentnode.south west)!0.66!(\tikzparentnode.south east)$)--(\tikzchildnode)}] 
        }
        child {node[dummy] {$\emptyset$}
        edge from parent [edge from parent path={($(\tikzparentnode.south west)!0.99!(\tikzparentnode.south east)$)--(\tikzchildnode)}] 
        }
    edge from parent [edge from parent path={($(\tikzparentnode.south west)!0.99!(\tikzparentnode.south east)$)--(\tikzchildnode)}]
    }
;
\end{tikzpicture}
\caption{A 2-4-tree.}
\end{figure}


\begin{figure}[ht] \centering
\begin{tikzpicture}[level distance=30pt, scale=0.7,
every node/.style={inner sep=0pt},
black/.style={minimum width=1.5em,circle,fill=black,text=white,font=\bfseries,inner sep=1.5},
red/.style={minimum width=1.5em,circle,draw,inner sep=1.5,fill=red!70!white},
dummy/.style={rectangle,minimum width=5mm},
level 1/.style={sibling distance=90pt},
level 2/.style={sibling distance=40pt},
level 3/.style={sibling distance=20pt}
]
\node [black] {12}
    child {node [red] {5} 
        child {node [black] {4}
            child {node [red] {3}
                child {node[dummy] {$\emptyset$}}
                child {node[dummy] {$\emptyset$}}
            } 
            child {node[dummy] {$\emptyset$}}
        }
        child {node [black] {11}
            child {node[dummy] {$\emptyset$}}
            child {node[dummy] {$\emptyset$}}
        }
    }
    child {node [black] {14}
        child {node [red] {13}
            child {node[dummy] {$\emptyset$}}
            child {node[dummy] {$\emptyset$}}
        }
        child {node [red] {15}
            child {node[dummy] {$\emptyset$}}
            child {node[dummy] {$\emptyset$}}
        }
    }
;
\end{tikzpicture}
\caption{A red-black tree.}
\end{figure}

\begin{figure}[ht] \centering
\begin{tikzpicture}[
font=\scriptsize,
level distance=25pt,
inner/.style={draw,font=\scriptsize,inner sep=2pt,rectangle split, rectangle split parts = 10,rectangle split horizontal,rectangle split part align={center}},
leaf/.style={draw,inner sep=1pt,rectangle split, rectangle split parts = 10},
level 1/.style={sibling distance=200pt},
level 2/.style={level distance=50pt,sibling distance=40pt}
]
\node [inner] (root) {
    \nodepart{two} ${<}46?$
    \nodepart{one} $\bullet$ \nodepart{three} $\bullet$ \nodepart{five} $\bullet$ \nodepart{seven} $\bullet$ \nodepart{nine} $\bullet$
    }
    child {node [inner] {\nodepart{two} ${<}16?$
        \nodepart{one} $\bullet$ \nodepart{three} $\bullet$ \nodepart{five} $\bullet$ \nodepart{seven} $\bullet$ \nodepart{nine} $\bullet$
        \nodepart{four} ${<}24?$ \nodepart{six} ${<}32?$ \nodepart{eight} ${<}40?$ }
        child {node [leaf] {\nodepart{one} 10 \nodepart{two} v
            \nodepart{three} 12 \nodepart{four} v 
            \nodepart{five} 14 \nodepart{six} v }
        edge from parent [edge from parent path={($(\tikzparentnode.one south)!0.5!(\tikzparentnode.one north)$)--(\tikzchildnode.north)}] 
        }
        child {node [leaf] {\nodepart{one} 16 \nodepart{two} v
            \nodepart{three} 18 \nodepart{four} v 
            \nodepart{five} 20 \nodepart{six} v 
            \nodepart{seven} 22 \nodepart{eight} v }
                edge from parent [edge from parent path={($(\tikzparentnode.three south)!0.5!(\tikzparentnode.three north)$)--(\tikzchildnode.north)}] 
        }
        child {node [leaf] {\nodepart{one} 24 \nodepart{two} v
            \nodepart{three} 26 \nodepart{four} v 
            \nodepart{five} 28 \nodepart{six} v 
            \nodepart{seven} 30 \nodepart{eight} v }
        edge from parent [edge from parent path={($(\tikzparentnode.five south)!0.5!(\tikzparentnode.five north)$)--(\tikzchildnode.north)}] 
        }
        child {node [leaf] {\nodepart{one} 32 \nodepart{two} v
            \nodepart{three} 34 \nodepart{four} v 
            \nodepart{five} 36 \nodepart{six} v 
            \nodepart{seven} 38 \nodepart{eight} v }
        edge from parent [edge from parent path={($(\tikzparentnode.seven south)!0.5!(\tikzparentnode.seven north)$)--(\tikzchildnode.north)}] 
        }
        child {node [leaf] {\nodepart{one}40  \nodepart{two} v
            \nodepart{three} 42 \nodepart{four} v 
            \nodepart{five} 44 \nodepart{six} v }
        edge from parent [edge from parent path={($(\tikzparentnode.nine south)!0.5!(\tikzparentnode.nine north)$)--(\tikzchildnode.north)}] 
        }
    edge from parent [edge from parent path={($(\tikzparentnode.one south)!0.5!(\tikzparentnode.one north)$)--(\tikzchildnode.north)}] 
    }
    child {node [inner] {\nodepart{two} ${<}54?$ 
        \nodepart{four} ${<}60?$ \nodepart{six} ${<}70?$
        \nodepart{one} $\bullet$ \nodepart{three} $\bullet$ 
        \nodepart{five} $\bullet$ \nodepart{seven} $\bullet$ 
        \nodepart{nine} $\bullet$ }
        child {node [leaf] {\nodepart{one} 46 \nodepart{two} v
            \nodepart{three} 48 \nodepart{four} v 
            \nodepart{five} 50 \nodepart{six} v 
            \nodepart{seven} 52 \nodepart{eight} v }
        edge from parent [edge from parent path={($(\tikzparentnode.one south)!0.5!(\tikzparentnode.one north)$)--(\tikzchildnode.north)}] 
        }
        child {node [leaf] {\nodepart{one} 54 \nodepart{two} v
            \nodepart{three} 56 \nodepart{four} v 
            \nodepart{five} 58 \nodepart{six} v }
        edge from parent [edge from parent path={($(\tikzparentnode.three south)!0.5!(\tikzparentnode.three north)$)--(\tikzchildnode.north)}] 
        }
        child {node [leaf] {\nodepart{one} 60 \nodepart{two} v
            \nodepart{three} 62 \nodepart{four} v 
            \nodepart{five} 64 \nodepart{six} v 
            \nodepart{seven} 66 \nodepart{eight} v 
            \nodepart{nine} 68 \nodepart{ten} v }
        edge from parent [edge from parent path={($(\tikzparentnode.five south)!0.5!(\tikzparentnode.five north)$)--(\tikzchildnode.north)}] 
        }
        child {node [leaf] {\nodepart{one} 70 \nodepart{two} v
            \nodepart{three} 72 \nodepart{four} v 
            \nodepart{five} 74 \nodepart{six} v }
        edge from parent [edge from parent path={($(\tikzparentnode.seven south)!0.5!(\tikzparentnode.seven north)$)--(\tikzchildnode.north)}] 
        }
        child {edge from parent [draw=none]}
    edge from parent [edge from parent path={($(\tikzparentnode.three south)!0.5!(\tikzparentnode.three north)$)--(\tikzchildnode.north)}] 
    }
;
\end{tikzpicture}
\caption{A $B^+$-tree.} 
\end{figure}

\tikzset{
}
\begin{figure}[ht] \centering
\begin{tikzpicture} [
grow'                    = right,
sibling distance        = 3em,
level 1/.style={sibling distance=32mm},
level 2/.style={sibling distance=16mm},
level 3/.style={sibling distance=8mm},
level distance          = 3em,
edge from parent/.style = {draw, -latex},
every node/.style       = {font=\footnotesize},
sloped,
fake/.style={opacity=0},
inner/.style={circle,draw,inner sep=1.5,fill=black},
leaf/.style={rectangle,draw,inner sep=1.5,fill=white},
external link/.style={>=stealth,<-,red,densely dotted,out=180,in=0,},
]
\node (r) [inner] {}
    child { node [inner] (0) {}
        child { node [inner] (00) {}
        edge from parent node [above] {0} 
        }
        child { node [inner] (01) {}
            child { node [inner] (010) {}
            edge from parent node [above] {0} 
            }
            child { node [inner] (011) {}
            edge from parent node [above] {1} 
            }
        edge from parent node [above] {1} 
        }
    edge from parent node [above] {0} 
    }
    child { node [inner] (1) {}
    edge from parent node [above] {1} 
    }
;

\begin{scope}[
            chain node/.style={draw,minimum width=6ex,minimum height=12mm},
            thick,
            start chain=going below,node distance=20pt,
            every label/.style={draw=none,minimum width=0pt,font=\tt\footnotesize},
            label distance=0mm,
]
\node[right=20mm of 00,chain node,on chain,label={above:00***}] (n00) 
            {\begin{minipage}{5ex} 00101 \\ 00000\end{minipage}}
            edge[external link]  (00);
\node[chain node,on chain,label={above:010**}] (n010) 
            {\begin{minipage}{5ex}01000 \linebreak 01010\end{minipage}}
            edge[external link] (010);
\node[chain node,on chain,label={above:011**}] (n011) 
            {\begin{minipage}{5ex}01101 \\ 01110 \\ 01111 \end{minipage}}
            edge[external link] (011);
\node[chain node,on chain,label={above:1****}] (n1) 
            {\begin{minipage}{5ex} 10101 \\ 11010 \\ 10000 \end{minipage}}
            edge[external link] (1);
\end{scope}
   
\coordinate[above left=.75 and .5 of n00.west] (top);
\coordinate[below left=.75 and .5 of n1.west] (bottom);
\draw[very thick,dashed,opacity=.5,blue] (bottom) -- (top);
\draw (n1.west) ++ (-2.75,-1.1) node [draw=none] {Internal};
\draw (n1) ++ (0,-1.1) node [draw=none] {External};
\end{tikzpicture}
\caption{A trie of blocks.}
\end{figure}


\end{document}