Two New Kinds of Biased Search Trees

J. Feigenbaum, R. E. Tarjan

Research output: Contribution to journalArticlepeer-review

14 Scopus citations

Abstract

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; pseudo‐weight‐balanced trees are especially easy to implement and analyze.

Original languageEnglish (US)
Pages (from-to)3139-3158
Number of pages20
JournalBell System Technical Journal
Volume62
Issue number10
DOIs
StatePublished - Jan 1 1983

All Science Journal Classification (ASJC) codes

  • Engineering(all)

Fingerprint Dive into the research topics of 'Two New Kinds of Biased Search Trees'. Together they form a unique fingerprint.

Cite this