Improving partial rebuilding by using simple balance criteria. (English) Zbl 0767.68016

Algorithms and data structures, Proc. workshop WADS ’89, Ottawa/Canada 1989, Lect. Notes Comput. Sci. 382, 393-402 (1989).
Summary: [For the entire collection see Zbl 0753.00021.]
Some new classes of balanced trees, defined by very simple balance criteria, are introduced. Those trees can be maintained by partial rebuilding at lower update cost than previously used weight-balanced trees. The used balance criteria also allow us to maintain a balanced tree without any balance information stored in the nodes.


68P05 Data structures


Zbl 0753.00021