by Sven Woltmann – August 31, 2021

**Article Series:** Trees

**Part 3: AVL Tree**

(Sign up for the HappyCoders Newsletter

to be immediately informed about new parts.)

An AVL tree is a concrete implementation of a self-balancing binary search tree. It was developed in 1962 by Soviet computer scientists Georgi Maximovich **A**delson-**V**elsky and Yevgeny Mikhailovich **L**andis and named after their initials.

In this article, you'll learn:

- What is an AVL tree?
- How to calculate the balance factor in an AVL tree?
- What is AVL tree rotation, and how does it work?
- How to insert elements, and how to delete them?
- How to implement an AVL tree in Java?
- What is the time complexity of the AVL tree operations?
- How does the AVL tree differ from the red-black tree?

You can find the source code for the article in this GitHub repository.

An AVL tree is a balanced binary search tree – that is, a binary search tree in which the heights of the left and right subtrees of each node differ by at most one.

After each insert and delete operation, this invariant is verified, and the balance is restored by AVL rotation if necessary.

The height of a (sub) tree indicates how far the root is from the lowest node. Therefore, a (sub) tree that consists of only a root node has a height of 0.

The balance factor "BF" of a node denotes the difference of the heights "H" of the right and left subtree ("node.right" and "node.left"):

*BF(node) = H(node.right) - H(node.left)*

The height of a non-existent subtree is -1 (one less than the height of a subtree consisting of only one node).

There are three cases:

- If the balance factor is < 0, the node is said to be
*left-heavy*. - If the balance factor is > 0, the node is said to be
*right-heavy*. - A balance factor of 0 represents a
*balanced*node.

In an AVL tree, the balance factor at each node is -1, 0, or 1.

The following example shows an AVL tree with height and balance factor specified at each node:

Nodes 2 and 7 in this example are right-heavy, node 4 is left-heavy. All other nodes are balanced.

The following tree, however, is *not* an AVL tree since the AVL criterion (*-1 ≤ BF ≤ 1*) is not fulfilled at node 4. Its left subtree has a height of 1, and the right, empty subtree has a height of -1. The difference between them is -2.

To implement the AVL tree in Java, we use the Java source code for the binary search tree from the previous tutorial in the binary tree series.

Nodes are represented by the `Node`

class. For the node's `data`

field, we use `int`

primitives for simplicity. In `height`

, we store the height of the subtree whose root is this node.

```
public class Node {
int data;
Node left;
Node right;
int height;
public Node(int data) {
this.data = data;
}
}
```

Code language: GAUSS (gauss)

The AVL tree is implemented by the `AvlTree`

class. It extends the `BinarySearchTreeRecursive`

class introduced in the previous part. We will reuse much of its functionality.

For balancing the AVL tree, we need the following three additional methods:

`height()`

returns the height of a subtree stored in`node.height`

‒ or -1 for an empty subtree.`updateHeight()`

sets`node.height`

to the maximum height of the children plus 1.`balanceFactor()`

calculates a node's balance factor.

```
public class AvlTree extends BinarySearchTreeRecursive {
private int height(Node node) {
return node != null ? node.height : -1;
}
private void updateHeight(Node node) {
int leftChildHeight = height(node.left);
int rightChildHeight = height(node.right);
node.height = max(leftChildHeight, rightChildHeight) + 1;
}
private int balanceFactor(Node node) {
return height(node.right) - height(node.left);
}
// ...
}
```

Code language: Java (java)

We will extend the code step by step in the following sections.

Inserting into and deleting from an AVL tree works basically as described in the article about binary search trees.

If the AVL invariant is no longer fulfilled after an insert or delete operation, we must rebalance the tree. We will do that by so-called rotations.

We distinguish between right and left rotation.

The following image shows a right rotation. The (sub) tree shown contains the following nodes:

*N*: the node where an imbalance was detected*L*: the left child node of*N**LL*: the left child node of*L**LR*: the right child node of*L**R*: the right child node of*N*

Under each letter, I have given an example node value in parentheses. This clearly shows that the following in-order sequence applies before the rotation:

*LL (1) < L (2) < LR (3) < N (4) < R (5)*

During rotation, node *L* moves to the root, and the previous root *N* becomes the right child of *L*. The previous right child of *L*, *LR* becomes the new left child of *N*. The two remaining nodes, *LL* and *R* remain unchanged relative to their parent node.

The example values in parentheses show clearly that the rotation has not changed the nodes' in-order sequence.

The Java code for the right rotation is straightforward (class `AvlTree`

, starting at line 71).

```
private Node rotateRight(Node node) {
Node leftChild = node.left;
node.left = leftChild.right;
leftChild.right = node;
updateHeight(node);
updateHeight(leftChild);
return leftChild;
}
```

Code language: Java (java)

We memorize the left child `leftChild`

(*L* in the image) of `node`

(*N* in the image), replace the left child of `node`

with the right child of the left child `leftChild.right`

(*LR* in the image) and then set `node`

as the new right child of the left child.

Then we update the heights of the subtrees in the order shown. I have already described the `updateHeight()`

method in the "AVL Tree Implementation in Java" section.

The return value of the method is the new root node `leftChild`

(*L* in the image).

Left rotation works similarly:

Node *R* becomes the root; the previous root *N* becomes the left child of *R*. The previous left child of *R*, *RL* becomes the new right child of *N*. The relative positions of nodes *RR* and *L* do not change.

Also during left rotation, the in-order sequence of the nodes (*L < N < RL < R < RR*) is preserved.

The Java code looks as follows (class `AvlTree`

, from line 83):

```
private Node rotateLeft(Node node) {
Node rightChild = node.right;
node.right = rightChild.left;
rightChild.left = node;
updateHeight(node);
updateHeight(rightChild);
return rightChild;
}
```

Code language: Java (java)

After insertion into or deletion from the AVL tree, we calculate the height and balance factor from the inserted or deleted node upwards to the root.

If, at a node, we determine that the AVL invariant is no longer satisfied (i.e., the balance factor is less than -1 or greater than +1), we must rebalance. We differentiate four cases:

- Balancing a left-heavy node:
- Right rotation
- Left-right Rotation

- Balancing a right-heavy node:
- Left rotation
- Right-left rotation

In the sections that follow, I describe the four cases using various examples.

We insert nodes 3, 2, and 1 into an empty tree. Without rebalancing, the tree then looks like this:

We examine the balance factor from the last inserted node 1 upwards:

- The balance factor at node 1 is 0.
- The balance factor at node 2 is -1; node 2 is therefore left-heavy. However, the AVL invariant (
*-1 ≤ BF ≤ 1*) is still fulfilled. - The balance factor at node 3 is -2; the AVL invariant is no longer fulfilled at this node.

In this case, we must perform a right rotation around node 3:

The new root is node 2, and its balance factor is 0. The AVL tree is balanced again.

We also have a left-heavy root in the following example, but the situation looks a little different. This time we insert the nodes in the order 3, 1, 2:

We notice that the AVL criterion is not fulfilled at the root (having a balance factor of -2). If we would now – as in the previous example – perform a right rotation, the tree would then look as follows:

The right child of node 1 – node 2 – became the left child of node 3. Instead of a left-heavy root with BF -2, we now have a right-heavy root with BF +2. We missed the target.

What can we do instead?

The correct procedure for this case (the root's left child is right-heavy) is a so-called left-right rotation. First, we rotate to the left around node 1 and then to the right around node 3:

With a balance factor of 0 at the new root 2, the AVL tree is balanced again.

For right-heavy nodes, we proceed analogously. We first insert nodes in the order 1, 2, 3 and obtain the following unbalanced tree:

The root's balance factor is +2. We can restore the balance by a single left rotation:

The fourth and final example shows an AVL tree with the nodes inserted in the order 1, 3, 2:

The root's balance factor is +2 again. But with a left rotation as in the previous example, the following would happen:

The left child of node 3 – node 2 – became the right child of node 1. Instead of a right-heavy root, we now have a left-heavy root with a balance factor of -2.

Analogous to the second case, the correct procedure in this case (the root's right child is left-heavy) is a right-left rotation. We rotate to the right around node 3 and then to the left around node 1:

With this, you have learned all the variations of balancing the AVL tree.

The four previous sections combined give the following rebalancing rule. *BF* stands for balance function, *N* for the node under consideration, and *L* and *R* for its left and right children, respectively.

Case | Condition | Rebalancing |
---|---|---|

1. | BF(N) < -1 and BF(L) ≤ 0 | Right rotation around N |

2. | BF(N) < -1 and BF(L) > 0 | Left rotation around L followed by right rotation around N |

3. | BF(N) > 1 and BF(R) ≥ 0 | Left rotation around N |

4. | BF(N) > 1 and BF(R) < 0 | Right rotation around R followed by left rotation around N |

In the Java code, we implement the rebalancing algorithm in the following `rebalance()`

method (class `AvlTree`

, starting at line 41):

```
private Node rebalance(Node node) {
int balanceFactor = balanceFactor(node);
// Left-heavy?
if (balanceFactor < -1) {
if (balanceFactor(node.left) <= 0) { // Case 1
// Rotate right
node = rotateRight(node);
} else { // Case 2
// Rotate left-right
node.left = rotateLeft(node.left);
node = rotateRight(node);
}
}
// Right-heavy?
if (balanceFactor > 1) {
if (balanceFactor(node.right) >= 0) { // Case 3
// Rotate left
node = rotateLeft(node);
} else { // Case 4
// Rotate right-left
node.right = rotateRight(node.right);
node = rotateLeft(node);
}
}
return node;
}
```

Code language: Java (java)

The code corresponds to the algorithm described above; comments reference the four cases. The method returns the new root node of the (sub) tree.

Now that we have the tool for rebalancing the tree (the `rebalance()`

method from the previous section), we can assemble the insertion and deletion methods.

To insert a node into the AVL tree, we first proceed as described in the "Binary Search Tree Insertion" section of the previous tutorial. After that we call `updateHeight()`

and `rebalance()`

.

Since our `AvlTree`

class inherits from `BinarySearchTreeRecursive`

, the insert method is called via `super.insertNode()`

(defined in `BinarySearchTreeRecursive`

starting at line 34):

```
@Override
Node insertNode(int key, Node node) {
node = super.insertNode(key, node);
updateHeight(node);
return rebalance(node);
}
```

Code language: Java (java)

To delete a node, we proceed as described in the section "Binary Search Tree Deletion" of the previous tutorial. Afterwards we call `updateHeight()`

and `rebalance()`

– as we did for the insertion:

You will find the method called with `super.deleteNode()`

in `BinarySearchTreeRecursive`

starting at line 57.

```
@Override
Node deleteNode(int key, Node node) {
node = super.deleteNode(key, node);
// Node is null if the tree doesn't contain the key
if (node == null) {
return null;
}
updateHeight(node);
return rebalance(node);
}
```

Code language: Java (java)

Searching in an AVL tree works precisely like searching in a binary search tree. Therefore, the `searchNode()`

method from `BinarySearchTreeRecursive`

does not need to be overridden.

Traversal in pre-order, post-order, in-order, reverse-in-order, and level-order is defined for binary trees in general. You can find the definitions in the "Binary Tree Traversal" section of the binary trees article.

The traversal classes `DepthFirstTraversal`

, `DepthFirstTraversalIterative`

, and `DepthFirstTraversalRecursive`

introduced in that article can also be applied to `AvlTree`

, which indirectly implements the `BinaryTree`

interface on which the traversal methods are defined.

(For an explanation of time complexity and complexity classes like *O(log n)*, see the article "Big O Notation and Time Complexity – Easily Explained").

The following operations occur when searching, inserting, and deleting:

- The maximum number of node comparison operations corresponds to the AVL tree's height.
- The maximum number of balance factor calculations is twice as high as we must also take a child's balance factor into account.
- The maximum number of rotations is also equal to twice the height of the AVL tree since no, one or two rotations are performed per level.
- The height is recalculated for two nodes per rotation. The maximum number of height calculations is, therefore, four times the tree height.

Since an AVL tree is a balanced binary tree – i.e., doubling the number of nodes only adds one level – the height of the AVL tree is of the order *O(log n)*.

Since the costs of all the above operations are constant, and the number of their executions is proportional to the tree height, the time complexity for searching, inserting, and deleting is also *O(log n)* each.

In the following sections, you will find the advantages and disadvantages of the AVL tree compared to similar data structures.

Both the AVL tree and the red-black tree are self-balancing binary search trees.

In the AVL tree, we perform rebalancing by calculating balance factors and subsequent rotations. The absolute height difference at any node is not greater than 1.

In a red-black tree, nodes are marked by colors (red/black). Rotations occur when certain criteria for color sequences are no longer met. The absolute height difference at a node can be greater than 1. More precisely, the lowest leaf can be up to twice as far from the root as the highest leaf.

These characteristics result in the following differences:

- Searching in the AVL tree is usually faster than in the red-black tree because the AVL tree is better balanced.
- Insertions and deletions, on the other hand, are faster in a red-black tree because it rebalances less frequently.
- AVL trees need an extra byte per node for storing their height. Red-black trees need only one bit per node for the color information. In Java practice, this makes no difference as at least one byte is occupied for the bit anyway.

An AVL tree is a binary search tree that re-establishes the AVL invariant by rotation after each insert and delete operation.

A binary search tree does not necessarily have to be balanced. Likewise, we can achieve balancing by other than the AVL tree algorithm.

Therefore, every AVL tree is a binary search tree. But not every binary search tree is an AVL tree.

In this tutorial, you learned what an AVL tree is and how to rebalance it after insert or delete operations by single or double rotation. You also learned how to implement an AVL tree in Java.

The next part will be about another concrete type of binary search tree: the red-black tree. Would you like to receive an email when the article is published? Then click here to join the HappyCoders newsletter.

If you liked the article, feel free to share it using one of the share buttons at the end or drop me a comment.

About the author

I'm a freelance software developer with more than two decades of experience in scalable Java enterprise applications. My focus is on optimizing complex algorithms and on advanced topics such as concurrency, the Java memory model, and garbage collection.
Here on HappyCoders.eu, I want to help you become a better Java programmer. Read more about me here.