Data Structures, Algorithms, & Applications in Java
Chapter 16, Exercise 51
The operation split(theKey, lessThan, greaterThan)
can be done by first doing a get(theKey).
If the splay tree
has an element with key equal to theKey,
then following the
get, the element with key theKey
is in the root of the splay tree. The left subtree of the splay tree
becomes the tree lessThan and the right subtree
becomes the tree greaterThan.
When the splay tree has no element with key equal to theKey,
then following the get either the
root node and its left subtree define the
tree lessThan and the right subtree of the root
defines greaterThan, or the left subtree
of the root defines lessThan and
the root together with its right subtree define greaterThan.