Saturday, November 30, 2013

Splaying

Splaying is the process that makes splay trees unique from a standard binary tree:

Splaying is a recursive function which takes node x and rotates it to the root of the tree.

Splaying performs three rotation types; Zig rotations, Zig-Zag Two rotations, and Zig-Zag rotations. Zig rotations are single rotations that occur when x is the left child of its parent, which is the root node. Zig-Zig rotations is a double zig rotation that occurs when node x is the left child of its parent, which is the left child of x's grandparent. Lastly, Zig-Zag rotations are double rotations that occur when node x is the right child of its parent, which is the left child of x's grandparent.

No comments:

Post a Comment