Search Trees
Easy Problems
- Modify the operation delete in a binary search tree so that the maximum node in the right subtree is used as the replacement node.
- What is the maximum height of a binary search tree on n nodes. What is the minimum height of a binary search tree on n nodes.
- What is the maximum height of a binary search tree if every internal node at level l have both their children before any node at level l+1 has some children.
Difficult Problems
- Many problems do not require the full repertoire of dictionary operations but only a subset. Consdier the subset of operations: insert(), and DeleteMin(). In this case, it is not required to have a binary search tree and we can think of ways to support these two oeprations efficiently. Here is a possible way.
- Use the binary tree described in the third question above. Use the invariant that the value at any node is at most the value of both of its children. In this data structure, where is the minimum element?
- Suppose you add one more element to the existing tree above. Where should you first place it? How do you repair the invaraint if required? What is the runtime of this operation?
- Extend your solution above to also the DeleteMin() operation. What is the runtime of your operation?
- How can you use your above data structure to sort n data items. What is the runtime of your solution?