A generalization of AVL trees
- 1 August 1973
- journal article
- Published by Association for Computing Machinery (ACM) in Communications of the ACM
- Vol. 16 (8) , 513-517
- https://doi.org/10.1145/355609.362340
Abstract
A generalization of AVL trees is proposed in which imbalances up to Δ are permitted, where Δ 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.Keywords
This publication has 4 references indexed in Scilit:
- On Foster's information storage and retrieval using AVL treesCommunications of the ACM, 1972
- Optimizing binary trees grown with a sorting algorithmCommunications of the ACM, 1972
- A balanced tree storage and retrieval algorithmPublished by Association for Computing Machinery (ACM) ,1971
- Information retrievalPublished by Association for Computing Machinery (ACM) ,1965