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