Take the 2-minute tour ×
TeX - LaTeX Stack Exchange is a question and answer site for users of TeX, LaTeX, ConTeXt, and related typesetting systems. It's 100% free, no registration required.

I was wondering if anybody knows how to draw a multiway tree like in Knuth's The Art of Computer Programming, Volume 3 on page 484?

This looks like a rounded box with the value of the keys being rotated 90 degrees leftwards/counter clockwise and leaf nodes as little squares, with pointers to the next nodes halfway between keys.

Here is how it looks in print

share|improve this question
    
Thanks for adding the picture. –  egreg Feb 5 at 23:01
add comment

1 Answer 1

up vote 12 down vote accepted

A basic approach using TikZ:

\documentclass{article}
\usepackage{graphicx}
\usepackage{tikz}
\usetikzlibrary{positioning}

\newcommand\Rot[2][90]{%
  \rotatebox[origin=c]{#1}{#2}}
\begin{document}

\begin{tikzpicture}[
  node distance=2cm and 1cm,
  mynoder/.style={draw,rounded corners},
  mysq/.style={draw}
]
\node[mynoder,text depth=0.4cm] (root) 
  {\quad$\cdots$\ \ \Rot{$031$}\qquad\Rot{$067$}\qquad\Rot{$097$}\ \ $\cdots$\quad\null};
\node[mynoder,below = of root.south west,anchor=west,text depth=0.8cm] (left) 
  {\Rot{$041$}\quad\Rot{$057$}\quad\Rot{$059$}};
\node[mynoder,below = of root.south east,anchor=east,text depth=0.8cm] (right) 
  {\Rot{$041$}\quad\Rot{$057$}\quad\Rot{$059$}};

\draw ([xshift=-10pt]root.center) -- (left);
\draw ([xshift=10pt]root.center) -- (right);
\foreach \Nodo in {left,right}
{
  \foreach \Corr in {-15,-5,5,15}
  {
    \path ([yshift=-0.2cm,xshift=\Corr]\Nodo.center) -- ++(0,-1.5cm) node[mysq] (\Nodo\Corr) {};
    \draw ([yshift=-0.2cm,xshift=\Corr]\Nodo.center) -- (\Nodo\Corr);
  }
}
\end{tikzpicture}

\end{document}

enter image description here

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.