Data Structures and Algorithms
with ObjectOriented Design Patterns in C++

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 nonleaf node with
two nonempty 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 Mway tree implementation given in Section
is an internal data structureit is assumed that all the nodes reside in the main memory.
However, the motivation for using an Mway tree is that
it is an efficient way to organize an external
data structureone that is stored on disk.
Design, implement and test an external Mway tree implementation.
Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.