Java Reference
In-Depth Information
G
P
S
D
S
P
G
A
B
C
A
B
C
D
(A)
(B)
Figure13.8
Splay tree zigzag rotation. (a) The original tree with S, P, and G
in zigzag formation. (b) The tree after the rotation takes place. The positions of
subtrees A, B, C, and D are altered as appropriate to maintain the BST property.
G
S
P
P
D
A
S
G
C
B
A
B
C
D
(A)
(B)
Figure13.9
Splay tree zigzig rotation. (a) The original tree with S, P, and G
in zigzig formation. (b) The tree after the rotation takes place. The positions of
subtrees A, B, C, and D are altered as appropriate to maintain the BST property.
Note that zigzag rotations tend to make the tree more balanced, because they
bring subtrees B and C up one level while moving subtree D down one level. The
result is often a reduction of the tree's height by one. Zigzig promotions and single
rotations do not typically reduce the height of the tree; they merely bring the newly
accessed record toward the root.
Splaying node S involves a series of double rotations until S reaches either the
root or the child of the root. Then, if necessary, a single rotation makes S the root.
This process tends to re-balance the tree. Regardless of balance, splaying will make
frequently accessed nodes stay near the top of the tree, resulting in reduced access
cost. Proof that the splay tree meets the guarantee of O(m log n) is beyond the
scope of this topic. Such a proof can be found in the references in Section 13.4.
