Complete the implementation of the BinarySearchTree class
introduced in Program
by providing suitable definitions for the following operations:
IsMember and Max.
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 operations:
RRRotation, and RLRotation.
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 operations:
Purge,
Count, IsEmpty, IsLeaf, Degree,
Key, GetSubtree,
IsMember, Min, Max,
BreadthFirstTraversal, and GetEnumerator.
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.