A Practical Guide to Data Structures and Algorithms using Java

Splay Tree Data Structure 541

OrderedCollection

successor.deleteAndReplaceBy(successor.right);

node.substituteNode(successor);

}

if (node.parent ! = null) //If x’s parent is not already at the root

splay(node.parent, null); //use splay to bring x’s parent to the root

node.parent = successor;

node.markDeleted();

size--;

}

An example call to remove is illustrated in Figure 35.6. First the node containing 18, the successor

of 17, is splayed (using Case 1) to be the top of the subtree rooted at 17. This leaves 18 as the left

child of 21, and 17 as the left child of 18 (not shown). Since there are no elements between 17 and

its successor, it is now guaranteed ...