Research and Advances

A generalization of AVL trees

A generalization of AVL trees is proposed in which imbalances up to &Dgr; are permitted, where &Dgr; is a small integer. An experiment is performed to compare these trees with standard AVL trees and with balanced trees on the basis of mean retrieval time, of amount of restructuring expected, and on the worst case of retrieval time. It is shown that, by permitting imbalances of up to five units, the retrieval time is increased a small amount while the amount of restructuring required is decreased by a factor of ten. A few theoretical results are derived, including the correction of an earlier paper, and are duly compared with the experimental data. Reasonably good correspondence is found. 0


Author Archives

Research and Advances

A view of computer architecture

An attempt is made to predict the developments of the next 25 years in the field of computer architecture. Standardized, inexpensive microcomputers on a single chip are predicted. These will be used extensively to provide logical functions for noncomputational devices and incidentally for the design of superscale computers.

Shape the Future of Computing

ACM encourages its members to take a direct hand in shaping the future of the association. There are more ways than ever to get involved.

Get Involved