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.
