diff options
Diffstat (limited to '03-02.md')
| -rw-r--r-- | 03-02.md | 215 |
1 files changed, 215 insertions, 0 deletions
@@ -514,3 +514,218 @@ void bag<Item>::insert(const Item& entry){ - For example consider insertion of keys 12, 10, 20, 9, 11, 10, 12, 12 in an empty Binary Search Tree  + +## The erase_one member function + +- The `erase_one` member function: Remoes a specified item from a binary search tree + - Prototype: `bool erase_one(const Item& target);` + +- We implement the `erase_one` function with two auxiliary functions to reduce the complexity of implementation + +``` +template <class Item> +bool bag<Item>::erase_one(const Item& target){ + return bst_remove(root_ptr, target); +} + +template <class Item> +bool bst_remove(binary_tree_node<Item>*& root_ptr, const Item& target); + +template <class Item> +void bst_remove_max(binary_tree_node<Item>*& root_ptr, Item& removed); +``` + +### bst_remove + +``` +template <class Item> +bool bst_remove(binary_tree_node<Item>*& root_ptr, const Item& target); + +//Precondition: root_ptr is a root pointer of a binary search tree (or may be NULL for the empty tree +//Postcondition: If target was in the tree, then one copy of target has been removed, root_ptr now points to the root of the new (smaller) binary search tree, and the function returns true. Otherwise, if target was not in the tree, then the tree is unchanged, and the function returns false + +template <class Item> +bool bst_remove(binary_tree_node<Item>*& root_ptr, const Item& target){ + binary_tree_node<Item> *oldroot_ptr; + + if(root_ptr == NULL) return false; + + if(target < root_ptr->data()) return bst_remove(root_ptr->left(), target); //target not yet found + if(target > root_ptr->data()) return bst_remove(root_ptr->right(), target); //target not yet found + + if(root_ptr->left() == NULL){ + ... + return true; + } + + bst_remove_max(root_ptr->left(), root_ptr->data()); + + return true; +} +``` + +- Employs a recursive implementation to remove the target +- Handles these cases: + 1. Empty tree: return + 2. The target < root entry: make a recursive call to delete the target from the left subtree + 3. The target > root entry: make a recursive call to delete the target from the right subtree + 4. The target = root entry + - Case a) The root node has no left child + - Case b) The root node does have a left child + +**The root node has no left child**: + +- We can delete the root entry and make the right child the new root node + +``` +oldroot_ptr = root_ptr; +root_ptr = root_ptr->right(); +delete oldroot_ptr; +``` + +- This scheme also works properly if there is no right child + +**The root node does have a left child**: + +- If there is no right child, then the left child can become the new root + - What if it has a right child? We need a better solution... + +- We need to find the largest entry in the left subtree and remove it + +- We want to design a more general solution + - To find some entry in the non-empty left subtree, and move this entry up to the root + - This case works even when the node to be deleted has a right child +- Questino: How to find this entry? + +### bst_remove_max + +``` +template <class Item> +void bst_remove_max(binary_tree_node<Item>*& root_ptr, Item& removed); + +//Precondition: root_ptr is a root pointer of a non-empty binary search tree +//Postcondition: The largest item in the binary search tree has been removed, and root_ptr now points to the root of the new (smaller) binary search tree. The reference parameter, removed, has been set to a copy of the removed item +``` + +- Implementing the `bst_remove_max` function: Cases + 1. No right child: The largest item is at the root, so you can set `removed` equal to the data from the root, move the root pointer down to the left, and delete the root node + 2. There is a right child: There are larger items in the right subtree. In this case, make a recursive call to delete the largest item from the right subtree + + + +## The erase member function + +- The `erase` member function: Removes all the occurrences of an item from a binary search tree + - Prototype: `bool erase(const Item& target)` + +``` +template <class Item> +bool bag<Item>::erase(const Item& target){ + return bst_remove_all(root_ptr, target); +} + +template <class Item> +bag<Item>::size_type bst_remove_all(binary_tree_node<Item>*& root_ptr, const Item& target); + +template <class Item> +void bst_remove_max(binary_tree_node<Item>*& root_ptr, Item& removed); +``` + +### bst_remove_all + +``` +template <class Item> +typename bag<Item>::size_type bst_remove_all(binary_tree_node<Item>*& root_ptr, const Item& target){ + binary_tree_node<Item> *oldroot_ptr; + + if(root_ptr == NULL) return 0; + + if(target < root_ptr->data()) return bst_remove_all(root_ptr->left(), target); + if(target > root_ptr->data()) return bst_remove_all(root_ptr->right(), target); + + if(root_ptr->left() == NULL){ + ... + return 1; + } + + bst_remove_max(root_ptr->left(), root_ptr->data()); + + return 1 + bst_remove_all(root_ptr, target); +} +``` + + + +``` +if(root_ptr->left() == NULL){ + //Target was found and there is no left subtree, so we can remove this node, amking the right child be the new root + oldroot_ptr = root_ptr; + root_ptr = root_ptr->right(); + delete oldroot_ptr; + return 1; +} +``` + + + + + +## The += member function + +``` +template <class Item> +void bag<Item>::operator +=(const bag<Item>& addend){ + if(root_ptr = addend.root_ptr){ //b += b + bag<Item> copy = addend; + insert_all(copy.root_ptr); + } + + else insert_all(addend.root_ptr); //b += c +``` + +- Benefits from an auxiliary function `insert_all` +- `insert_all` is actually another bag member function +- The `insert_all` member function: + +``` +template <class Item> +void bag<Item>::insert_all(binary_tree_node<Item>* addroot_ptr){ + //Precondition: addroot_ptr is the root pointer of a binary search tree that is separate from the binary search tree of the bag that activated this method + //Postcondition: All the items from the addN's binary search tree have been added to the binary search tree of the bag that activated this method + + if(addroot_ptr != NULL){ //Explicity uses the pre-order traversal of the tree + insert(addroot_ptr->data()); + insert_all(addroot_ptr->left()); + insert_all(addroot_ptr->right()); + } +} +``` + +### insert_all + +- We could also use the post-order traversal +- Avoid in-order because: + - The nodes of the addend tree will be processed in order from smallest to largest + - These nodes will be inserted into the other bag from smallest to largest + - The resulting tree ends up with a single long, narrow path, with only right children + - Searching and other algorithms are inefficient when the trees lose their branching structure + +## Summary + +- Trees are a nonlinear structure +- Applications such as: + - Organizing information (such as taxonomy trees) + - Implementing an efficient version of the bag class (using binary search trees) +- Trees may be implemented with: + - Fixed-size arrays: Appropriate for complete binary trees + - Dynamic data structures +- A tree traversal consists of processing a tree by applying some action to each node + - Using parameters that are functions, we can write extremely flexible tree traversals +- Binary search trees are one common application of trees + - Permit us to store a bag of ordered items in a manner where adding, deleting, and searching for entries is potentially much faster with a linear structure +- Operations on trees are good candidates for recursive thinking + - Because many tree operations include a step to process one or more sub-trees, and this step is "a smaller version of the same problem" + +--- + +[03/09 ->](03-09.md) |