Detailed Illustration
When a subtree is rotated, the subtree side upon which it is rotated decreases its height by one node while the other subtree increases its height. This makes tree rotations useful for rebalancing a tree.
Using the terminology of Root for the parent node of the subtrees to rotate, Pivot for the node which will become the new parent node, RS for rotation side upon to rotate and OS for opposite side of rotation. In the above diagram for the root Q, the RS is C and the OS is P. The pseudo code for the rotation is:
Pivot = Root.OS Root.OS = Pivot.RS Pivot.RS = Root Root = PivotThis is a constant time operation.
The programmer must also make sure that the root's parent points to the pivot after the rotation. Also, the programmer should note that this operation may result in a new root for the entire tree and take care to update pointers accordingly.
Read more about this topic: Tree Rotation
Famous quotes containing the words detailed and/or illustration:
“... every event has had its cause, and nothing, not the least wind that blows, is accident or causeless. To understand what happens now one must find the cause, which may be very long ago in its beginning, but is surely there, and therefore a knowledge of history as detailed as possible is essential if we are to comprehend the past and be prepared for the future.”
—Pearl S. Buck (1892–1973)
“An illustration is no argument,—nor do I maintain the wiping of a looking-glass clean, to be a syllogism;Mbut you all, may it please your worships, see the better for it.”
—Laurence Sterne (1713–1768)