Efficient Multiway Radix Search Trees


Úlfar Erlingsson, Mukkai Krishnamoorthy and T.V. Raman. Efficient Multiway Radix Search Trees. Information Processing Letters 60 (1996), pp. 115-120.
(compressed PostScript)

I've also implemented a switch-statement code generator for lcc which uses MRSTs. You can get the C source here.

Abstract

We present a new scheme for building static search trees, using multiway radix search. We apply this method to the problem of code generation for switch statements in imperative languages. For sparse case sets, the method has an advantage over existing methods, empirically requiring fewer than three branches for the average search. We give timing results that show that in practice our method runs faster than other methods on large sparse case sets.


Figure: A Multiway Radix Search Tree