Balancing Binary Search Trees (AVL Trees)

This set of exercises accompanies Lecture of Week 3 of the course Algorithm Design and Analysis.

Short comprehension exercises

Insert following keys into an initially empty AVL tree. Discuss the cases of balancing that appear. Keys are: 4, 23, 11, 89, 34, 2, 7 14, 75, 69, 99, 80

Delete following keys from the AVL tree built before: 34, 75

Implementation assignment

Implement the insertion into a balanced AVL tree.

Draw a table comparing the cases of using the 2 different implementations of binary search trees (simple binary search tree implementation from previous lab vs balanced AVL tree.

Compare your AVL tree with some sets or maps in different standard container libraries that are based on some kind of balanced binary search trees. (most relie on another kind of balanced BST, the Red-Black trees):

Tree height for simple BST Tree height for balanced BST Time for insertion - simple BST Time for insertion - balanced BST Time for insertion - Java TreeMap
Insert N=1000000 random keys ... ... ... ... ...
Insert N=1000000 keys in increasing order ... ... ... ... ...

Creative assignment (*)

Given 2 different binary search trees that contain both the same set of values, find a method to transform the first binary search tree into the second one by applying only rotation operations.

Implement following operations:

GenerateRandomPermutation(n): generates a random permutation of the numbers 1..n

TestClones(T1, T2): returns true if two binary trees are identical as shape and contained values

TransformTree(T1, T2) -> T1 : transforms the BST T1 into a clone of the BST T2 by using only rotation operations;

Write a program that, for a given value n, generates 2 random permutations of the numbers 1..n, inserts them into the binary search trees T1 and T2, and then transforms T1 into a clone of T2. Verify the result by calling TestClones on the transformed T1 and T2.