Warm-up:

ADT Task 1: Pick a neighbor. Explain to them how a heap is different than a priority queue. Have them explain to you how a queue is different than a priority queue and how to implement a queue with a plain old array.

STL Task 2: Which STL containers do you think are the most likely to be implemented with a hash map?

Class 18: Binary Search Trees - reloaded

So we now have binary search trees: left child is dominated by the node which is dominated by everything in the right child. We can insert, search, max, min, next, and previous. Here is an interactive simulation from VisuAlgo: (If the display is too compressed then just follow the link or twiddle your CSS.)

VisuAlgo Task 3: Insert the numbers 1, 2, …, 7 in the order that makes the Binary Search Tree above look the best.

BST Task 4: What is the shortest possible binary search tree holding 64 unique values? What is the tallest BST holding 64 unique values?

Traversal Task 5: Put the numbers 1 to 7 in the BST in such a way that the number of steps to start at 1 and call next 6 times is the largest possible. (Start by just trying and counting, then start thinking.) Do you believe that the number of steps for \(k\) successive next calls is \(\mathcal{O}(h + k)\)?

Removal

The next stop is deletion, which gives some funky looking code, but the story is simple (isn't that always the way…):

• With NO children just remove the node
• With ONE child just replace the removed node by its child
• With TWO children replace the node by the NEXT node. If that NEXT node is a grandchild or worse then have its (the NEXT node's) right child replace it.

See it Task 6: At highest speed insert the numbers: 50, 25, 40, 35, 45, 75, 63, 87, 69, 67, 71, 60.

Predict One Task 7: Predict what will happen when you remove 25. Slow down the pace and remove 25.

Predict None Task 8: Now do the same for 45.

Predict Two Task 9: Predict what will happen when you remove the root, 50. Then remove it. After that remove the root value again.

OK, here is the code to do that with our current BST implementation:

Code Trace Task 10: In the reality of having a recursive structure like this, why do you think I made remove return a Node*? (Hint: what should someone do when they want to remove the root node?)

Hack Task 11: Alter my code to remove all nodes, one by one, but always remove the root node.

Hack Task 12: Now remove the nodes in alternating fashion first max, then min, then max, then min, etc.

Removal Theory 13: Devise an example BST where the removal of two nodes is not symmetric. That is removing node A then node B has a different outcome than removing node B then node A.

Preview

Next up AVL trees

For now let's introduce a measure of balance: height of left tree minus height of right tree.

Play Task 14: Take the visualgo app, clear the tree and insert 50, 25, 75, 12, 37, 62, 87, 10, 20, 30, 40, 60, 70, 80, 90. What is the balance score at every node?

Play Task 15: Now remove 2 nodes that most unbalance the tree.