Istituto di Scienza e Tecnologie dell'Informazione     
Sprugnoli R. Pseudo-balanced binary trees. Internal note IEI-B77-16, 1977.
We propose in the present paper a method to keep a binary tree "balanced", even if the elements are added to the tree in their proper order. The kernel of the method is a procedure which allows us to attach a new element to a binary tree at a predefined level. This insertion procedure is accomplished in time o(1n n) and maintains all the properties of binary trees. Elements are inserted in the tree according to suitable probability distribution function of the levels. Empirical evidence is given that the average searching time is of order 0(1n n) also for the trees constructed by our method and corresponding to the sorted permutation.

Icona documento 1) Download Document PDF

Icona documento Open access Icona documento Restricted Icona documento Private


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional