Ordered Map and BST

Question 1

What is an Ordered Map

Answer 1

Similar to a map, but with the keys being ordered.

Question 2

2 Implementations of Ordered Map

Answer 2

1. Array -> very inefficient
2. Binary Search Tree

Question 3

What is the BST Property

Answer 3

Everything to the left of a vertex has a smaller value. Everything to the right of a vertex has a greater or equal value to the vertex. Unlike min / max heap.

Question 4

3 Implementations of BST

Answer 4

1. Sequential Array (inefficient)
2. Parent Array (inefficient)
3. Nodes (best)

Question 5

Time Complexity of Search

Answer 5

O(h) -> Not the same as O(logn) because BST is unlikely to be a perfect tree. If current node value too large, search from left child, else search from right child.

Question 6

Time Complexity of Insertion

Answer 6

O(h) -> Same logic as in search, insert the node at the right place and recursively assign the node as the appropriate child.

Question 7

Time Complexity of GetMax

Answer 7

O(h) -> Recursively visit the right child until you reach a node with no right child, then return the node’s value.

Question 8

Time Complexity of GetMin

Answer 8

O(h) -> Recursively visit the left child until you reach a node with no left child, then return that node’s value.

Question 9

Time Complexity of Successor

Answer 9

O(h) -> If the node with value x has a right child, the minimum of the right subtree is the successor. If it doesn’t, keep going up until it finds a parent a that is the left child of parent b. Return parent b’s value.

Question 10

Time Complexity of Predecessor

Answer 10

O(h) -> If the node with value x has a left child, the maximum of the left subtree is the predecessor. If it doesn’t, keep going up until it finds a parent a that is the right child of parent b. Return parent b’s value.

Question 11

Time Complexity of ListSorted

Answer 11

O(3n) = O(n) -> Do in-order traversal: If the current node is null, return. Else visit the left child. Process the current node value. Visit the right child. 3n because you visit each node 3 times.

Question 12

Time Complexity of Deletion

Answer 12

Overall O(h)

1. Vertex v has no children -> O(1): Just remove v
2. Vertex v has 1 child -> O(1): Connect child to parent.
3. Vertex v has 2 children -> O(h): Find the successor x of v. Replace v.key with x.key. Recursively delete x in v.right.

Question 13

Time Complexity of Rank

Answer 13

O(h) -> Check if value is smaller, larger, equal to value of current node. If smaller, recursively return rank(curr.left). If equal, return curr.left.size + 1. If larger, return curr.left.size + 1 + rank(curr.right).

Question 14

Time Complexity of Select -> given a rank, return the value of the node with that rank

Answer 14

O(h) -> Check if rank needed is smaller than rank of current node (curr.left.size + 1), equal or larger. If equal, return the current node’s value. If smaller, recursively call with curr.left and rank k. If larger, recursively call with curr.right and rank (k - rank(curr))What

Question 15

What is the worst case for a BST

Answer 15

When height = N. To prevent this, we use AVL trees.