On the correspondence between AVL trees and brother trees. (English) Zbl 0399.68069

Ottmann, Th.; Six, H.-W.; Wood, D.

Computing 23, 43-54 (1979).

MSC:

68R10	Graph theory (including graph drawing) in computer science
68P20	Information storage and retrieval of data
68W99	Algorithms in computer science

Keywords:

Height-Balanced Search Trees; Insertion Algorithms; Brother Trees; Nonstandard Updating Algorithms

References:

[1]	Culik II, K., Ottmann, Th., Wood, D.: Dense multiway trees. Technical Report No. 77, Institut für Angewandte Informatik und Formale Beschreibungsverfahren, Karlsruhe, 1978. · Zbl 0462.68035
[2]	Foster, C. C.: A generalization of AVL trees. Communications of the ACM16, 8, 513–517 (1973). · Zbl 0269.68063
[3]	Knuth, D.: The art of computer programming, Vol. 3, sorting and searching. Reading, Mass.: Addison-Wesley 1973. · Zbl 0302.68010
[4]	Luccio, R., Pagli, L.: On the height of height-balanced trees. IEEE Transactions on ComputersC25, 87–90 (1976). · Zbl 0316.68025
[5]	Melhorn, K.: Effiziente Algorithmen. Stuttgart: Teubner 1977. · Zbl 0357.68041
[6]	Ottmann, Th., Six, H.-W.: Eine neue Klasse von ausgeglichenen Binärbäumen. Angewandte Informatik8, 395–400 (1976). · Zbl 0331.68023
[7]	Ottmann, Th., Six, H.-W., Wood, D.: New results in balanced search trees. Applied Computer Science. München: Carl Hanser 1978. · Zbl 0382.68058
[8]	Ottmann, Th., Six, H.-W., Wood, D.: Right brother trees. Communications of the ACM21, 9, 769–776 (1978). · Zbl 0399.68068
[9]	Ottmann, Th., Six, H.-W., Wood, D.: One-sided k-height-balanced trees. Computing (1979), to appear. · Zbl 0394.68047
[10]	Ottmann, Th., Wood, D.: 1–2 brother trees or AVL trees revisited. The Computer Journal (1979), to appear. · Zbl 0399.68069
[11]	van Leeuwen, J.: The complexity of data organization, in: Foundations of Computer Science, Part I (Apt, de Bakker, eds.). Mathematical Centre Tracts 81, Amsterdam, 37–147 (1976).