# Multiway trees like in Knuth's The Art of Computer Programming, Volume 3

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.

-
Thanks for adding the picture. –  egreg Feb 5 at 23:01

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}


-