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

1. height = max distance from a leaf (leaf has zero height, parent of leaf has height 1)
2. balance = height of left sub-tree — height of right sub-tree (technically can be calculated and doesn’t need to be stored)

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

performance ⏱️

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

• rebalance the tree upon each insert
• update ‘height’ data upon each insert

no guarantee of being weight-balanced