Java Reference
In-Depth Information
17
17
92
92
G
25
99
25
P
99
18
42
G
18
89
S
72
P
72
89
S
42
75
75
(A)
(B)
17 P
89
89
S
17
92
25
92
25
99
18
72
99
18
72
42
75
42
75
(C)
(D)
Figure13.10
Example of splaying after performing a search in a splay tree.
After finding the node with key value 89, that node is splayed to the root by per-
forming three rotations. (a) The original splay tree. (b) The result of performing
a zigzig rotation on the node with key value 89 in the tree of (a). (c) The result
of performing a zigzag rotation on the node with key value 89 in the tree of (b).
(d) The result of performing a single rotation on the node with key value 89 in the
tree of (c). If the search had been for 91, the search would have been unsuccessful
with the node storing key value 89 being that last one visited. In that case, the
same splay operations would take place.
