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:
“Modern tourist guides have helped raised tourist expectations. And they have provided the natives—from Kaiser Wilhelm down to the villagers of Chichacestenango—with a detailed and itemized list of what is expected of them and when. These are the up-to- date scripts for actors on the tourists’ stage.”
—Daniel J. Boorstin (b. 1914)
“Each truth that a writer acquires is a lantern, which he turns full on what facts and thoughts lay already in his mind, and behold, all the mats and rubbish which had littered his garret become precious. Every trivial fact in his private biography becomes an illustration of this new principle, revisits the day, and delights all men by its piquancy and new charm.”
—Ralph Waldo Emerson (1803–1882)