needing individual treatment the remaining ones can be derived by symmetry considerations from those two case is characterized by inserting keys or in the tree of fig case by inserting nodes or the two cases are generalized in fig in which rectangular boxes denote subtreesand the height added by the insertion is indicated by crosses simple transformations of the two structures restore the desired balance their result is shown in fig note that the only movements allowed are those occurring in the vertical directionwhereas the relative horizontal positions of the shown nodes and subtrees must remain unchanged case case fig imbalance resulting from insertion case case fig restoring the balance an algorithm for insertion and rebalancing critically depends on the way information about the tree' balance is stored an extreme solution lies in keeping balance information entirely implicit in the tree structure itself in this casehowevera node' balance factor must be rediscovered each time it is affected by an insertionresulting in an excessively high overhead the other extreme is to attribute an explicitly stored balance factor to every node the definition of the type node is then extended into type node pointer to record keycountbalinteger(*bal - + *leftrightnode end we shall subsequently interpret node' balance factor as the height of its right subtree minus the height of its left subtreeand we shall base the resulting algorithm on this node type the process of node insertion consists essentially of the following three consecutive parts follow the search path until it is verified that the key is not already in the tree insert the new node and determine the resulting balance factor retreat along the search path and check the balance factor at each node rebalance if necessary although this method involves some redundant checking (once balance is establishedit need not be