Two New Kinds of Biased Search Trees

Two New Kinds of Biased Search Trees By J. FEIGENBAUM* and R. E. TARjAN* (Manuscript received May 20, 1983) In this paper, we introduce two new kinds of biased search trees: biased, a, b trees and pseudo-weight-balanced trees. A biased search tree is a data structure for storing a sorted set in which the access time for an item depends on its estimated access frequency in such a way that the average access time is small. Bent, Sleator, and Tarjan were the first to describe classes of biased search trees that are easy to update; such trees have applications not only in efficient table storage but also in various network optimization algorithms. Our biased a, b trees generalize the biased 2, b trees of Bent, Sleator, and Tarjan. They provide a biased generalization of B-trees and are suitable for use in paged external memory, whereas previous kinds of biased trees are suitable for internal memory. Our pseudo-weight-balanced trees are a biased version of weight-balanced trees much simpler than Bent's version. Weight balance is the natural kind of balance to use in designing biased trees; pseudoweight-balanced trees are especially easy to implement and analyze. I. INTRODUCTION T h e following problem, which we shall call the dictionary problem, occurs frequently in computer science. Given a totally ordered universe U, we wish to maintain one or more subsets of U under the following operations, where R and S denote any subsets of U and i denotes any item in U: access (i, S)--If item i is in S, return a pointer to its location.