Binary Search Trees Flashcards
Which number(s) are returned by the sequence of queries below?
Insert(3)
Insert(8)
Insert(5)
Insert(10)
Delete(8)
Insert(12)
NearestNeighbors(7)
a) 3
b) 5
c) 8
d) 10
e) 12
5 y 10
Which of the trees satisfies the search tree property?
https://drive.google.com/file/d/1zG0XqWoyEvO0YuyX955khfzL2p1K33JS/view?usp=sharing
a) A
b) B
c) C
B
There is actually a slight bug in the code presented for Next. What is it?
a) Does not correctly handle case where N is the largest element,
b) Does not correctly handle the case when N is the root node
c) Does not correctly handle the case when N is the smallest element
d) Does not correctly handle the case when N has no left child
Does not correctly handle case where N is the largest element.
If in the presented code N is the largest element in the tree, you will get an error when finding the RightAncestor after trying to find the grandparent of the root node. To fix this, you would want to modify RightAncestor to return null if the input is null.
Which tree results when the highlighted node is deleted?
https://drive.google.com/file/d/1JPcsldN17s_LEdsE4fSwIwdP3tMGBjfW/view?usp=sharing
A
B
C
C
What is the ordering of the times that it takes to search for the given nodes?
https://drive.google.com/file/d/1aJlJskZF8wr-tvVGjZH9yewvMS3IoUSx/view?usp=sharing
A<D<B<C
A<B<C<D
C<D<A<B
A<D<C<B
A<B<D<C
A<D<B<C
What is the height of the highlighted node?
https://drive.google.com/file/d/1JonF6WQlEMoebndPDjzHkyEs0-thw3Y6/view?usp=sharing
6
Which insertion will require the tree to be rebalanced in order to maintain the AVL property?
https://drive.google.com/file/d/19iXqc0x5bT8KaZhDrr2RXV9y9OMo4Eoi/view?usp=sharing
A
B
C
D
D
Which of the trees below can be merged with the one above?
https://drive.google.com/file/d/1GzVZc9jLxwnfmZf864YCNEaL0vEp7cbl/view?usp=sharing
A
B
C
A
Your colleague proposed a different definition of a binary search tree: it is such binary tree with keys in the nodes that for each node the key of its left child (if exists) is less than its key, and the key of its right child (if exists) is bigger than its key. Is this a good definition for a binary search tree?
No
Yes
Correct! Binary search for a key in such tree might not work: try finding the key 2 in the tree below. Your first move would be to go left from the root, because 2<3 However, the key 2 is in the right subtree of the root. The condition that the key of the left child of each node is less than the key of the parent, and the key of the right child is greater than the key of the parent is satisfied for all nodes in the tree. What’s missing is that not just the key of the left child, but the keys of the whole left subtree of each node should be less than the key of the subtree root, and similarly for the right subtree.
Suppose we enforce the AVL tree condition only for the root of the tree, but not for all the nodes. Can such tree be unbalanced?
Yes
No
Correct! Such tree could have height n/2 where n is the number of nodes: two chains of length n/2 having root as the only common node form such a tree
Can the Insert operation be implemented given only Split and Merge operations?
a) Yes. First create a new tree with single key- the key to be inserted. Then merge current tree with the new tree
b) Yes. First create a new tree with single key - the key to be inserted. Then split the current tree by this key. Then merge the left splitted part with the new tree. Then merge the result with the right splitted part
c) NO
b) Yes. First create a new tree with single key - the key to be inserted. Then split the current tree by this key. Then merge the left splitted part with the new tree. Then merge the result with the right splitted part
Can the Delete operation be implemented given only Split and Merge operations?
Yes
No
Yes
Which node represents the 5th smallest element in the tree?
https://drive.google.com/file/d/1i0RHcm0TkYbIZWrykRWpR6_CgZHqs99-/view?usp=sharing
A
B
C
D
E
Which of the following is the result of splaying the highlighted node?
https://drive.google.com/file/d/1IUjEwnFB1URwFuMLJCELC1J5hEKzVOwF/view?usp=sharing
A
B
C
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?
a) The tree will work too slow on some sequences of operations
b) Some of the tree operations will work incorrectly after that.
Correct! See this visualization and try to insert many elements in perfect order starting from an empty tree: insert 1, them 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!
