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.

For 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.)

  Loading links to posts on similar topics...