Reading material

Section 9.2 (pages 396-399)


Consider an AVL tree. An item is inserted. Let n1 be the first node on the path from the inserted node to the root of the tree that has become unbalanced because of the insertion. Below you find a picture of the subtree rooted at the node n1.

Assume that the item has been inserted in the subtree T2.