PCPlus 282: Understanding ternary trees

June 2009’s article was a reversion to what might be called straight computer science after a few months of layman’s topics (indexing the internet, spellchecking, etc) and covered ternary trees. Quick overview: ternary trees are a speedy, space-efficient data structure for storing large numbers of key-value pairs that in certain situations are better than hash tables.

PCPlus logoFor some reason, ternary trees really gelled with me way back when I first found out about them. They were invented by Jon Bentley and Robert Sedgewick and first described in Dr Dobbs in April 1998 (article). I actually wrote about them in June 1998 in The Delphi Magazine (a pretty quick turn-around, considering it had code as well — although buggy as I discovered later) and presented a session on them at DCON 1999 (with corrected code). So it was good to get back to them some 11 years later for another audience.

The article does a pretty good job discussing the precursors to the invention and shows why ternary trees are so important for key-value lists.

For some reason, although there were a couple of nice images of trees that enhanced the article, the editor or page designer put in a picture of a Sierpinski triangle (or gasket, as it’s sometimes known) which, unfortunately has nothing to do with ternary trees. Well, apart from the association with “three” I suppose.

This article first appeared in issue 282, June 2009.

You can download the PDF here.

(I write a monthly column for PCPlus, a computer news-views-n-reviews magazine in the UK (actually there are 13 issues a year — there’s an Xmas issue as well — so it’s a bit more than monthly). The column is called Theory Workshop and appears in the Make It section of the magazine. When I signed up, my editor and the magazine were gracious enough to allow me to reprint the articles here after say a year or so.)

Album cover for PromiseNow playing:
Sade - War of the Hearts
(from Promise)

Loading similar posts...   Loading links to posts on similar topics...

No Responses

Feel free to add a comment...

Leave a response

Note: some MarkDown is allowed, but HTML is not. Expand to show what's available.

  •  Emphasize with italics: surround word with underscores _emphasis_
  •  Emphasize strongly: surround word with double-asterisks **strong**
  •  Link: surround text with square brackets, url with parentheses [text](url)
  •  Inline code: surround text with backticks `IEnumerable`
  •  Unordered list: start each line with an asterisk, space * an item
  •  Ordered list: start each line with a digit, period, space 1. an item
  •  Insert code block: start each line with four spaces
  •  Insert blockquote: start each line with right-angle-bracket, space > Now is the time...
Preview of response