Java Reference
In-Depth Information
P
S
S
P
A
C
A
B
B
C
(A)
(B)
Figure13.7
Splay tree single rotation. This rotation takes place only when
the node being splayed is a child of the root. Here, node S is promoted to the
root, rotating with node P. Because the value of S is less than the value of P,
P must become S's right child. The positions of subtrees A, B, and C are altered
as appropriate to maintain the BST property, but the contents of these subtrees
remains unchanged. (a) The original tree with P as the parent. (b) The tree after
a rotation takes place. Performing a single rotation a second time will return the
tree to its original shape. Equivalently, if (b) is the initial configuration of the tree
(i.e., S is at the root and P is its right child), then (a) shows the result of a single
rotation to splay P to the root.
way that retains the BST property. While Figure 13.7 is slightly different from
Figure 13.5, in fact the splay tree single rotation is identical to the AVL tree single
rotation.
Unlike the AVL tree, the splay tree requires two types of double rotation. Dou-
ble rotations involve S, its parent (call it P), and S's grandparent (call it G). The
effect of a double rotation is to move S up two levels in the tree.
The first double rotation is called a zigzag rotation. It takes place when either
of the following two conditions are met:
1. S is the left child of P, and P is the right child of G.
2. S is the right child of P, and P is the left child of G.
In other words, a zigzag rotation is used when G, P, and S form a zigzag.
The
zigzag rotation is illustrated by Figure 13.8.
The other double rotation is known as a zigzig rotation. A zigzig rotation takes
place when either of the following two conditions are met:
1. S is the left child of P, which is in turn the left child of G.
2. S is the right child of P, which is in turn the right child of G.
Thus, a zigzig rotation takes place in those situations where a zigzag rotation is not
appropriate. The zigzig rotation is illustrated by Figure 13.9. While Figure 13.9
appears somewhat different from Figure 13.6, in fact the zigzig rotation is identical
to the AVL tree double rotation.
