AVL Trees

1. Rotations
   1. Right rotation
   2. Left rotation
   3. Right-left Rotation
   4. Left-right Rotation
2. General Form of AVL Rotations

In this section, we examine Adelson-Velsky & Landis trees, commonly known as AVL-trees.¹ AVL-trees are height-balanced binary search trees. Accordingly, they are a subset of balanced binary trees:

Given this fact, we might guess that there are various ways of defining what it means to be "balanced." And in fact, we would guess correctly. The term balanced tree, without more, could mean many things. Do we mean balanced in terms of weight? Height? Depth? Order? Node categories?

For AVL-trees, we define "balanced" in terms of height. And to construct that definition, we need a way of quantifying balance. We do so by defining a height balance factor:

Definition: Height Balance Factor. Let ${n}$ be a node in some tree. The height balance factor of ${n}$ is defined as:

$$\textit{\textsf{BF}}(n) = \textit{\textsf{H}}(\textit{\textsf{LST}}(n)) - \textit{\textsf{H}}(\textit{\textsf{RST}}(n))$$

where:

• ${\textit{\textsf{BF}}(n)}$ is the height balance factor of the node ${n,}$
• ${\textit{\textsf{H}}(\textit{\textsf{LST}}(n))}$ is the height of the left-subtree of the node ${n,}$ and
• ${\textit{\textsf{H}}(\textit{\textsf{RST}}(n))}$ is the height of the right-subtree of the node ${n.}$

To understand this definition, it's important to recall the definitions for height:

Definition: Height of a Node. Let ${n}$ be a node in some rooted tree. The height of ${n,}$ denoted ${\textit{\textsf{H}}(n),}$ is the number of nodes, including the starting and end nodes, along the longest strictly downward path from ${n}$ to a leaf.

Note that there are two different definitions for the height of a node. An alternative definition is:

Definition: Height of a Node. Let ${x}$ be a node in some tree ${T.}$ The height of ${x,}$ denoted ${\textit{\textsf{H}}(x),}$ is the number of edges in the longest strictly-downward path from ${x}$ to a leaf.

The key difference between this definition and the one we will use is whether a leaf has a height of ${0}$ or ${1.}$ The existence of two differing definitions for node height is similar to the situation of natural numbers in mathematics—does the set of natural numbers include ${0?}$ Some say yes, others no.

In response to this debate, we take the pragmatic approach. In some situations, it's more convenient to define the height of a node as the number of edges along the path, since this implies that a balanced binary tree of height ${H}$ has ${2^H}$ leaves. If we defined it as the number of nodes along the path (number of edges plus ${1}$), we would have ${H + 1}$ or ${H-1}$ leaves. For the purposes of AVL-trees, we use the definition presented in the main text.

Definition: Height of a Tree. Let ${\textsf{T}}$ be some rooted tree. The height of ${\textsf{T},}$ denoted ${\textit{\textsf{H}}(\textsf{T}),}$ is the height of its root node.

From the height balance factor ${\textit{\textsf{BF}},}$ we have the definition of an AVL tree:

Definition: avl-tree. Let ${A}$ be a binary tree. ${A}$ is an AVL-tree if, and only if, for every node ${n \in A,}$

$$\textit{\textsf{BF}}(n) \in \{ -1, 0, 1 \}$$

Or, alternatively:

$$\lvert \textit{\textsf{BF}}(n) \rvert \leq 1$$

Following the definition above, if the absolute value of the balance factor of some node ${x}$ is greater than or equal to ${1,}$ we say that the node ${x}$ is height-imbalanced. Moreover, to determine if a particular tree ${T}$ is an AVL-tree, we must calculate the height balance factor for each node in ${T.}$ If a single node in ${T}$ is imbalanced, we conclude that ${T}$ is height-imbalanced. If the tree is imbalanced, we can attempt to balance the tree by performing rotations, as we'll see later.

That said, let's consider a few examples. Below are several binary trees, with their heights indicated.

Examining each tree, we have the following tables of balance factors:

From the tables above, we can see that trees ${\texttt{C}}$ and ${\texttt{D}}$ are imbalanced. The same trees are presented below with their balance factors indicated (red for imbalanced, green for balanced).

Now that we know what it means for a tree to be imbalanced, let's examine rotating—the act of correct height imbalances.

General Form of AVL Rotations

AVL tree rotations have a general form. Consider the following tree:

The nodes without circles indicate that the child node is the root to some larger subtree. In this case, we see that Node(A) is imbalanced — it has a balance factor of 2. Given that Node(B) has a balance factor of 1, we see that the rotation should be an LL-rotation. If Node(B) had a balance factor of -1, the rotation would be an LR-rotation.

More generally:

Tree	Imbalance	Procedure
	Left-left	Left-left rotation
	Left-right	Left-right rotation
	Right-right	Right-right rotation
	Right-left	Right-left rotation

Returning to our imbalanced tree, how do we balance this tree knowing it potentially has thousands of other nodes in those subtrees? The idea is to just momentarily ignore the fact that those subtrees exist. Performing the LL-rotation, we get:

Now we see that it's balanced. The subtrees are now:

Ok hang on. How did those subtrees move? A helpful way to think about how the subtrees got to their positions is to imagine the links between each node as a thread:

Notice that by pulling the thread, the subtree slowly goes up, until it arrives at its final location. Knowing this general form, consider a more complicated tree:

This tree is balanced. Suppose we insert a new node with the value 4. Because 4 is smaller than 30, it goes towards the left, landing at the node containg 20. Then, because it's smaller than 20, it goes to the left again, landing on the node containing 10. And because it's smaller than 10, it lands at node 5. And because it's smaller than 5, it's inserted as the left child of 5:

Now that we've inserted node(4), the tree is imbalanced. To balance this tree, we focus on just three nodes:

After node(10), wherever node(4) is inserted, it's left-left imbalanced.