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