+/* Return the node in SP with the greatest key. */
+
+splay_tree_node
+splay_tree_max (sp)
+ splay_tree sp;
+{
+ splay_tree_node n = sp->root;
+
+ if (!n)
+ return NULL;
+
+ while (n->right)
+ n = n->right;
+
+ return n;
+}
+
+/* Return the node in SP with the smallest key. */
+
+splay_tree_node
+splay_tree_min (sp)
+ splay_tree sp;
+{
+ splay_tree_node n = sp->root;
+
+ if (!n)
+ return NULL;
+
+ while (n->left)
+ n = n->left;
+
+ return n;
+}
+
+/* Return the immediate predecessor KEY, or NULL if there is no
+ predecessor. KEY need not be present in the tree. */
+
+splay_tree_node
+splay_tree_predecessor (sp, key)
+ splay_tree sp;
+ splay_tree_key key;
+{
+ int comparison;
+ splay_tree_node node;
+
+ /* If the tree is empty, there is certainly no predecessor. */
+ if (!sp->root)
+ return NULL;
+
+ /* Splay the tree around KEY. That will leave either the KEY
+ itself, its predecessor, or its successor at the root. */
+ splay_tree_splay (sp, key);
+ comparison = (*sp->comp)(sp->root->key, key);
+
+ /* If the predecessor is at the root, just return it. */
+ if (comparison < 0)
+ return sp->root;
+
+ /* Otherwise, find the rightmost element of the left subtree. */
+ node = sp->root->left;
+ if (node)
+ while (node->right)
+ node = node->right;
+
+ return node;
+}
+
+/* Return the immediate successor KEY, or NULL if there is no
+ successor. KEY need not be present in the tree. */
+
+splay_tree_node
+splay_tree_successor (sp, key)
+ splay_tree sp;
+ splay_tree_key key;
+{
+ int comparison;
+ splay_tree_node node;
+
+ /* If the tree is empty, there is certainly no successor. */
+ if (!sp->root)
+ return NULL;
+
+ /* Splay the tree around KEY. That will leave either the KEY
+ itself, its predecessor, or its successor at the root. */
+ splay_tree_splay (sp, key);
+ comparison = (*sp->comp)(sp->root->key, key);
+
+ /* If the successor is at the root, just return it. */
+ if (comparison > 0)
+ return sp->root;
+
+ /* Otherwise, find the leftmost element of the right subtree. */
+ node = sp->root->right;
+ if (node)
+ while (node->left)
+ node = node->left;
+
+ return node;
+}
+