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:

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.