Homework No. 3

[ Search Trees ]

The number of your particular task is the value of the expression faculty_number%7.
Write a complete program with at least one example in main function.

(0) [P-9.3] Extend class BinarySearchTree, shown in Code Fragmant 9.3 through 9.5 to support the functions of the orderd dictionary ADT, listed in Section 8.3.1.

(1) [P-9.5] Implement a class RestructableNodeBinaryTree that supports the functions of the binary tree ADT, plus a function restructure() for performing a rotation operation. This class is a component of the implementation of an AVL tree given in Section 9.2.2.

(2) [P-9-7] Implement the functions of the ordered dictionary ADT using AVL tree.

(3) [P-9.9] Write a C++ class that implements all the functions of an ordered dictionary given in Chapter 8 using (2,4) tree.

(4)
[P-9.10a] Write a C++ class that can take any red-black tree and convert it into its corresponding (2,4) tree.

(5) [P-9.10b] Write a C++ class that can take any (2,4) tree and convert it into its corresponding red-black tree.

(6) [P-9-11]
Write a C++ class that implements all the functions of a dictionary given in Chapter 8 by means of red-black tree.