Binary Search Trees 2

Question 1

Which node represents the 5th smallest element in the tree?

https://drive.google.com/file/d/1sSd5xOdoXiOdkJwH4An6lZ60izxORDSM/view?usp=sharing

A
B
C
D
E

Question 2

Which of the following is the result of splaying the highlighted node?

https://drive.google.com/file/d/1IyGdCf-nOqDd8QIBx0FYfG945EHKNdAy/view?usp=sharing

A
B
C

Question 3

What is going to happen if you forget to splay the last accessed vertex in the implementation of Find in case the key was not found in the splay tree?

The tree will work too slow on some sequences of operations

Some of the tree operations will work incorrectly after that

Answer 3

Correct! See this visualization and try to insert many elements in perfect order starting from an empty tree: insert 1, then 2, then 3, and so on. See how the tree grows unbalanced, it is just a chain! However, by now each operation took O(1) time, so it’s ok. Now think what will happen if you look for element 0 in this tree. If you use the visualization, you will see that you will have to go all the way down through the tree and then find out in the end that you didn’t find anything. The tree in the visualization then splays the lowest vertex, and the tree becomes more balanced. But let’s suppose you forgot to implement that - then the tree won’t change after the call to Find If you then try to find 0 again in the tree, you will have to go all the way down again! So, after inserting n elements in the tree in the perfect order, if you look for an element that is smaller than all the keys in the tree n times. then each of the last n operations will take O(n) time, so the tree no longer works in amortized O(logn) time!

Question 4

What will happen if you splay the node with the smallest key in a splay tree?

The root of the new tree wont have right child

The root of the new tree wont have left child

The root of the new tree wont have children

The root of the new tree will have both children

Answer 4

Correct! The node with the smallest key will become the root after splaying, and it cannot have a left child, because the key of the left child must be smaller than the key of its parent.

Question 5

What will happen if you select a node N, splay its predecessor P the node with the largest key smaller than the key of N), then splay the node N itself?

N will be the root, P will be the left child of the root, P wont have a right child

P will be the root

N will be the root, P will be the right child of the root

N will be the root, P will be the left child of the root, P wont have a left child

Answer 5

Correct! After the first splay, P will become the root. After the second splay, will become the root, and P will become its child, and it will be on the left, because its key is smaller. P won’t have a right child, because a right child of P must have key bigger than the key of P and also it must have key smaller than the key of N (because it is now in the left subtree of N) , but it can’t happen, because P is the predecessor of N ,so there are no keys between the key of P and the key of N