recitation 10/1/97 o Binary trees, Binary search trees o More DP and memoizing if needed TREES ------ Let's go through some examples of Binary Search Trees, and various things we might want to do with trees. Basic concept of BSTs: for each node N, everything in left subtree has value <= N's value, and everything in right subtree has value >= N's value. In lecture we talked about one way of creating a BST: to insert a new value X, compare with value Y of the current node. If X < Y then insert at left (if we don't have a left child then put it right there, else insert recursively). If X >= Y then insert at right (if we don't have a right child then put it right there, else insert recursively). E.g., insert letters V M A H Q R P E into a binary search tree. We went through some code for this in lecture. Could do it again if students want to: [this is the same as in lecture... class BST { private: char *value; BST *left; BST *right; public: BST(char *str); // copies str into value of new node. ~BST(); // frees up value void InOrder(); // InOrder traversal. void Insert(char *str); // insert into the BST. }; void BST::Insert(char *word) { if (strcmp(word, value) < 0) { // insert to the left if < if (left == NULL) left = new BST(word); else left->Insert(word); } else { // insert to the right if > or = if (right == NULL) right = new BST(word); else right->Insert(word); } } ....] Any questions about inorder versus pre-order versus post-order traversals? Go through the results of each of these on the tree we just constructed. [... here is code from the lecture.... void BST::InOrder() { if (left) left->InOrder(); cout << value << endl; if (right) right->InOrder(); } ] How much time does it take to do a traversal on a tree of n nodes? Answer: O(n) At the very end of lecture we asked the question: How can we use BST's to do sorting? Answer: First insert everything, then do the inorder printing. How much time does this take? It depends on how lucky we are. What is the worst case? If everything is already sorted (or in reverse order). Then time is O(n^2) to do all the insertions. What is the best case? If the tree we create is balanced, then its depth is only O(log n). So, the total time is only O(n log n) Say you want to maintain a changing database using a binary search tree. We've seen how to insert. How about deletions? This is a bit trickier. Let's continue with the above example. 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. Q: How do you find next highest element? A: Go to the right child, then take left child pointers as far as you can. Convince class that this really finds the next highest element. Here is some code for deletions. This might be too long/complicated to actually do in detail. This code demonstrates good style 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 the code: // We're writing this as if it is a friend function. // It returns a pointer to the new tree. BST *remove(BST *root, char *str) // returns new tree. { // EASY CASE FIRST: we're not there yet if (root == NULL) return NULL; // str wasn't in the tree int result = strcmp(str, root->value); if (result < 0) { root->left = remove(root->left, str); return root; } else if (result > 0) { root->right = remove(root->right, str); return root; } // Now, we're at the correct spot in the tree. // EASY CASE FIRST: removing a leaf if (root->left == NULL && root->right == NULL) { delete root; return NULL; } // EASY CASE: has only one non-NULL child BST *onlychild = NULL; if (root->left == NULL) onlychild = root->right; if (root->right == NULL) onlychild = root->left; if (onlychild) { delete root; return onlychild; } // harder case (but not that hard now that it's the only one left): // have two children. BST *nextp; // this will soon point to the next highest element for(nextp = root->right; nextp->left != NULL; nextp = nextp->left); delete root->value; // assuming we copied it in constructor root->value = strdup(nextp->value); root->right = remove(root->right, nextp->value); //a little slow, but OK return root; } ================================================================== DP and Memoizing and Assignment 3: Hint on assignment 3: read the first paragraph in the Specifications section several times. Try it by hand on the example given in the handout. - See if students have questions on DP and memoizing. Students can do it either way on the assignment. - if you didn't get through Monday's notes on DP and memoizing, you can continue with those examples if students want more. Here is another example, just in case you prefer this one. Say you want to multiply a bunch of matrices. If you multiply an LxM matrix with an MxN matrix, you end up with an LxN matrix. Also, if you do the multiplication the usual way, the time taken is O(L*M*N). Say you want to multiply three matrices together. The first one is L0 x L1, the second is L1 x L2, and the third is L2 x L3 The total amount of time this takes is going to depend on what order you do it: either O(L0*L1*L2 + L0*L2*L3) or O(L1*L2*L3 + L0*L1*L3) Say you have seven matrices and you want to figure out the best order to multiply them in. You can do this using Dynamic programming (or Memoizing). The idea is you figure out the best way to multiply matrices i,i+1,...,j using the previously-computed solutions for (i,k) and (k+1,j) for each k between i and j.