AVL Trees and Balancing

Question 1

What is the AVL Tree Property?

Answer 1

Vertex x is said to be height-balanced if |x.left.height - x.right.height| <= 1. A BST is said to be height balanced if every vertex in the tree is height balanced. It makes the O(h) operations in BST become O(logn).

Question 2

What is the balance factor?

Answer 2

bf(x) = x.left.height - x.right.height
If we get a balance factor of +2, left subtree is taller. If -2, right subtree is taller. This is checked from the insertion point all the way up to the root node.