The goal of this assignment is to reinforce the heap and B-tree data structure in C++.
1. Do programing project #9 on page 538 of textbook. You need to have a test program to test your code.
Binary search trees have their best perfor mance when they are balanced, which means that at each node, n, the size of the left subtree of n is within one of the size of the right subtree of n. Write a function that takes a sorted linked list of entries and produces a balanced binary search tree. If useful, you may add extra parameters to the procedure, such as the total number of entries in the list. Hint: First build the left subtree of the root, then the right subtree of the root, then put the pieces together with the join function from Self- Test Exercise 26 on page 531. Think recursively!
Test exercise 26:
26. Write a bag friend function called join with this prototype:
template < class Item>
void join(
bag< Item>& top,
bag< Item>& left,
bag< Item>& right
);
The precondition of the function requires that top has just one item, that everything in left is less than or equal to the item in top , and that every- thing in right is greater than the item in top . The postcondition requires that top now contains everything from left and right , and that left and right are now both empty. Your function should take constant time.
2. Download the project Priority_Queue_Heap.
Finish the implementation of the class priority_queue_heap. The only member data will be a heap.
Modify the main.cpp to create two new functions to demonstrate two implementations of priority queues.
3. B-Tree Operations
You can carry this out in an electronic document or on paper.
In each of the following questions, you will redraw the B-tree above after the indicated operation has been carried out. The value of MINIMUM for the tree above is 1.
1) Insert 9 into the original tree above.
2) Insert 23 into the original tree above.
3) Insert 24 into the tree resulting from the previous question.
4) Delete 4 from the original tree.
5) Delete 20 from the original tree.