On Digital Search Trees: A Simple Method for Constructing Balanced Binary Trees
Abstract
This paper presents digital search trees, a binary tree data structure
that can produce well-balanced trees in the
majority of cases. Digital search tree algorithms are reviewed, and a
novel algorithm for building sorted trees
is introduced. It was found that digital search trees are simple to
implement because their code is similar to the
code for ordinary binary search trees. Experimental evaluation was
performed and the results are presented. It
was found that digital search trees, in addition to being conceptually
simpler, often outperform other popular
balanced trees such as AVL or red-black trees. It was found that good
performance of digital search trees is
due to better exploitation of cache locality in modern computers.
Reference
F. Plavec, Z. G. Vranesic, Stephen D. Brown, "On Digital Search Trees: A Simple Method for Constructing Balanced Binary Trees", in Proceedings of the 2nd International Conference on Software and Data Technologies (ICSOFT '07), vol. 1, Barcelona, Spain, July, 2007, pp. 61-68.
(Download Full Paper)