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 $O(\log n)$ (logarithmic time complexity) and only take $O(n)$ (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 $v$, it holds:

$$\text{bal}(v)\in \{-1,0,1\}$$

where $\text{bal}(v)$ is the balance of $v$.

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

Height

The height of an empty tree is defined as $-1$:

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 $n\ge 1$ nodes is constrained by $O(\log n)$.

Balance

Let $v$ be a tree node of a AVL tree, and $h_{v,l}$ be the height of $v$‘s left subtree and $h_{v,r}$ be the height of $v$‘s right subtree.

The balance $\text{bal}(v)$ is defined as:

$$\text{bal}(v)=\text{height}(v.right)-\text{height}(v.left)$$

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

Balanced Node

A tree node is called balanced iff:

$$v\text{ balanced}:⟺\text{bal}(v)\in \{-1,0,1\}$$

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. $O(\log n)$.

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. $O(\log n)$.

Rebalance

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