COMP9024 25T3
Week 9 Practical
Search Tree Algorithms
1. (AVL trees)
Extend the BST ADT from the lecture (BST. h, BST. c) by an implementation of the function
Tree deleteAVL(Tree t, Item it)
to delete an element from an AVL tree.
Deleting an element from an AVL tree requires to combine:
o a standard BST deletion method (see below for the details)
o with repairing any (potential) imbalances similar to AVL insertion.
For example, standard deletion of node 35 in the following AVL tree with root 14:
means to delete 35 from the subtree rooted in 31, which results in a tree that is imbalanced at 31:
Repairing this imbalance leads to:
Since we started at node 14, we need to check whether the last tree is imbalanced at 14. It is not, so no repair is necessary at the root node. We have obtained an AVL tree resulting from deleting 35.
Standard BST Deletion
For this exercise, the standard BST deletion you should implement as part of AVL deletion should follow version 2 for case 4 according to siide 46 (week 7) but with join Trees(ty,t2) (cf. siide Joining Two Trees) implemented by finding the maximum element in t and making it the new root.
We have created a script. that can automatically test your program. To run this test you can execute the dryrun program that corresponds to this exercise. It expects to find the file named BST. c in the current directory with your implementation of AVL deletion.
You can use dryrun as follows:
prompts 9024 dryrun AVL
2. (Red-black trees)
Implement the pseudocode for Red-Black Tree Insertion from the lecture (slides 69-73) in our Red-Black Tree ADT (RBTree. h, RBTree. c) as the function:
Tree TreeInsert (Tree t, Item it) {...}
Note: Ensure that you implement the pseudocode from the lecture. Other algorithms will not score full marks for this exercise even if they also result in the correct insertion of the new element.
We have created a script. that can automatically test your program. To run this test you can execute the dryrun program that corresponds to this exercise. it expects to find the file named RBTree. c in the current directory with your implementation of the function TreeInsert ().
You can use dryrun as follows:
prompts 9024 dryrun RBTree