“Left rotation”的意思、由来-开放百科全书

词条

Left rotation

释义

Tree Rotation
References

Left rotation refers to the following

In an array, moving all items to the next lower location. The first item is moved to the last location, which is now vacant.
In a list, removing the head and inserting it at the tail.

Tree Rotation

In a binary search tree, a left rotation is the movement of a node, X, down to the left. This rotation assumes that X has a right child (or subtree). X's right child, R, becomes X's parent node and R's left child becomes X's new right child. This rotation is done to balance the tree; specifically when the right subtree of node X has a significantly (depends on the type of tree) greather height than its left subtree.

Left rotations (and right) are order preserving in a binary search tree; it preserves the binary search tree property (an in-order traversal of the tree will yield the keys of the nodes in proper order). AVL trees and red-black trees are two examples of binary search trees that use the left rotation.

A single left rotation is done in O(1) time but is often integrated within the node insertion and deletion of binary search trees. The rotations are done to keep the cost of other methods and tree height at a minimum.

References

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, 2001, Introduction to Algorithms, second edition. McGraw-Hill, {{ISBN|0-07-013151-1}}. Chapter 13.

1 : Trees (data structures)

随便看

开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。