Lecture 24 - November 19, 2007

Today we talked about binary search trees.

We learned that it helps to have two nodePointers walking through the tree, one behind the other, when trying to delete a node.

We talked about how to delete a node

when it is a leaf

when it is an only child

when it is one of two children

We modified the Binary Search Tree programming assignment so that it had the following procedures

insert

delete

search

InorderTraverse

PreorderTraverse

PostOrderTraverse

The due date was extended until next Sunday night at 11:59 pm.

We then discussed building a heap and performing a heap sort.

A heap represents a binary tree stored in an array (NOTE: NOT a binary SEARCH tree)

There are two types of heaps: a min-heap and a max-heap

In both types of heaps, the children of a node n are stored in positions 2n and 2n+1

In a min-heap, the value stored in node n is less than the value stored in either of n's children.

In a max-heap, the value stored in node n is greater than the value stored in either of n's children.

In the example in class, we put the values into the array, one at a time, trying to keep the heap a max-heap.

Then we saw how to sort the array.

We could have filled the array first and then built the max-heap.

We always have to build the heap before we can sort.

HAVE A GREAT THANKSGIVING ! Drive safely.