A new class of balanced search trees: Half-balanced binary search trees. (English) Zbl 0489.68056


68R10 Graph theory (including graph drawing) in computer science
68P10 Searching and sorting
68Q25 Analysis of algorithms and problem complexity
Full Text: EuDML


[1] 1. G. M. ADELSON-VELSKII and E. M. LANDIS, An Algorithm for the Organization of Information, Dokl. Akad. Nauk S.S.S.R., Vol. 146, 1962, pp. 263-266 (Russian). English translation in Soviet Math. Dokl., Vol. 3, 1962, pp. 1259-1263. MR156719
[2] 2. A. V. AHO, J. E. HOPCROFT and J. D. ULLMAN, The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, Mass., 1974. Zbl0326.68005 MR413592 · Zbl 0326.68005
[3] 3. R. BAYER, Symmetric Binary B-trees Data Structure and Maintenance Algorithms, Acta Informatica, Vol. 1, 1972, pp. 290-306. Zbl0233.68009 MR323192 · Zbl 0233.68009 · doi:10.1007/BF00289509
[4] 4. N. BLUM and K. MEHLHORM, Mittlere Anzahl von Rebalancierungoperationen in Gewichtsbalancierten Bäumen, 4th GI Conference on Theoretical Computer Science, Aachen 1979, Lecture Notes in Computer Science, Vol. 67, pp. 67-78, Springer, Berlin, Heidelberg, New York. Zbl0399.05022 MR568093 · Zbl 0399.05022
[5] 5. P. L. KARLTON, S. H. FULLER, R. E. SCROGGS and E. B. KAEHLER, Performance of Height-Balanced Trees, Com. A.C.M. 19, Vol. 1, 1976, pp. 23-28. Zbl0317.68044 · Zbl 0317.68044 · doi:10.1145/359970.359989
[6] 6. D. E. KNUTH, The Art of Computer Programming, Vol. 1, Fundamental Algorithms, Addison-Wesley, Reading, Mass., 1968, 1973. MR378456 · Zbl 0191.17903
[7] 7. D. E. KNUTH, The Art of Computer Programming, Vol. 3, Sorting and Searching, Addison-Wesley, Reading, Mass., 1973. Zbl0302.68010 MR445948 · Zbl 0302.68010
[8] 8. J. NIEVERGELT and E. M. Reingold, Binary Search Trees of Bounded Balance, S.I.A.M. J. Comput., Vol. 2, 1973, pp. 33-43. Zbl0262.68012 MR331903 · Zbl 0262.68012 · doi:10.1137/0202005
[9] 9. H. J. OLIVIÉ, A New Class of Balanced Search Trees: Half-Balanced Binary Searc Trees, Technical Report 80-02, IHAM, Paardenmarkt 94, B-2000 Antwerp, Belgium, 1980.
[10] 10. H. J. OLIVIÉ, A Study of Balanced Binary Trees and Balanced One-Two Trees, Ph. D. Thesis, Dept. of Mathematics, U.I.A., University of Antwerp, Belgium, 1980.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.