10 AVL Trees

In the previous chapter, you learned about the O(log n) performance characteristics of the binary search tree. However, you also learned that unbalancedtrees can deteriorate the performance of the tree, all the way down to O(n). In 1962, Georgy Adelson-Velsky and Evgenii Landis came up with the first self-balancing binary search tree: The AVL Tree. In this chapter, you’ll dig deeper into how the balance of a binary search tree can impact performance and implement the AVL tree from scratch!

Understanding Balance

A balanced tree is the key to optimizing the performance of the binary search tree. In this section, you’ll learn about the three main states of balance: perfectly balanced, balanced and unbalanced.

Perfect Balance

The ideal form of a binary search tree is the perfectly balanced state. In technical terms, this means every level of the tree is filled with nodes, from top to bottom.

Perfectly balanced tree

Not only is the tree perfectly symmetrical, the nodes at the bottom level are completely filled. This is the requirement for being perfectly balanced.

“Good-enough” Balance

Although achieving perfect balance is ideal, it’s rarely possible. A perfectly balanced tree must contain the exact number of nodes to fill every level to the bottom, so it can only be perfect with a particular number of elements.

For example, a tree with 1, 3 or 7 nodes can be perfectly balanced, but a tree with 2, 4, 5 or 6 cannot be perfectly balanced since the last level of the tree will not be filled.

Balanced tree

The definition of a balanced tree is that every level of the tree must be filled, except for the bottom level. For most binary trees, this is the best you can do.

Unbalanced

Finally, there’s the unbalanced state. Binary search trees in this state suffer from various levels of performance loss, depending on the degree of imbalance.

Unbalanced trees

Keeping the tree balanced gives the find, insert and remove operations an O(log n) time complexity. AVL trees maintain balance by adjusting the structure of the tree when the tree becomes unbalanced. You’ll learn how this works as you progress through the chapter.

Implementation

Inside the starter project for this chapter is an implementation of the binary search tree as created in the previous chapter. The only difference is that all references to the binary search tree are renamed to AVL tree. Similarly, the binary node is renamed to AVL node.

Binary search trees and AVL trees share much of the same implementation; in fact, all that you’ll add is the balancing component. Open the starter project to begin.

Measuring Balance

To keep a binary tree balanced, you’ll need a way to measure the balance of the tree. The AVL tree achieves this with a height property in each node. In tree-speak, the height of a node is the longest distance from the current node to a leaf node:

032010Nodes marked with heights

Open the lib folder and add the following property to AvlNode in avl_node.dart:

int height = 0;

You’ll use the relative heights of a node’s children to determine whether a particular node is balanced. The height of the left and right children of each node must differ at most by 1. This number is known as the balance factor.

Write the following just below the height property of AvlNode:

int get balanceFactor => leftHeight - rightHeight;

int get leftHeight => leftChild?.height ?? -1;

int get rightHeight => rightChild?.height ?? -1;

The balanceFactor computes the height difference of the left and right child. If a particular child is null, its height is considered to be -1.

Here’s an example of an AVL tree. The diagram shows a balanced tree — all levels except the bottom one are filled. The numbers to the right of the node represent the height of each node, while the numbers to the left represent the balanceFactor.

50253775Balance (Left)Height (Right)-1001011AVL tree with balance factors and heights

Here’s an updated diagram with 40 inserted. Inserting 40 into the tree turns it into an unbalanced tree. Notice how the balanceFactor changes:

502-22-1000103025753740Balance (Left)Height (Right)302102-2-100Unbalanced tree

A balanceFactor of 2 or -2 or something more extreme indicates an unbalanced tree. By checking after each insertion or deletion, though, you can guarantee that it’s never more extreme than a magnitude of two.

Although more than one node may have a bad balancing factor, you only need to perform the balancing procedure on the bottom-most node containing the invalid balance factor. For example, in the figure above both 50 and 25 have a balance factor with a magnitude of 2. However, you only need to perform the balancing procedure on the lower node, that is, the one containing 25.

This is where rotations come in.

Rotations

The procedures used to balance a binary search tree are known as rotations. There are four rotations in total, one for each of the four different ways that a tree can be unbalanced. These are known as left rotation, left-right rotation, right rotation and right-left rotation.

Left Rotation

The imbalance caused by inserting 40 into the tree can be solved by a left rotation. A generic left rotation of node X looks like this:

After rotationBefore rotationABCDYXZXABYZCDLeft rotation applied on node X

Before going into specifics, there are two takeaways from this before-and-after comparison:

• In-order traversal for these nodes remains the same.
• The depth of the tree is reduced by one level after the rotation.

Open lib/avl_tree.dart and add the dart:math library to the top of the file:

import 'dart:math' as math;

Then add the following method to AvlTree below the _insertAt method:

AvlNode<E> leftRotate(AvlNode<E> node) {
  // 1
  final pivot = node.rightChild!;
  // 2
  node.rightChild = pivot.leftChild;
  // 3
  pivot.leftChild = node;
  // 4
  node.height = 1 +
      math.max(
        node.leftHeight,
        node.rightHeight,
      );
  pivot.height = 1 +
      math.max(
        pivot.leftHeight,
        pivot.rightHeight,
      );
  // 5
  return pivot;
}

Here are the steps needed to perform a left rotation:

1. The right child is chosen as the pivot point. This node will replace the rotated node as the root of the subtree. That means it’ll move up a level.
2. The node to be rotated will become the left child of the pivot. It moves down a level. This means that the current left child of the pivot must be moved elsewhere. In the generic example shown in the earlier image, this is node B. Because B is smaller than Y but greater than X, it can replace Y as the right child of X. So you update the rotated node’s rightChild to the pivot’s leftChild.
3. The pivot’s leftChild can now be set to the rotated node.
4. You update the heights of the rotated node and the pivot.
5. Finally, you return the pivot so that it can replace the rotated node in the tree.

Here are the before-and-after effects of the left rotation of 25 from the previous example:

After left rotate on 25100050372540075Before left rotate on 252-2-1005025374075

Right Rotation

Right rotation is the symmetrical opposite of left rotation. When a series of left children is causing an imbalance, it’s time for a right rotation.

A generic right rotation of node X looks like this:

Before right rotate of xYZABCDXBefore right rotate of xXYZADCBRight rotation applied on node X

To implement this, add the following code just after leftRotate:

AvlNode<E> rightRotate(AvlNode<E> node) {
  final pivot = node.leftChild!;
  node.leftChild = pivot.rightChild;
  pivot.rightChild = node;
  node.height = 1 +
      math.max(
        node.leftHeight,
        node.rightHeight,
      );
  pivot.height = 1 +
      math.max(
        pivot.leftHeight,
        pivot.rightHeight,
      );
  return pivot;
}

This algorithm is nearly identical to the implementation of leftRotate, except the references to the left and right children are swapped.

Right-Left Rotation

You may have noticed that the left and right rotations balance nodes that are all left children or all right children. Consider the case in which 36 is inserted into the original example tree.

The tree now requires a right-left rotation:

250-225075137036Inserted 36 as left child of 37

Doing a left rotation, in this case, won’t result in a balanced tree. The way to handle cases like this is to perform a right rotation on the right child before doing the left rotation. Here’s what the procedure looks like:

Left rotation on 25150036025037075Right rotate on 37250-225075-136037Before rotations250-225075137036Right-left rotation

1. You apply a right rotation to 37.
2. Now that nodes 25, 36 and 37 are all right children, you can apply a left rotation to balance the tree.

Add the following code just after rightRotate:

AvlNode<E> rightLeftRotate(AvlNode<E> node) {
  if (node.rightChild == null) {
    return node;
  }
  node.rightChild = rightRotate(node.rightChild!);
  return leftRotate(node);
}

Don’t worry just yet about when to call this. You’ll get to that in a second. You first need to handle the last case, left-right rotation.

Left-Right Rotation

Left-right rotation is the symmetrical opposite of the right-left rotation. Here’s an example:

Right rotate of 25150015010025075Before rotations22-1005025101575Left rotate of 10221050251510750Left-right rotation

1. You apply a left rotation to node 10.
2. Now that nodes 25, 15 and 10 are all left children; you can apply a right rotation to balance the tree.

Add the following code just after rightLeftRotate:

AvlNode<E> leftRightRotate(AvlNode<E> node) {
  if (node.leftChild == null) {
    return node;
  }
  node.leftChild = leftRotate(node.leftChild!);
  return rightRotate(node);
}

That’s it for rotations. Now you just need to apply them at the correct time.

Balance

The next task is to design a method that uses balanceFactor to decide whether a node requires balancing or not. Write the following method below leftRightRotate:

AvlNode<E> balanced(AvlNode<E> node) {
  switch (node.balanceFactor) {
    case 2:
    // ...
    case -2:
    // ...
    default:
      return node;
  }
}

There are three cases to consider.

1. A balanceFactor of 2 suggests that the left child is “heavier” (contains more nodes) than the right child. This means that you want to use either right or left-right rotations.
2. A balanceFactor of -2 suggests that the right child is heavier than the left child. This means that you want to use either left or right-left rotations.
3. The default case suggests that the particular node is balanced. There’s nothing to do here except to return the node.

The sign of the child’s balanceFactor can be used to determine if a single or double rotation is required:

1021052102-1057Right rotate, or left-right rotate?

Replace balanced with the following:

AvlNode<E> balanced(AvlNode<E> node) {
  switch (node.balanceFactor) {
    case 2:
      final left = node.leftChild;
      if (left != null && left.balanceFactor == -1) {
        return leftRightRotate(node);
      } else {
        return rightRotate(node);
      }
    case -2:
      final right = node.rightChild;
      if (right != null && right.balanceFactor == 1) {
        return rightLeftRotate(node);
      } else {
        return leftRotate(node);
      }
    default:
      return node;
  }
}

balanced inspects the balanceFactor to determine the proper course of action. All that’s left is to call balanced at the proper time.

Revisiting Insertion

You’ve already done the majority of the work. The remainder is fairly straightforward. Replace _insertAt with the following:

AvlNode<E> _insertAt(AvlNode<E>? node, E value) {
  if (node == null) {
    return AvlNode(value);
  }
  if (value.compareTo(node.value) < 0) {
    node.leftChild = _insertAt(node.leftChild, value);
  } else {
    node.rightChild = _insertAt(node.rightChild, value);
  }
  final balancedNode = balanced(node);
  balancedNode.height = 1 +
      math.max(
        balancedNode.leftHeight,
        balancedNode.rightHeight,
      );
  return balancedNode;
}

Instead of returning the node directly after inserting, you pass it into balanced. Passing it ensures every node in the call stack is checked for balancing issues. You also update the node’s height.

That’s all there is to it! Open bin/starter.dart and replace the contents of the file with the following:

import 'package:starter/avl_tree.dart';

void main() {
  final tree = AvlTree<int>();
  for (var i = 0; i < 15; i++) {
    tree.insert(i);
  }
  print(tree);
}

Run that and you should see the following output in the console:

  ┌── 14
 ┌──13
 │ └── 12
┌──11
│ │ ┌── 10
│ └──9
│  └── 8
7
│  ┌── 6
│ ┌──5
│ │ └── 4
└──3
 │ ┌── 2
 └──1
  └── 0

Take a moment to appreciate the uniform spread of the nodes. If the rotations weren’t applied, this would have become a long, unbalanced link of right children.

Revisiting Remove

Retrofitting the remove operation for self-balancing is just as easy as fixing insert. In AvlTree, find _remove and replace the final return node;statement with the following:

final balancedNode = balanced(node);
balancedNode.height = 1 +
    math.max(
      balancedNode.leftHeight,
      balancedNode.rightHeight,
    );
return balancedNode;

Head back to starter.dart and replace the body of main with the following code:

final tree = AvlTree<int>();
tree.insert(15);
tree.insert(10);
tree.insert(16);
tree.insert(18);
print(tree);
tree.remove(10);
print(tree);

Run that and you should see the following console output:

 ┌── 18
┌──16
│ └── null
15
└── 10

┌── 18
16
└── 15

Removing 10 caused a left rotation on 15. Feel free to try out a few more test cases of your own.

Whew! The AVL tree is the culmination of your search for the ultimate binary search tree. The self-balancing property guarantees that the insert and remove operations function at optimal performance with an O(log n) time complexity.

Challenges

Here are three challenges that revolve around AVL trees. Solve these to make sure you have the concepts down. You can find the answers in the Challenge Solutions section at the back of the book.

Challenge 1: Number of Leaves

How many leaf nodes are there in a perfectly balanced tree of height 3? What about a perfectly balanced tree of height h?

Challenge 2: Number of Nodes

How many nodes are there in a perfectly balanced tree of height 3? What about a perfectly balanced tree of height h?

Challenge 3: A Tree Traversal Interface

Since there are many variants of binary trees, it makes sense to group shared functionality in an interface. The traversal methods are a good candidate for this.

Create a TraversableBinaryNode abstract class that provides a default implementation of the traversal methods so that conforming types get these methods for free. Have AvlNode extend this.

Key Points

• A self-balancing tree avoids performance degradation by performing a balancing procedure whenever you add or remove elements in the tree.
• AVL trees preserve balance by readjusting parts of the tree when the tree is no longer balanced.
• Balance is achieved by four types of tree rotations on node insertion and removal: right rotation, left rotation, right-left rotation and left-right rotation.

Where to Go From Here?

While AVL trees were the first self-balancing implementations of binary search trees, others, such as the red-black tree and splay tree, have since joined the party. If you’re interested, look them up. You might even try porting a version from another language into Dart.