Data Structures and Algorithms with Object-Oriented Design Patterns in Java

Projects

Complete the implementation of the BinarySearchTree class introduced in Program by providing suitable definitions for the following methods: 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 introduced in Program by providing suitable definitions for the following methods: getLeft, getRight, doRRRotation, and doRLRotation. You must also have a complete implementation of the base class BinarySearchTree. (See Project ). Write a test program and test your implementation.
Complete the implementation of the MWayTree class introduced in Program by providing suitable definitions for the following methods: purge, getCount, isEmpty, isLeaf, getDegree, getKey, getSubtree, isMember, findMin, findMax, breadthFirstTraversal, and getEnumeration. Write a test program and test your implementation.
Complete the implementation of the BTree class introduced in Program by providing suitable definitions for the following methods: insertKey, insertSubtree, 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 method 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 field of the AVL class defined in Program with one called diff and rewrite the various methods 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.