A new class of balanced search trees : half-balanced binary search tress
Olivié, H. J.
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 16 (1982), p. 51-71 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 1982-01-01
@article{ITA_1982__16_1_51_0,
     author = {Olivi\'e, H. J.},
     title = {A new class of balanced search trees : half-balanced binary search tress},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {16},
     year = {1982},
     pages = {51-71},
     mrnumber = {677655},
     zbl = {0489.68056},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_1982__16_1_51_0}
}

Olivié, H. J. A new class of balanced search trees : half-balanced binary search tress. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 16 (1982) pp. 51-71. http://gdmltest.u-ga.fr/item/ITA_1982__16_1_51_0/

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. | MR 156719

2. A. V. Aho, J. E. Hopcroft and J. D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, Mass., 1974. | MR 413592 | Zbl 0326.68005

3. R. Bayer, Symmetric Binary B-trees Data Structure and Maintenance Algorithms, Acta Informatica, Vol. 1, 1972, pp. 290-306. | MR 323192 | Zbl 0233.68009

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. | MR 568093 | Zbl 0399.05022

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. | Zbl 0317.68044

6. D. E. Knuth, The Art of Computer Programming, Vol. 1, Fundamental Algorithms, Addison-Wesley, Reading, Mass., 1968, 1973. | MR 378456

7. D. E. Knuth, The Art of Computer Programming, Vol. 3, Sorting and Searching, Addison-Wesley, Reading, Mass., 1973. | MR 445948 | Zbl 0302.68010

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. | MR 331903 | Zbl 0262.68012

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. 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.