AVL Trees

Question 1

AVL Trees

Answer 1

• type of binary search tree with the additional invariant that tree is balanced
• implemented just like a bst, with additional “rotation” operations
• each time you insert or delete an item, you balance nodes along path of insertion/deletion

Question 2

rotation

Answer 2

• operation used to balance a tree
• mainly involves changing pointers
• shift the root and the left (or right) child over, while maintaining the relative order of the subtrees

2 types of rotation

1. left rotation
2. right rotation

Question 3

AVL

balancing tree

Answer 3

• process of restoring the balanced invariant

Steps (left-heavy):

1. Check balance factor of root node and children
2. If bf(root) == -2, tree is left-heavy
3. If bf(left) < 0 or bf(left) == 0 → case: left-left
   
   • Perform right rotation on root
4. If bf(left) > 0 → case: left-right
   
   • Perform left rotation of left child
   • Perform right rotation on root
5. Use reverse logic for right-heavy trees

Question 4

height of a node

Answer 4

• number of edges from a node to its furthest leaf
• height(node) = max(left subtree, right subtree) + 1
  
  • where the empty tree has height of -1
• the height of a tree is the height of the root

Question 5

balance factor

Answer 5

• balance factor (bf) of a tree is the difference in the heights of both subtrees
• bf(node n) = height(right subtree) - height(left substree)

Question 6

balanced tree

Answer 6

• a tree where the heights of the left and right subtrees differ by no more than 1
• a tree is balanced if balance factor is {-1, 0, 1}