AVL Tree

AVL Tree is a type of balanced binary search tree which is early invented data structure in binary search solutions. It requires a stable property that the absolute difference between the height of the left subtree of root and the height of the right subtree of root is no larger than 1.

Height Guarantee

Formal Claim:

For every AVL Tree with 𝓃 nodes, its height 𝒽 ⩽ 2 ⋅ log(n).

Proof:

define Nh is the minimum number of nodes in an AVL Tree of height h, then

Nh = 1 + Nh-1 + Nh-2, Nh > 2 Nh-2

Obviously, n = Θ(2h/2) (given that Nh = n, N0 = 1, N1 = 2), h < 2 ⋅ log(n)

A more subtle claim:

a AVL Tree has most height of 1.44 ⋅ log(n + 2).

Proof:

Nh has a lower bound Ω(kh), then

substituting c ⋅ kh with both sides of the recurrence relation above yields:

c ⋅ kh ⩽ 1 + c ⋅ kh-1 + c ⋅ kh-2 = Τ(n)

in which to find out a c, h0 such that for every h > h0, the inequality above holds.

Divided both sides by c ⋅ kh-2:

k2 ⩽ k2-h/c + k + 1

wherein the term k2-h becomes relatively small when h grows very large, then the inequality will be satisfied if value of k is smaller than the solution to the equation: k2 = k + 1, which is the golden ratio φ = 1.618... ≈ 1.62

Hence, n = Ω(φh), conversely, h = Ο(logφn) ≈ 1.44 ⋅ log (n + 2)

Performance Comparisons

comparing with Red-Black Tree, AVL Tree has a better lookup performance given its relative shorter height of the tree: 1.44 ⋅ log(n + 2) < 2 ⋅ log(n + 1);

While the Red-Black Tree requires less costs during tree adjustments when INSERTION or DELETION operations happen than the AVL Tree does;

In conclusion, the AVL Tree is performant if used in scenarios where the number of element lookup dominates the number of element updates.