An Insertion Technique for One-Sided Height-Balanced Trees

A restriction on height-balanced binary trees
is presented.  It is seen that this restriction 
reduces the extra memory requirements by half (from
two extra bits per node to one) and maintains fast 
search capabilities at a cost of increased
time requirements for inserting new nodes.

CACM August, 1976

Hirschberg, D. S.

balanced, binary, search, trees

3.73 3.74 4.34 5.25 5.31

CA760805 JB January 4, 1978  10:04 AM

2839	4	2839
3042	4	2839
3096	4	2839
3163	4	2839
2839	5	2839
2839	5	2839
2839	5	2839
2889	5	2839
3009	5	2839
3042	5	2839
3065	5	2839
3096	5	2839
3163	5	2839
2455	6	2839
2839	6	2839
2839	6	2839
2839	6	2839
2839	6	2839
2839	6	2839
2889	6	2839
2889	6	2839
2889	6	2839
2968	6	2839
3009	6	2839
3009	6	2839
3065	6	2839
3096	6	2839
3096	6	2839