Homework 8
AVL Tree
My AVL Tree is very similar to the Binary search tree. The key difference of course is that it self balances upon insertion on new elements by rotating each side of itself to be biased torwards that side (as a preparation for the next roation, and only if it isn't already), and then doing a rotation that will balance the nodes.
Everything went smoothly enough until I had to change the way that the program handles heights. The complexity beat me after two additional days and the speed of the insertion is dependant on the speed of the height collection algorithm. It couldn't handle 10000 units of insertion within a reasonable amount of time. I know the theory of how to do it though; need to store the height of a node, and adjust all the heights with of nodes that go through rotations. The complexity was more than I could decipher. So I have a slow AVL insertion.
These trees should be faster than the Binary Search Trees for very large N because they are more balanced, and thus can insert things without going ridiculous amounts of levels deeper. The extra operations should be cheap on running time, since it shouldn't need to rebalance terribly often for large N, that is the entire point.