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.