Balanced Binary Tree Solution



AVL Trees

The standard template library is not to be used in this assignment or any other assignment unless expressly stated.

AVL Trees

Implement an AVLTree class that stores an Integer as a data type. Including the followlOg functions:

• Constructor Destructor Insert

• Print (indented print function like the one we did In class, but witn each node’s height) PreOrderTraversal

• Node’ GetRootO (return root) 1/ needed for Unit Testing

plus all other functions needed to properly trnplernent an AVL balanced BST.

Also implement a Node class appropriate with this assignment. 1 he supplied Template for Node.h ilinciudes “Observer.h’ and defines a member variable of type Observer. Your Node.h MUST do the same. This is needed for Unit Testing of your AVL Tree. In addition to whatever you feel needed, you MUST have the following three public data members name eXACTLY as follows:

• int value;

Node’ len;

• Node’ right;

These are needed to be named this way so that the Unit Testing will work.


The supplied MalO.cpp should properly compile and run when added to your files. You mus.t not modify Main.cpp to get it to compile and run. When mainO runs it will create several AVLTrees and add data to each. After adding data, the tree will be traversed (with PreOrderTraversaIO). When the final tree is traversed, it wOl also print that tree.

• .The output should look nke this:

14, 4, 3, 2, 9, 7, re, 21, 15, 18, 28, 26, 39,

14 (3)

4 (2)

3 (1)

2 (e) [leaf]


9 (1)

7 (e) [leaf]

re (e) [leaf]

21 (2)

15 (1)


18 (e) [leaf]

28 (1)

26 (e) [leaf]

30 (e) [leaf]