balanced binary search trees one method of deleting node from splay tree is accomplished by deleting just as you would in binary search tree if the node to delete has zero or one child it is trivial to delete the node if the node to delete has two childrenthen the leftmost value in its right subtree can replace the value in the node to delete and the leftmost value can be deleted from the right subtree the parent of the deleted node is splayed to the top of the tree another method of deletion requires splaying the deleted node to the root of the tree first then the rightmost value of the left subtree is splayed to the root after splaying the left subtreeits root node' right subtree is empty and the original right subtree can be added to it the original left subtree becomes the root of the newly constructed splay tree recursive splaying implementing splaying recursively follows the recursive insert operation on binary search trees the splaying is combined with this recursive insert function as the recursive insert follows the path down the tree it builds rotate string of "rand "lif the new item is inserted to the right of the current root nodethen left rotate will be required to splay the newly inserted node up the tree and an "lis added to the rotate string otherwisea right rotate will be required and an "ris added to the rotate string as the recursive insert function returnsthe path to the newly inserted node is retraced by the returning function the last two characters in the rotate string dictate what double rotation is required dictionary or hash table takes care of mapping "rr""rl""lr"and "llto the appropriate rotate functions the hash table lookup is used to call the appropriate rotation and the rotate string is truncated (or re-initialized to the empty string depending on when "rand "lare added to the rotate stringwhen the recursive insert is finishedany required single rotation will be recorded in the rotate string and can be performed it should be noted that implementing splaying using rotate string and hash table like this requires about one half the conditional statements to determine the required rotations as compared to the iterative algorithm described above when inserting new node the path must be determined by comparing the value to insert to each node on the path to its location in the tree in the iterative description abovethe values on the path are again compared during splaying in this recursive description the new item is only compared to each item on the path once this has an impact on performance as shown later in the looking up value using this recursive implementation works similarly to insert either splaying the found value or its parent if it is not found to the root of the tree deleting value again can be done recursively by first looking up the value to delete resulting in it being splayed to the root of the tree and then performing the method of root removal described in the previous section this copy belongs to 'acha