Problem
Consider a type of Splay tree that stops splaying as soon as a zig situation arises (without executing it). Build the Splay Tree resulting from the insertions of the keys below, in this order, and answer the following questions for 3 points each. For internal nodes and external, consider only nodes that have a non-null key; in other words, take the resulting tree without the sentinel nodes. Also take the height of the tree without the sentinel nodes. Keys for the Splay Tree: 3,13,14,16,4,0,5,9
Task
i. What is the height of the splay tree?
ii. What is the key in the root node?
iii. How many external nodes does this splay tree have?
iv. What is the sum of the keys in the last 2 nodes of the left branch?
v. What is the sum of the keys in the last 2 nodes of the right branch?