Binary Search Trees

Question 1

What is the time for operations on a BST in the worst case?

Answer 1

Proportional to the height of the tree

Question 2

What is the operation for floor and ceiling?

Answer 2

Given key < root - go left
Given key > root - floor could be right if and only if there is a key smaller than or equal to the key in the right subtree. If not, then root.
Ceiling follows the same logic, less is exchanged with greater

Question 3

How does selection work in a BST?

Answer 3

If we seek key of rank k:
* If number of keys in left tree is larger than k, look for key in left tree
* If num keys N = k, return root
* If num keys < k, look for the key of rank k - (num of keys) - 1 in right

Question 4

How does rank work in a BST?

Answer 4

• if given key is the key at the root, return size(left)
• If given key is less than root, return rank(key, left)
• If given key is larger, return 1 + size(left) + rank(key, x.right)

Question 5

How does deleting the min/max work in BSTs?

Answer 5

Min: Go left until finding node with null left link and replace with right link
Max: Go right until node with null right and replace with left

Question 6

How do we delete a node with one child?

Answer 6

Link replacement from parent to child

Question 7

How do we delete any node with 2 children?

Answer 7

• Save link to t
• Set x to point to successor min(t.right)
• Set right link of x to deleteMin(t.right)
• Set left link to t.left.