## Data Structures & Algorithms in Kotlin

First Edition · Android 10 · Kotlin 1.3 · IDEA

#### Before You Begin

Section 0: 3 chapters

#### Section I: Introduction to Data Structures & Algorithms

Section 1: 2 chapters

#### Section II: Elementary Data Structures

Section 2: 3 chapters

#### Section IV: Sorting Algorithms

Section 4: 5 chapters

# 9. AVL Trees Written by Irina Galata, Kelvin Lau and Vincent Ngo

Heads up... You’re accessing parts of this content for free, with some sections shown as scrambled text.

Heads up... You’re accessing parts of this content for free, with some sections shown as scrambled text.

Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.

Unlock now

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 could 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. There are three main states of balance. You’ll look at each one.

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

### “Good-enough” balance

Although achieving perfect balance is ideal, it’s rarely possible because it also depends on the specific number of nodes. A tree with 2, 4, 5 or 6 cannot be perfectly balanced since the last level of the tree will not be filled.

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

## 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 have been renamed to AVL tree.

### Measuring balance

To keep a binary tree balanced, you 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:

``````var height = 0
``````
``````var height = 0

val leftHeight: Int
get() = leftChild?.height ?: -1

val rightHeight: Int
get() = rightChild?.height ?: -1

val balanceFactor: Int
get() = leftHeight - rightHeight
``````

### Rotations

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

#### Left rotation

You can solve the imbalance caused by inserting 40 into the tree using a left rotation. A generic left rotation of node X looks like this:

``````private fun leftRotate(node: AVLNode<T>): AVLNode<T> {
// 1
val pivot = node.rightChild!!
// 2
node.rightChild = pivot.leftChild
// 3
pivot.leftChild = node
// 4
node.height = max(node.leftHeight, node.rightHeight) + 1
pivot.height = max(pivot.leftHeight, pivot.rightHeight) + 1
// 5
return pivot
}
``````

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

``````private fun rightRotate(node: AVLNode<T>): AVLNode<T> {
val pivot = node.leftChild!!
node.leftChild = pivot.rightChild
pivot.rightChild = node
node.height = max(node.leftHeight, node.rightHeight) + 1
pivot.height = max(pivot.leftHeight, pivot.rightHeight) + 1
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.

``````private fun rightLeftRotate(node: AVLNode<T>): AVLNode<T> {
val rightChild = node.rightChild ?: return node
node.rightChild = rightRotate(rightChild)
return leftRotate(node)
}
``````

#### Left-right rotation

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

``````private fun leftRightRotate(node: AVLNode<T>): AVLNode<T> {
val leftChild = node.leftChild ?: return node
node.leftChild = rightRotate(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()`:

``````private fun balanced(node: AVLNode<T>): AVLNode<T> {
return when (node.balanceFactor) {
2 -> {
}
-2 -> {
}
else -> node
}
}
``````

``````private fun balanced(node: AVLNode<T>): AVLNode<T> {
return when (node.balanceFactor) {
2 -> {
if (node.leftChild?.balanceFactor == -1) {
leftRightRotate(node)
} else {
rightRotate(node)
}
}
-2 -> {
if (node.rightChild?.balanceFactor == 1) {
rightLeftRotate(node)
} else {
leftRotate(node)
}
}
else -> node
}
}
``````

### Revisiting insertion

You’ve already done the majority of the work. The remainder is fairly straightforward. Update `insert()` to the following:

``````private fun insert(node: AVLNode<T>?, value: T): AVLNode<T>? {
node ?: return AVLNode(value)
if (value < node.value) {
node.leftChild = insert(node.leftChild, value)
} else {
node.rightChild = insert(node.rightChild, value)
}
val balancedNode = balanced(node)
balancedNode?.height = max(balancedNode?.leftHeight ?: 0, balancedNode?.rightHeight ?: 0) + 1
return balancedNode
}
``````
``````"repeated insertions in sequence" example {
val tree = AVLTree<Int>()

(0..14).forEach {
tree.insert(it)
}

print(tree)
}
``````
``````---Example of repeated insertions in sequence---
┌──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` statement with the following:

``````val balancedNode = balanced(node)
balancedNode.height = max(
balancedNode.leftHeight,
balancedNode.rightHeight
) + 1
return balancedNode
``````
``````val tree = AVLTree<Int>()
tree.insert(15)
tree.insert(10)
tree.insert(16)
tree.insert(18)
print(tree)
tree.remove(10)
print(tree)
``````
``````---Example of removing a value---
┌──18
┌──16
│ └──null
15
└──10

┌──18
16
└──15
``````

## Challenges

Here are three challenges that revolve around AVL trees. Solve these to make sure you understand the concepts.

### Challenge 1: Count the leaves

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

#### Solution 1

A perfectly balanced tree is a tree where all of the leaves are at the same level, and that level is completely filled:

``````fun leafNodes(height: Int): Int {
return 2.0.pow(height).toInt()
}
``````

### Challenge 2: Count the nodes

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

#### Solution 2

Since the tree is perfectly balanced, you can calculate the number of nodes in a perfectly balanced tree of height three using the following:

``````fun nodes(height: Int): Int {
var totalNodes = 0
(0..height).forEach { currentHeight ->
totalNodes += 2.0.pow(currentHeight).toInt()
}
}
``````
``````fun nodes(height: Int): Int {
return 2.0.pow(height + 1).toInt() - 1
}
``````

### Challenge 3: Some refactoring

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

#### Solution 3

First, create the following abstract class:

``````abstract class TraversableBinaryNode<Self :
TraversableBinaryNode<Self, T>, T>(var value: T) {

var leftChild: Self? = null
var rightChild: Self? = null

fun traverseInOrder(visit: Visitor<T>) {
leftChild?.traverseInOrder(visit)
visit(value)
rightChild?.traverseInOrder(visit)
}

fun traversePreOrder(visit: Visitor<T>) {
visit(value)
leftChild?.traversePreOrder(visit)
rightChild?.traversePreOrder(visit)
}

fun traversePostOrder(visit: Visitor<T>) {
leftChild?.traversePostOrder(visit)
rightChild?.traversePostOrder(visit)
visit(value)
}
}
``````
``````"using TraversableBinaryNode" example {
val tree = AVLTree<Int>()
(0..14).forEach {
tree.insert(it)
}
println(tree)
tree.root?.traverseInOrder { println(it) }
}
``````
``````---Example of using TraversableBinaryNode---
┌──14
┌──13
│ └──12
┌──11
│ │ ┌──10
│ └──9
│  └──8
7
│  ┌──6
│ ┌──5
│ │ └──4
└──3
│ ┌──2
└──1
└──0

0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
``````

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