Let's say a tree is defined by:
struct node {
char value; // entry is a character
node *left, *right;
};
Now consider a simple recursive tree routine: freeing up a tree:
void
free_tree(node *t) {
if (t == NULL) return;
free_tree(t->left);
free_tree(t->right);
delete t;
}
Everyone understand Binary Search Trees? Try inserting some letters V M A H Q R P E into a binary search tree. What does it look like?
Can anyone thing of a way to use BSTs to do sorting? (First insert everything, then do the inorder printing.)
Say you want to maintain a changing database using a binary search tree. We've seen how to insert: in lecture there was a recursive procedure where if the current node is null, you insert there and return the pointer, else you go down the left or right side as appropriate.
What about deletions? This case is harder than insertion.
Say you want to delete "M". First you find it, that's easy. If has no children, deleting is easy - just remove. If only has left or right child, deleting is not so hard either. (Why?) Otherwise, you will have to replace it with something. What do you want to use? (2 reasonable options). Suppose you use the next highest element. But how do you find it?
Go to the right child, then take left child pointers as far as you can. Convince yourself that this really finds the next highest element.
Here is some code for deletions. This code demonstrates a good style, that you should try to emulate, in the following sense: One good way to attack a difficult task is to first handle the easy case. Often, as you keep handling the next easiest case, the harder cases get easier by themselves.
Here is code:
node* // returns new tree
remove(node *root, char c) {
// easy case: we're not there yet
if(root == NULL) return NULL; // c wasn't in the tree
if(c < root->value) {
root->left = remove(root->left, c);
return root;
}
if(c > root->value) {
root->right = remove(root->right, c);
return root;
}
// Now, we are at the correct spot in the tree
// easy case: removing a leaf
if(root->left == NULL && root->right == NULL) {
delete root;
return NULL;
}
// easy case: left is NULL or right is NULL
if(root->left == NULL || root->right == NULL) {
node *temp;
if(root->left == NULL) temp = root->right;
else temp = root->left;
delete root;
return temp;
}
// harder case (but not that hard now that it's the only one left):
// neither is NULL
node *nextp; // this will soon point to the next highest element
// Why is "nextp->left" safe to do??
for(nextp = root->right; nextp->left != NULL; nextp = nextp->left);
root->value = nextp->value;
root->right = remove(root->right, nextp->value); // a little slow, but OK
return root;
}