Assignment 8: AVL Tree

Building off of the binary search tree from last week's assignment, this week I made an AVL tree, which self balances as you add or delete nodes so that the AVL property is always maintained.

I performed two different timing tests on this week's tree and last week's tree.

First, I generated trees of random integers of different sizes.  In the first test I timed how long it took to find 30 random integers in each tree.



The regular binary search tree was sporadic (because of the randomness at work), but was always slower, and usually quite a bit slower than the AVL tree.

Next, I tested in order traversals.  They were about the same, but the AVL tree was slightly faster.




Home