Java Reference
In-Depth Information
that is found to be unbalanced. Deletion is similar; however, consideration for
unbalanced nodes must begin at the level of the
deletemin
operation.
Example13.3
In Figure 13.4 (b), the bottom-most unbalanced node has
value 7. The excess node (with value 5) is in the right subtree of the left
child of 7, so we have an example of Case 2. This requires a double rotation
to fix. After the rotation, 5 becomes the left child of 24, 2 becomes the left
child of 5, and 7 becomes the right child of 5.
13.2.2
The Splay Tree
Like the AVL tree, the splay tree is not actually a distinct data structure, but rather
reimplements the BST insert, delete, and search methods to improve the perfor-
mance of a BST. The goal of these revised methods is to provide guarantees on the
time required by a series of operations, thereby avoiding the worst-case linear time
behavior of standard BST operations. No single operation in the splay tree is guar-
anteed to be efficient. Instead, the splay tree access rules guarantee that a series
of m operations will take O(m log n) time for a tree of n nodes whenever m n.
Thus, a single insert or search operation could take O(n) time. However, m such
operations are guaranteed to require a total of O(m log n) time, for an average cost
of O(log n) per access operation. This is a desirable performance guarantee for any
search-tree structure.
Unlike the AVL tree, the splay tree is not guaranteed to be height balanced.
What is guaranteed is that the total cost of the entire series of accesses will be
cheap. Ultimately, it is the cost of the series of operations that matters, not whether
the tree is balanced. Maintaining balance is really done only for the sake of reaching
this time efficiency goal.
The splay tree access functions operate in a manner reminiscent of the move-
to-front rule for self-organizing lists from Section 9.2, and of the path compres-
sion technique for managing parent-pointer trees from Section 6.2. These access
functions tend to make the tree more balanced, but an individual access will not
necessarily result in a more balanced tree.
Whenever a node S is accessed (e.g., when S is inserted, deleted, or is the goal
of a search), the splay tree performs a process called splaying. Splaying moves S
to the root of the BST. When S is being deleted, splaying moves the parent of S to
the root. As in the AVL tree, a splay of node S consists of a series of rotations.
A rotation moves S higher in the tree by adjusting its position with respect to its
parent and grandparent. A side effect of the rotations is a tendency to balance the
tree. There are three types of rotation.
A single rotation is performed only if S is a child of the root node. The single
rotation is illustrated by Figure 13.7. It basically switches S with its parent in a
