CPSC 220 Assignment 3
AVL Tree
Due Before Class on Wednesday, October 7th

In this assignment you will explore how using a self balancing tree to organize objects interacting in a simple 2D game affects performance as measured by the number of frames rendered per second.


You should begin by modifying your game from assignment 2 by adding a third enum field for collision detection using an AVL Trees. When the game is set to use this collision detection method it should function very similar to the binary search tree collision from the last lab. The only exception is that objects should be added to an AVL tree object of a class that you create. The AVL tree can extend the binary search tree or be a different class. Note that it is possible that two objects in the game will have the same key, but nodes with duplicate keys can not be in an AVL tree. Also note that the AVL tree implementation must use links (an array implementation may not fit in memory when the number of objects is very large).

If your game includes images, it should include the ability to switch the image drawing to rectangles for testing purposes. Also, your program should display the number of comparison operations that are made for collision detection at every frame.

Your game should also include something new that improves the game in addition to the above requirements. Be prepared to demo your game in class on Wednesday including an asymptotic analysis of and the number of comparisons when using the different collision detection algorithms.

Hand In: Tar and email your code to your instructor with a subject of cpsc220 assign 3 before class on Wednesday, October 7th.