COMP225 : Algorithms and Data Structures
Week 12
Objectives : to learn more about balanced search trees Reference Carrano chapter 12 (Advanced Implementations of ADT table).- Given the above 2-3 tree insert the keys 44, 45, 46, 47. Show tree at each step.
- Given the above 2-3 tree delete the keys 60,70,80. Show tree at each step. (Just ensure given key is deleted and that you have a valid 2-3 tree afterwards. Can use Carrano's algorithm if you wish but not necessary).
- Write the pseudocode for an postorder traversal of a 2-3 tree.
- (*)Write a c++ function for determining the height of an AVL tree. Assume the following definition of a node :
struct node { int data; node *left; node *right; }; int height (node * AVLtree) // pre : none // post : returns the height of the tree - (*)Write a c++ function for determining the largest value in an AVL tree.
int findMax( node * AVLtree) // pre : none // post : returns the maximum value in an AVL tree or INT_MIN if none exists
- (*)Write a c++ function for determining if two red-black trees are equal.
Two red-black trees are equal if they are the same shape and contain the same data in the corresponding nodes. (Ignore colour coding).
struct node { int data; bool isRed; node *left; node *right; }; bool areEqual (node *t1, node *t2) // pre : none // post : returns true if both trees are equal and otherwise false - When are B-trees of higher order (degree) an advantage?
