checked on that node' ancestors)we shall first adhere to this evidently correct schema because it can be implemented through pure extension of the already established search and insertion procedures this procedure describes the search operation needed at each single nodeand because of its recursive formulation it can easily accommodate an additional operation on the way back along the search path at each stepinformation must be passed as to whether or not the height of the subtree (in which the insertion had been performedhad increased we therefore extend the procedure' parameter list by the boolean with the meaning the subtree height has increased clearlyh must denote variable parameter since it is used to transmit result assume now that the process is returning to node pfrom the left branch (see fig )with the indication that it has increased its height we now must distinguish between the three conditions involving the subtree heights prior to insertion hl hrp bal + the previous imbalance at has been equilibrated hl hrp bal the weight is now slanted to the left hl hrp bal - rebalancing is necessary in the third caseinspection of the balance factor of the root of the left subtree (sayp baldetermines whether case or case of fig is present if that node has also higher left than right subtreethen we have to deal with case otherwise with case (convince yourself that left subtree with balance factor equal to at its root cannot occur in this case the rebalancing operations necessary are entirely expressed as sequences of pointer reassignments in factpointers are cyclically exchangedresulting in either single or double rotation of the two or three nodes involved in addition to pointer rotationthe respective node balance factors have to be updated the details are shown in the searchinsertionand rebalancing procedures ab fig insertions in balanced tree the working principle is shown by fig consider the binary tree (awhich consists of two nodes only insertion of key first results in an unbalanced tree ( linear listits balancing involves rr single rotationresulting in the perfectly balanced tree (bfurther insertion of nodes and result in an imbalance of the subtree with root this subtree is balanced by an ll single rotation (dthe subsequent insertion of key immediately offsets the balance criterion at the root node balance is thereafter reestablished by the more complicated lr double rotationthe outcome is tree (ethe only candidate for losing balance after next insertion is node indeedinsertion of node must invoke the fourth case of rebalancing outlined belowthe rl double rotation the final tree is shown in fig (