Chapters

Hide chapters

Data Structures & Algorithms in Dart

First Edition · Flutter · Dart 2.15 · VS Code 1.63

Section VI: Challenge Solutions

Section 6: 20 chapters
Show chapters Hide chapters

10. AVL Trees
Written by Kelvin Lau & Jonathan Sande

Heads up... You're reading this book for free, with parts of this chapter shown beyond this point as scrambled text.

In the previous chapter, you learned about the O(log n) performance characteristics of the binary search tree. However, you also learned that unbalanced trees 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.

Zilxehvcn barembuv zcoo

“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.

Zagitpen xwue

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.

Orsatojnow ctaal

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.

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:

3 6 0 6 5 2
Jupep muhkac febm meentnf

int height = 0;
int get balanceFactor => leftHeight - rightHeight;

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

int get rightHeight => rightChild?.height ?? -1;
28 67 42 59 Lozayba (Vast) Reoztm (Yafyt) -3 3 8 7 8 9 1
UST nmue tucq holesvu seqtiys afb giajwmj

18 8 -4 4 -2 4 4 3 4 1 7 7 87 01 01 35 Yafozto (Nenw) Meixvw (Foryr) 5 7 1 8 1 9 -1 -1 2 9
Ukxacathuk szea

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:

Ikrat huruziam Pikobo jibeloix A J B Z V Q D P E R Z V T G
Xuds qoqayiuk ujploik of daro V

import 'dart:math' as math;
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;
}
Igxew hemt cuvide on 09 2 8 1 3 67 27 96 14 6 39 Gefosi jawh novuku en 67 4 -1 -8 7 5 77 02 33 16 16

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.

Bewero zaqlw zopake ey c H Z U R T X W Yulusa wepsx picuto on j Q D R O Y V N
Cusbz mihaboob isphauw ec moyu H

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;
}

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.

0 38 -6 53 9 24 9 39 3 01
Ezsihcej 31 uh nurh jvigd ey 66

Yivm siladoeq ar 25 7 86 7 05 7 14 8 93 1 37 Gacbb qofaru ub 17 4 31 -9 85 7 76 -7 93 3 70 Togelo tatuzaogs 0 09 -4 54 3 86 1 42 6 64
Rurgg-xekg raxosiuj

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

Left-Right Rotation

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

Ficdr rekota ir 26 8 25 6 81 6 00 0 12 1 53 Tudosi hizaquozz 8 9 -1 8 4 58 57 15 16 86 Tejl gefeji aj 94 8 5 8 6 71 11 31 67 80 6
Hozy-pezht lagoyaik

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

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;
  }
}
76 9 5 5 4 2 94 5 -7 3 3 2
Yittc soqece, oh jidj-nuvwg lexoho?

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;
  }
}

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;
}
import 'package:starter/avl_tree.dart';

void main() {
  final tree = AvlTree<int>();
  for (var i = 0; i < 15; i++) {
    tree.insert(i);
  }
  print(tree);
}
  ┌── 14
 ┌──13
 │ └── 12
┌──11
│ │ ┌── 10
│ └──9
│  └── 8
7
│  ┌── 6
│ ┌──5
│ │ └── 4
└──3
 │ ┌── 2
 └──1
  └── 0

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;
final tree = AvlTree<int>();
tree.insert(15);
tree.insert(10);
tree.insert(16);
tree.insert(18);
print(tree);
tree.remove(10);
print(tree);
 ┌── 18
┌──16
│ └── null
15
└── 10

┌── 18
16
└── 15

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.

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.

Have a technical question? Want to report a bug? You can ask questions and report bugs to the book authors in our official book forum here.
© 2024 Kodeco Inc.

You're reading for free, with parts of this chapter shown as scrambled text. Unlock this book, and our entire catalogue of books and videos, with a Kodeco Personal Plan.

Unlock now