AVL trees = trees that fix imbalances as soon as they occur (self-balancing)
trees reasonably maintain balance with an O(log n) cost
accomplished by storing information on each node about its
repairs on tree balance are done locally, not on the overall structure
unbalanced tree: where $|$balance$|$ = $|$height of left sub-tree — height of right sub-tree$|$ $>1$
if we detect an unbalanced tree,
if (height of left sub-tree) > (height of right sub-tree), rotate right
if (height of right sub-tree) > (height of left sub-tree), rotate left
insertAVL(tree, item):
if tree is empty:
return new node containing item
else if item = data(tree):
return tree
if item < data(tree):
left(tree) = insertAVL(left(tree), item)
else if item > data(tree):
right(tree) = insertAVL(right(tree), item)
LHeight = height(left(tree))
RHeight = height(right(tree))
if (LHeight - RHeight) > 1:
if item > data(left(tree)):
left(tree) = rotateLeft(left(tree))
tree = rotateRight(tree)
else if (RHeight - LHeight) > 1:
if item < data(right(tree)):
right(tree) = rotateRight(right(tree))
tree = rotateLeft(tree)
return tree
pros:
search has worst-case performance is O(log n)
tree is always height-balanced (subtree-depths differ by 1 max)
cons:
an AVL tree uses more memory (to store ‘height’ data)
additionally, there is a finite amount of time added to
no guarantee of being weight-balanced