# CPSC250A Assignment 1011 - AVL Tree

## Due Monday October 31

The big O of operations on a binary search tree are linear because the
tree can degenerate into a list. It is possible to maintain a balanced
binary search tree by performing rotations whenever elements are added
or removed, as in an AVL tree.

### Details

The file avl_test.cc contains a program that allows the user
to test adding ints to an AVL tree. For this assignment, write the
`AVLTree`

class. The class should be a template class that
implements an AVL tree (either doubly or singly linked).
The class should define four functions:

- A zero parameter constructor that initializes an empty AVL tree.
- A desctructor that deletes all nodes of an AVL tree.
- The
`Add`

function, that adds the specified object to the AVL tree. This
function can assume the < operator is overloaded.
A function that overloads the << operator and prints an AVL tree
to the specified `ostream`

. When printing the tree use the following
recursive structure:

nodeData if node is a leaf
(nodeData leftChild rightChild) if node is not a leaf

Be sure to test your code on multiple examples and on the cs server.

### Submission

Tar your code in a file that contains your name and submit it on course
Inquire site.