Height-Balanced Trees of Order (beta,gamma,delta).

Shou-Hsuan Stephen Huang: Height-Balanced Trees of Order (beta,gamma,delta). ACM Trans. Database Syst. 10(2): 261-284(1985)

@article{DBLP:journals/tods/Huang85,
  author    = {Shou-Hsuan Stephen Huang},
  title     = {Height-Balanced Trees of Order (beta,gamma,delta)},
  journal   = {ACM Trans. Database Syst.},
  volume    = {10},
  number    = {2},
  year      = {1985},
  pages     = {261-284},
  ee        = {http://doi.acm.org/10.1145/3857.3858, db/journals/tods/Huang85.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

BibTeX

Abstract

We study restricted classes of B-trees, called H(beta, gamma, delta) trees. A class is defined by three parameters: beta, the size of a node; gamma, the minimal number of grandsons a node must have; and delta, the minimal number of leaves bottom nodes must have. This generalizes the brother condition of 2-3 brother trees in a uniform way to B-trees of higher order. The class of B-trees of order m is obtained by choosing beta = m, gamma = (m/2)² and delta = m/2. An algorithm to construct H-trees for any given number of keys is given in Section 1. Insertion and deletion algorithms are given in Section 2. The costs of these algorithms increase smoothly as the parameters are increased. Furthermore, it is proved that the insertion can be done in time O(beta + log N), where N is the number of nodes in the tree. Deletion can also be accomplished without reconstructing the entire tree. Properties of H-trees are given in Section 3. It is shown that the height of H-trees decreases as gamma increases, and the storage utilization increases significantly as delta increases. Finally, comparisons with other restricted classes of B-trees are given in Section 4 to show the attractiveness of H-trees.

Copyright © 1985 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

Joint ACM SIGMOD / IEEE Computer Society Anthology

CDROM Version: Load the CDROM "Volume 3 Issue 1, TODS 1976-1990" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the CD and click on the path of your mount point:
/Anthology/An3-1 or /cdrom

DVD Version: Load ACM SIGMOD Anthology DVD 2" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the DVD and click on the path of your mount point:
/Anthology/aDVD2 or /dvd

BibTeX

References

[1]: Rudolf Bayer, Edward M. McCreight: Organization and Maintenance of Large Ordered Indices. Acta Inf. 1: 173-189(1972) BibTeX
[2]: James R. Bitner, Shou-Hsuan Stephen Huang: Key Comparison Optimal 2-3 Trees with Maximum Utilization. SIAM J. Comput. 10(3): 558-570(1981) BibTeX
[3]: Douglas Comer: The Ubiquitous B-Tree. ACM Comput. Surv. 11(2): 121-137(1979) BibTeX
[4]: Karel Culik II, Thomas Ottmann, Derick Wood: Dense Multiway Trees. ACM Trans. Database Syst. 6(3): 486-512(1981) BibTeX
[5]: ...
[6]: ...
[7]: ...
[8]: ...
[9]: Donald E. Knuth: The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley 1973, ISBN 0-201-03803-X
BibTeX
[10]: Raymond E. Miller, Nicholas Pippenger, Arnold L. Rosenberg, Lawrence Snyder: Optimal 2, 3-Trees. SIAM J. Comput. 8(1): 42-59(1979) BibTeX
[11]: Thomas Ottmann, Douglas Stott Parker Jr., Arnold L. Rosenberg, Hans-Werner Six, Derick Wood: Minimal-Cost Brother Trees. SIAM J. Comput. 13(1): 197-217(1984) BibTeX
[12]: Thomas Ottmann, Derick Wood: 1-2 Brother Trees or AVL Trees Revisited. Comput. J. 23(3): 248-255(1980) BibTeX
[13]: Arnold L. Rosenberg, Lawrence Snyder: Time- and Space-Optimality in B-Trees. ACM Trans. Database Syst. 6(1): 174-193(1981) BibTeX
[14]: Arnold L. Rosenberg, Lawrence Snyder: Minimal-Comparison 2, 3-Trees. SIAM J. Comput. 7(4): 465-480(1978) BibTeX
[15]: Jan van Leeuwen, Mark H. Overmars: Stratified Balanced Search Trees. Acta Inf. 18: 345-359(1982) BibTeX
[16]: Andrew Chi-Chih Yao: On Random 2-3 Trees. Acta Inf. 9: 159-170(1978) BibTeX

Referenced by

Anatoly P. Pinchuk, Konstantin V. Shvachko: Maintaining Dictionaries: Space-Saving Modifications of B-Trees. ICDT 1992: 421-435
Witold Litwin, Djamel Eddine Zegour, Gérard Lévy: Multilevel Trie Hashing. EDBT 1988: 309-335

BibTeX

ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]