[Solved] COEN79-Homework 5

2. For the bag class defined in Appendix 1, please complete the following function:

1. template < class Item >
2. void bag<Item>::insert(const Item& entry)
3. // Postcondition: A new copy of entry has been inserted into the bag.
4. // Header file used: bintree.h

3. Write a function to perform left-right rotation on the following AVL tree. The figure shows the steps. (Note: Please implement the function in two steps: (1) left rotation, (2) right rotation.)

parent

1. template < class Item >
2. binary_tree_node <Item>* left_right_rotation (binary_tree_node <Item>*& parent) {
3. binary_tree_node <Item>* temp;

4. Add the following numbers to an AVL tree. Please draw the final tree. 2, 4, 6, 8, 10, 12, 20, 18, 16, 14

5. The following functions are available:

Also assume the following functions are available:

• binary_tree_node<Item>* left_rotation (binary_tree_node<Item>*& parent)
• binary_tree_node<Item>* right_rotation (binary_tree_node<Item>*& parent)
• binary_tree_node<Item>* left_right_rotation (binary_tree_node<Item>*& parent)
• binary_tree_node<Item>* right_left_rotation (binary_tree_node<Item>*& parent)

Complete the following function, which balances a tree rooted at temp.

1. template < class Item >
2. binary_tree_node<Item>* balance(binary_tree_node <Item>*& temp)

6. Please implement the following function (recursively).

1. template < class Item >
2. void flip(binary_tree_node < Item > * root_ptr)
3. // Precondition: root_ptr is the root pointer of a non-empty binary tree. // Postcondition: The tree is now the mirror image of its original value.

Example:

// 1 1

// / /

// 2 3 3 2

// / /

// 4 5 5 4

1. template < class Item >
2. void flip (binary_tree_node <Item>* root_ptr)

Appendix 1: Bag class with binary search tree.