Power Trees

The new class of Pk trees is presented, where
height balance is maintained for the nodes Iying 
on particular paths.  The number of nodes of a Pk tree
asymptotically grows as a power of the height, 
in the worst case.  A procedure for node insertion is given,
and the class of trees  considered is restricted 
to IPk trees, which are buildable by such a procedure.
 The average behavior of such trees, studied by 
an extensive set of simulation runs, is close to that
of AVL trees.  In particular, the family of IPO 
trees whose main advantage is the reduced number of
restructurings required after node insertion, is 
analyzed.

CACM November, 1978

Luccio, F.
Pagli, L.

Binary search trees, Pk trees, IPk trees, search
length, node insertion, subtree rotation

3.73 3.74 4.34 5.25 5.31

CA781109 DH January 25, 1979  4:29 PM

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