TY - JOUR
T1 - Two New Kinds of Biased Search Trees
AU - Feigenbaum, J.
AU - Tarjan, R. E.
PY - 1983/12
Y1 - 1983/12
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=0020909472&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0020909472&partnerID=8YFLogxK
U2 - 10.1002/j.1538-7305.1983.tb03469.x
DO - 10.1002/j.1538-7305.1983.tb03469.x
M3 - Article
AN - SCOPUS:0020909472
SN - 0005-8580
VL - 62
SP - 3139
EP - 3158
JO - Bell System Technical Journal
JF - Bell System Technical Journal
IS - 10
ER -