node of its left sub tree (its in-order predecessor) or the leftmost node of its right subtree (its in-order successor). Remove that node instead. In this way, deletion is reduced to the problem of removing a node with 0 or 1 children. Unlike a binary search tree, in a splay tree after deletion, we splay the parent of the removed node to the top of the tree. Alternatively: The node to be deleted is first splayed, i.e. brought to the root of the tree and then deleted. leaves the tree with two sub trees. The two sub-trees are then joined using a "join" operation. Implementation and variants Splaying, as mentioned above, is performed during a second, bottom-up pass over the access path of a node. It is possible to record the access path during the first pass for use during the second, but that requires extra space during the access operation. Another alternative is to keep a parent pointer in every node, which avoids the need for extra space during access operations but may reduce overall time efficiency because of the need to update those pointers. Another method which can be used is based on the argument that we can restructure the tree on our way down the access path instead of making a second pass. This top-down splaying routine uses three sets of nodes – left tree, right tree and middle tree. The first two contain all items of original tree known to be less than or greater than current item respectively. The middle tree consists of the sub-tree rooted at the current node. These three sets are updated down the access path while keeping the splay operations in check. Another method, semisplaying, modifies the zig-zig case to reduce the amount of restructuring done in all operations. Below there is an implementation of splay trees in C++, which uses pointers to represent each node on the tree. This implementation is based on bottom-up splaying version and uses the second method of deletion on a splay tree. Also, unlike the above definition, this C++ version does not splay the tree on finds – it only splays on insertions and deletions, and the find operation, therefore, has linear time complexity. #include <functional> #ifndef SPLAY_TREE #define SPLAY_TREE template<typename T, typename Comp = std::less<T>> class splay_tree { private: Comp comp; unsigned long p_size; struct node { node *left, *right; node *parent; T key;