Adelson-Velsky-Landis Tree

trees

Definition

Adelson-Velsky-Landis Tree

An AVL tree is a self-balancing binary search tree with the benefit that lookup, insertion, and deletion all take (logarithmic time complexity) and only take (linear) space complexity.

A binary search tree is called AVL tree if all of its tree nodes are balanced, i.e. for every tree node , it holds:

where is the balance of .

It’s named after Georgy Adelson-Velsky and Evgenii Landis.

Height

The height of an empty tree is defined as :

def height(u: TreeNode) -> int:
	if u == null:
		return -1
	else:
		return u.height

Height Theorem

The height condition of an AVL tree ensures that the height of an AVL tree with nodes is constrained by .

Balance

Let be a tree node of a AVL tree, and be the height of ‘s left subtree and be the height of ‘s right subtree.

The balance is defined as:

Note that the height of an empty tree is defined as .

Balanced Node

A tree node is called balanced iff:

Operations

Insertion

The insertion operation of a tree node into the AVL tree is equal to the insertion in binary search trees, except that the AVL tree rebalances afterwards.

The time complexity of adding a node is logarithmic, i.e. .

Removal

The insertion operation of a tree node into the AVL tree is equal to the removal in binary search trees, except that the AVL tree rebalances afterwards.

The time complexity of removing a node is logarithmic, i.e. .

Rebalance

After an alteration, i.e. insertion or removal, of the AVL tree, rebalancing is mandatory to ensure all remaining nodes are balanced.