% display tree structure of a comparison program for finding the second largest
% of four elements
% Adam Gashlin 2012-09-08
\documentclass[letterpaper]{article}
\usepackage[landscape]{geometry}
\usepackage{tikz}
\usetikzlibrary{positioning}
\begin{document}
\begin{tikzpicture} [
    comp/.style={circle,draw,minimum size=1cm},
    complabel/.style={minimum size=10mm},
    complabel left/.style={complabel,anchor=east},
    complabel right/.style={complabel,anchor=west},
    result/.style={rectangle,draw,minimum size=5mm,inner sep=0},
    hasse/.style={node distance=1mm, inner sep=0,minimum size=2.5mm,fill=white},
    hasse matrix/.style={hasse, left=of #1, node distance=0, column sep=2mm,fill=none}]
\tt
% root
\node[comp] (node) {a:b};
% inner nodes 
\foreach \xscale/\lttext/\gttext/\parent in {
        4/c:d/c:d/,
        2/b:d/b:c/_0,
        2/a:d/a:c/_1,
        1/b:c/a:d/_0_0,
        1/b:d/a:c/_0_1,
        1/a:c/b:d/_1_0,
        1/a:d/b:c/_1_1}
    \foreach \xdir/\xtext/\labeltext/\labelopts/\xname in {
       -9mm/\lttext/$<$/complabel left/node\parent_0,
        9mm/\gttext/$\ge$/complabel right/node\parent_1}
    {
        \node[comp] (\xname) [below=of node\parent, xshift=\xdir*\xscale] {\xtext};
        \draw (node\parent) to node [\labelopts] {\labeltext} (\xname);
    }
% leaves
\foreach \parent/\lttext/\gttext in {
        _0_0_0/c/b,
        _0_0_1/d/a,
        _0_1_0/d/b,
        _0_1_1/c/a,
        _1_0_0/c/a,
        _1_0_1/d/b,
        _1_1_0/d/a,
        _1_1_1/c/b}
    \foreach \xdir/\xtext/\labeltext/\xname in {
       -4mm/\lttext/$<$/node\parent_0,
        4mm/\gttext/$\ge$/node\parent_1}
    {
        \node[result] (\xname) [below=of node\parent,xshift=\xdir] {\xtext};
        \draw (node\parent) to node [complabel,xshift=\xdir*.5] {\labeltext} (\xname);
    }

% annotate with Hasse diagrams
\newcommand{\orderedpair}[2]{
    \draw (0,3mm) node[hasse,anchor=center] {#1} -- (0,-3mm) node[hasse,anchor=center] {#2}
}

\newcommand{\lefthook}[5]{
    \draw ++(#5.west) +(-1.5mm,0) node[hasse] {#4} -- +(-3.5mm,5mm) node[hasse] {#3} -- +(-5.5mm,0) node[hasse] {#2} -- +(-5.5mm,-6mm) node[hasse] {#1}
}

\newcommand{\righthook}[5]{
    \draw ++(#5.west) +(-1.5mm,-6mm) node[hasse] {#4} -- +(-1.5mm,0mm) node[hasse] {#3} -- +(-3.5mm,5mm) node[hasse] {#2} -- +(-6mm,0) node[hasse] {#1}
}

\newcommand{\linehandle}[5]{
    \draw ++(#5.south) +(0,-2mm) node[hasse] {#1} -- +(0,-7mm) node[hasse] {#2} -- +(0,-12mm) node[hasse] {#3} -- +(0,-17mm) node[hasse] {#4} 
}

\newcommand{\handleleft}[5]{
    \draw ++(#5.south) +(0,-2mm) .. controls +(-3mm,-7mm) .. +(0,-12mm);
    \linehandle{#1}{#2}{#3}{#4}{#5}
}

\newcommand{\handleright}[5]{
    \draw ++(#5.south) +(0,-2mm) .. controls +(3mm,-7mm) .. +(0,-12mm);
    \linehandle{#1}{#2}{#3}{#4}{#5}
}

\newcommand{\flux}[5]{
    \draw ++(#5.south) ++(0,-7mm) node[hasse] {#2} -- +(0,5mm) node[hasse] {#1} +(0,0) -- +(-3mm,-5mm) node[hasse] {#3} +(0,0) -- +(3mm,-5mm) node[hasse] {#4}
}

\newcommand{\fluxleft}[5]{
    \draw ++(#5.south) ++(0,-7mm) +(0,5mm) .. controls +(-3mm,1mm) .. +(-3mm,-5mm);
    \flux{#1}{#2}{#3}{#4}{#5}
}

\newcommand{\fluxright}[5]{
    \draw ++(#5.south) ++(0,-7mm) +(0,5mm) .. controls +(3mm,1mm) .. +(3mm,-5mm);
    \flux{#1}{#2}{#3}{#4}{#5}
}

\node[hasse, left=of node] {a b c d};

\matrix[hasse matrix=node_0] {
    \orderedpair{b}{a}; &
    \node {c d}; \\
};

\matrix[hasse matrix=node_1] {
    \orderedpair{a}{b}; &
    \node {c d}; \\
};

\matrix[hasse matrix=node_0_0] {
    \orderedpair{b}{a}; &
    \orderedpair{d}{c}; \\
};

\matrix[hasse matrix=node_0_1] {
    \orderedpair{b}{a}; &
    \orderedpair{c}{d}; \\
};

\matrix[hasse matrix=node_1_0] {
    \orderedpair{a}{b}; &
    \orderedpair{d}{c}; \\
};

\matrix[hasse matrix=node_1_1] {
    \orderedpair{a}{b}; &
    \orderedpair{c}{d}; \\
};

\lefthook {a}{b}{d}{c}{node_0_0_0};
\righthook{a}{b}{d}{c}{node_0_0_1};
\lefthook {a}{b}{c}{d}{node_0_1_0};
\righthook{a}{b}{c}{d}{node_0_1_1};
\lefthook {b}{a}{d}{c}{node_1_0_0};
\righthook{b}{a}{d}{c}{node_1_0_1};
\lefthook {b}{a}{c}{d}{node_1_1_0};
\righthook{b}{a}{c}{d}{node_1_1_1};

\handleleft {d}{c}{b}{a}{node_0_0_0_0};
\fluxright  {d}{b}{a}{c}{node_0_0_0_1};
\fluxleft   {b}{d}{a}{c}{node_0_0_1_0};
\handleright{b}{a}{d}{c}{node_0_0_1_1};

\handleleft {c}{d}{b}{a}{node_0_1_0_0};
\fluxright  {c}{b}{a}{d}{node_0_1_0_1};
\fluxleft   {b}{c}{a}{d}{node_0_1_1_0};
\handleright {b}{a}{c}{d}{node_0_1_1_1};

\handleleft {d}{c}{a}{b}{node_1_0_0_0};
\fluxright  {d}{a}{b}{c}{node_1_0_0_1};
\fluxleft   {a}{d}{b}{c}{node_1_0_1_0};
\handleright{a}{b}{d}{c}{node_1_0_1_1};

\handleleft {c}{d}{a}{b}{node_1_1_0_0};
\fluxright  {c}{a}{b}{d}{node_1_1_0_1};
\fluxleft   {a}{c}{b}{d}{node_1_1_1_0};
\handleright{a}{b}{c}{d}{node_1_1_1_1};

\end{tikzpicture}
\end{document}
