AVL trees

Question 1

Describe the AVL tree structure.

Answer 1

The AVL tree is similar to a binary search tree.

We want to make sure the tree is balanced - the height should be as low as possible.

To achieve this, we keep track of the height of each subtree. By taking the difference in these values, we find what’s called the balance factor. If this is outside the interval [-1, 1], the tree is unbalanced and we need to perform appropriate rotations.

Question 2

The subtrees can be in four different states. Describe these.

Answer 2

Follow this chart: http://imgur.com/a/6fd0P

The tree can be weighted to the left:

• LL (Left child, left child’s left child)
• LR (Left child, left child’s right child)

The tre can be weighted to the right, which are mirrored left-weighted problems.

• RR (Right child, right child’s right child)
• RL (Right child, right child’s left child)

Question 3

How do you do a left or right rotation? (LL or RR)

Answer 3

http://imgur.com/a/od9Rm

Question 4

How do you perform a LR or RL rotation?

Answer 4

http://imgur.com/a/BVWR8

Question 5

When do we need to perform rotations?

Answer 5

When a node’s balance factor is something besides is outside the interval [-1, 1].