CSCA48 Week 11: Worksheet There is another type of search tree (i.e. binary search tree), that is called a splay tree. The idea is to keep the more frequently accessed node close to the root. Therefore, the rule to perform move-to-root (splay) operation after every splay tree operation is a) Insert(k): insert k in its right place according to the BST rules and splay the node containing k to the root. b) Search(k): search for key k, if k was found at position p, splay p. If not found, splay the leaf at which the searching was ended unsuccessfully Delete(K): when deleting a key k, splay the position of k's parent unless it is the root of the tree In this case normal search tree deletion process is followed c) Here is how splaying works: 1- 2- 3- 4- 5- 6- 7- If p is the root, no splaying is required If p is the left child of the root, right rotate about the root. If p is the right child of the root, left rotate about the root. If p is left-left grandchild, right rotate about its grandparent, right rotate about its parent. If p is right-right grandchild, left rotate about its grandparent, left rotate about its parent. If p is right-left grandchild, left rotate about its parent, right rotate about its grandparent. If p is left-right grandchild, right rotate about its parent, left rotate about its grandparent. You keep splaying until p gets to the root. Hint 1 Rotation is performed as was explained in the lecture for AVL trees. 2- Splay trees do not preserve logarithmic upper bound on the height of the tree. (e.g. the height is not less than or equal to log 2) Every time that you splay, make sure that the resulted tree is a binary search tree 3- Question 1: Insert the following numbers into a splay tree as they are entered from left to right and draw the final tree in the worksheet. 5,15,10, 20,1, 35, 8, 28,4 Question 2: Following question 1, perform search(28) and draw the final tree in the worksheet. Question 3: Following question 2, perform search(11) and draw the final tree in the worksheet. Question 4: Following question 3, perform delete(10) and draw the final tree in the worksheet