0

I'm trying to create a Binary Search Tree with Linked Lists on every node, something like the picture but the blue arrows are not desired. I'm currently using tikz-qtree to create my trees.

Current tree:

\tikzset{every tree node/.style={minimum width=2em,draw,circle},
     blank/.style={draw=none},
     edge from parent/.style=
     {draw, edge from parent path={(\tikzparentnode) -- (\tikzchildnode)}},
     level distance=1.5cm}
\begin{tikzpicture}
  \Tree
  [.2,1
    [.1,2
      [.0,2
        \edge[blank]; \node[blank]{};
        [.0,3
          \edge[blank]; \node[blank]{};
          [.0,4 ]
        ]
      ]
      [.1,4 ]
    ]
    [.2,2 ]
  ]
  \end{tikzpicture}

BST with linked list

  • I can draw simple tree, but I don't know how I can add a linked list to a node. I posted the current tree code. BST means binary search tree. – Nicolò Ciraci Sep 12 '16 at 14:34
  • the shown tree does not look like a BST (binary Search Tree) to me. more like a left shifted disfigured tree. maybe if you could clearify you intentions, the community could provide better help. – naphaneal Sep 12 '16 at 14:44
  • I don't understand how I can be more specific, I would like that my tree have a linked list starting from every node, just like the picture below. What is the problem with the tree? It is a not balanced binary search tree using two key for comparison. – Nicolò Ciraci Sep 12 '16 at 14:47
  • 1
    You can just use TikZ to add the list nodes since you're using tikz-qtree. I'd use Forest, but that's because I like it and could probably automate it so Forest placed all or most of the list nodes for me. tikz-qtree doesn't have the same power, but you can use the full power of TikZ to do the job. – cfr Sep 12 '16 at 15:22
  • In any case, please provide complete code. How is blank defined? Presumably you are loading tikz-qtree? Anything else needed for the example? (Or does tikz-qtree defineblank?) – cfr Sep 12 '16 at 15:35
1

Here's how I would do it. This solution defines a forest style binary search tree.

For each node within the tree, it is possible to typeset a second node to the right or left, to contain the list. If this is desired, the content of the node should be specified in the form

<content of main node>:<content of secondary node>

Because the contents of all nodes include commas in this case, the form

{<content of main node>}:{<content of secondary node>}

is needed. Translating your code and adding some secondary nodes, for example,

\begin{forest}
  binary search tree,
  [{2,1}:{1,1}
    [{1,2}:{0,1}
      [{0,2}:{2,2}
        [,phantom]
        [{0,3}:{1,4}
          [,phantom]
          [{0,4}:{-3,0}]
        ]
      ]
      [{1,4}:{0,-1}]
    ]
    [{2,2}:{-1,1}]
  ]
\end{forest}

produces

binary search tree

You said that the blue/green arrows were not required, so I've left the tree plain. However, these could easily be added using the tikz or tikz+ keys, if desired.

Complete code:

\documentclass[border=10pt,multi,tikz]{standalone}
\usepackage{forest}
\forestset{%
  list me/.style={draw, no edge},
  list node/.style={%
    if level=0{%
      label={[draw, anchor=east, label distance=5pt]left:{#1}},
    }{%
      if n=1{%
        insert before={[{#1}, list me]},
      }{%
        if={strequal((content("!u1")),"")}{%
          for nodewalk={fake=u,n=1}{%
            insert before={[{#1},phantom]},
          },
        }{},
        insert after={[{#1}, list me]},
      },
    },
  },
  binary search tree/.style={%
    for tree={%
      circle,
      draw,
    },
    delay={%
      for tree={%
        split option={content}{:}{content,list node},
      },
    },
    before typesetting nodes={%
      where content={}{%
        if nodewalk valid={s}{%
          content/.wrap pgfmath arg={##1}{content("!s")},
        }{},
      }{},
    },
  },
}
\begin{document}
\begin{forest}
  binary search tree,
  [{2,1}:{1,1}
    [{1,2}:{0,1}
      [{0,2}:{2,2}
        [,phantom]
        [{0,3}:{1,4}
          [,phantom]
          [{0,4}:{-3,0}]
        ]
      ]
      [{1,4}:{0,-1}]
    ]
    [{2,2}:{-1,1}]
  ]
\end{forest}
\end{document}

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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