SELF-ADJUSTING MULTIWAY SEARCH-TREES

We introduce a new data structure, the k-forest, which is a self-adjusting multi-way search tree. A k-forest provides an efficient implementation of a weighted Dictionary in a virtual memory environment where the time to access a tree node is much greater than the time to examine data items in a node. We achieve results that are natural generalizations of the Working Set and Static Optimality theorems of Sleator and Tarjan for splay trees. Thus we are able to show that even when the lookup frequencies of the elements of the dictionary are not known in advance, a k-forest can equal or exceed the performance of an optimal static multi-way tree which is built knowing the lookup frequencies in advance.