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.


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