Biased Search Trees
Authors:
- Samuel W. BentSBSamuel W. Bent
- Daniel D. SleatorDSDaniel D. Sleator
- Robert E. TarjanRTRobert E. Tarjan
- 1 August 1985
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 14 (3) , 545-568
Abstract
We consider the problem of storing items from a totally ordered set in a search tree so that the access time for a given item depends on a known estimate of the access frequency of the item. We describe two related classes of biased search trees whose average access time is within a constant factor of the minimum and that are easy to update under insertions, deletions and more radical update operations. We present and analyze efficient update algorithms for biased search trees. We list several applications of such trees.Keywords
This publication has 23 references indexed in Scilit:
- Two New Kinds of Biased Search TreesBell System Technical Journal, 1983
- Multidimensional B-tree: An efficient dynamic file structure for exact match queries1980
- Binary Trees Optimum Under Various CriteriaSIAM Journal on Applied Mathematics, 1979
- A dichromatic framework for balanced trees1978
- A New Algorithm for Minimum Cost Binary TreesSIAM Journal on Computing, 1977
- Organization and maintenance of large ordered indexesActa Informatica, 1972
- Symmetric binary B-Trees: Data structure and maintenance algorithmsActa Informatica, 1972
- Optimal Computer Search Trees and Variable-Length Alphabetical CodesSIAM Journal on Applied Mathematics, 1971
- Optimum binary search treesActa Informatica, 1971
- A Method for the Construction of Minimum-Redundancy CodesProceedings of the IRE, 1952