HEAP finishing

We didn't quite make it through the heap lectures, so let's head back to class15 now.

Binary (search) Trees

OK, we're moving on to the final chapter of this course, the more subtle data structures. The star of our show will be balanced binary trees, but we might do some cool obscure ones and possibly some graph traversal.

Binary Trees

Imagine a linked list, it's just a node which connects to another node. A binary tree is just a node which connects to a left node and connects to a right node. (Both or either could be null pointers.)

Some basics

So this is a recursive structure. At any node in the tree you have the root of another tree. (Linked list was recursive too.)

Here is a first simple implementation which takes advantage of this to traverse the tree:

At this point this is like a linked list squared. You could almost imagine the index of a random point in this structure as a sequence of lefts and rights.

Wild Task 1: Add a left child to the left child with value 17. Add a right child to that left left child with value 25. Predict the order that things are printed.

Crazy Insert

So this isn't normal, but I'm going to write a Node insert which just sticks the number wherever. Then we're going to learn some lessons from that:

Root Second Task 2: Change the print function to display the root value last (the 10).

Find Task 3: NOW, take that lesson and write an is_in(int value) function which determines if a number has been inserted into this binary tree. (To test yourself change the input value from i to rand()%50.)

Counter Task 4: Can you adjust your code to count the number of comparisons you make? What complexity does your search algorithm need in the worst case?

Binary Search Trees

Now we add one extra property to a binary tree to make it much more useful. The binary search property is this: every value in the left subtree must be no larger than the root value and every value in the right subtree must be no smaller than the root value.

Here is normal_insert(int value) (by the way I'm ignoring duplicates):

Structure Task 5: Sketch on paper what that binary search tree looks like now.

Random Task 6: Change the insert to rand() % 50. Change the print statement to help you see left and right subtrees. How does your random binary search tree look different than the last one?

Search Task 7: Write the is_in(int value) code now that we know the left tree only has smaller elements and the right tree only has larger elements.

Complexity Task 8: What is the worst case insertion order for the complexity of is_in? What is the best case? What happens in a average case?

Do you remember how we wanted to binary search on linked lists, but it wouldn't work because we didn't have a pointer to the middle of a range? THAT is what binary search trees are all about!

This is the linked list version of binary search!

Min/Max Task 9: Write two methods min() and max().

Next/Prev

Now, from a particular node I want to go to the NEXT node (in logical order).

OK so this doesn't just spill out from the definition of left is small and right is big. In fact, at this point I'm going to also store a parent pointer (and fix the memory leaks we've been making).

Here is the big idea:

• IF your node has a right child then the NEXT is the MIN of that tree.
• IF you do not have a right child then walk up the tree until you find a node which is a left child, the parent of that node is the NEXT. (Your node is the largest in that node's left subtree.)

Take a look at this Binary Search Tree, what is the NEXT of 23?

Notice how you walk up the tree until you made a right?

PREV Task 10: OK, write a function that finds the previous node.

Theory Task 11: Prove that no matter what node we start at in a height-h binary search tree, k successive calls to NEXT takes \(\mathcal{O}(k+h)\) time.

Deleting

So how do we delete a node from a binary search tree and preserve the binary search tree property?

• If NO CHILDREN then kill the node.
• If ONE CHILD then replace the node by it's child.
• If BOTH CHILDREN EXIST then replace node by NEXT node (min of right subtree), but also replace NEXT node by its right child (even if right child null).

There are simpler solutions, but this one delete the actual spot in memory of the node being deleted, so I accept the extra complexity.

We have to be careful with the head. I'll give you code next time.