AVL Trees
(A)delson-(V)elsky & Evgenii (L)andis Tree
A self-balancing tree.
$$ balance(tree) = height(left(tree)) - height(right(tree)) $$and aims to always be:
$$ balance(tree) \in \{-1,0,1\} $$This is (in the bigger picture) done by changing root node to balance the left and right “heights” of the tree. In a B-Tree, it’s a left rotation if the child has a greater value than the parent, and a right rotation if the child has a smaller value than the parent.