Figure 2

Example of an RR operation. Depicted is an example of an RR operation where T' = RR _T (d). The original tree T is shown in (a). In (b), we first suppress the root node, and then introduce the new root node r above d. Finally we rearrange the tree so that r is at root, as in (c).