A Generalization of AVL Trees A generalization of AVL trees is proposed in which imbalances up to (triangle shape) 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. CACM August, 1973 Foster, C. C. AVL trees, balanced trees, information storage and retrieval 3.7 3.72 4.49 5.31 CA730819 JB January 23, 1978 10:13 AM 2455 4 2455 2455 4 2455 2493 4 2455 2889 4 2455 2968 4 2455 2278 5 2455 2388 5 2455 2455 5 2455 2455 5 2455 2455 5 2455 2889 5 2455 2968 5 2455 3042 5 2455 2138 6 2455 2388 6 2455 2388 6 2455 2455 6 2455 2455 6 2455 2455 6 2455 2839 6 2455 2889 6 2455 2968 6 2455