Data Structures and Algorithms with Object-Oriented Design Patterns in C++

Projects

Complete the implementation of the BST class declared in Program by providing suitable definitions for the following member functions: IsMember and FindMax. You must also have a complete implementation of the base class BinaryTree. (See Project ). Write a test program and test your implementation.
Complete the implementation of the AVLTree class declared in Program by providing suitable definitions for the following member functions: Left, Right, RRRotation and RLRotation. You must also have a complete implementation of the base class BST. (See Project ). Write a test program and test your implementation.
Complete the implementation of the MWayTree class declared in Program by providing suitable definitions for the following member functions: MWayTree (constructor), MWayTree (destructor), Purge, Count, IsEmpty, IsLeaf, Degree, Key, Subtree, IsMember, FindMin, FindMax, BreadthFirstTraversal and NewIterator. Write a test program and test your implementation.
Complete the implementation of the BTree class declared in Program by providing suitable definitions for the following member functions: BTree, InsertKey, InsertSubtree, AttachKey, AttachSubtree, AttachLeftHalfOf, AttachRightHalfOf and Withdraw. You must also have a complete implementation of the base class MWayTree. (See Project ). Write a test program and test your implementation.
The binary search tree Withdraw routine shown in Program is biased in the following way: If the key to be deleted is in a non-leaf node with two non-empty subtrees, the key is swapped with the maximum key in the left subtree and then recursively deleted from the left subtree. Following a long series of insertions and deletions, the search tree will tend to have more nodes in the right subtrees and fewer nodes in the left subtrees. Devise and conduct an experiment that demonstrates this phenomenon.
Consider the implementation of AVL trees. In order to check the AVL balance condition in constant time, we record in each node the height of that node. An alternative to keeping track of the height information explicitly is to record in each node the difference in the heights of its two subtrees. In an AVL balanced tree, this difference is either -1, 0 or +1. Replace the height member variable of the AVL class defined in Program with one called diff and rewrite the various member functions accordingly.
The M-way tree implementation given in Section is an internal data structure--it is assumed that all the nodes reside in the main memory. However, the motivation for using an M-way tree is that it is an efficient way to organize an external data structure--one that is stored on disk. Design, implement and test an external M-way tree implementation.