Tutorial
COMP20007 Design of Algorithms
Week 9 Workshop
1. Rotations In the following binary trees, rotate the ¡®X¡¯ node to the right (that is, rotate it and its left child). Do these rotations make the tree more balanced, or less balanced?
(a) (b) (c)
XXX LYLU
AVUL
2. Balance factor A node¡¯s ¡®balance factor¡¯ is defined as the height of its right subtree minus the height of its left subtree. Calculate the balance factor of each node in the following binary search tree.
3. AVL Tree Insertion
4. 2-3 Tree Insertion
H DL BFJN
CIMO
Insert the following letters into an initially-empty AVL Tree. AVLTREXMP
Insert the following letters into an initially-empty 2-3 Tree. ALGORITHM
1
Computer Lab
Feel free to use this time to complete previous lab exercises.
1. Binary Search Tree (Optional) If you have already completed the sorting exercises, try implementing a binary search tree. You may find your linked list implementation helpful. Insert the numbers
5, 4, 3, 1, 2, 6, 7, 8, 9, 10
perform a traversal to print out the level of each value in the tree and compare this with the value you find running through the algorithm manually. Give your tree a parent pointer.
2. 2-3-4 Tree (Optional) After completing your binary search tree implementation try modifying it into a 2-3-4 tree. In your data structure include a parent pointer, the number of nodes being used and during insertion promote the median value of any node containing 3 values while traversing to the root so you always have room for the new value in its parent nodes and can perform O(1) promotion. Again, insert the numbers
5, 4, 3, 1, 2, 6, 7, 8, 9, 10
and perform a traversal to print out the level of each value in the tree and compare this with running manually.
2