In the previous post, I talked about the **binary search tree**. With efficiency in search, insert, delete,... binary search tree can be done in logrithmic time (${\Theta(logn)}$) in the average case. In this article, I will talk about AVL tree, which is a type of binary search tree, ensuring that in all cases, the time complexity of the above operations is the same ${\Theta(logn)}$.

## 1. AVL tree

An AVL tree is a balanced binary search tree in which the heights of the left and right subtrees differ by at most 1 ${(1)}$. In the process of performing operations on the tree that make the tree unbalanced, we need to rebalance the tree to ensure the nature of the tree ${(1)}$.

## 2. Tree height assessment

The height of the tree

${h}$ = max{ left subtree height, right subtree height } + 1

The heights of the nodes are numbered as shown above.

With the property ${(1)}$, the worst case of an AVL tree occurs when the right subtree is 1 unit taller than the left subtree for all nodes (or vice versa).

For ${N{_h}}$ is the smallest number of nodes in a tree of height ${h}$.

With the diagram above, we have

${N{_ {O(1)}} = O(1)}$ và ${N{_ h} = 1 + N{_ {h-1}} + N{_{h-2}}}$

### 2.1. First approach

The above expression reminds us of the fibonacci sequence, we have ${N{_h} > F{_h}}$ với ${F{_h}}$ is the ${h^{th}}$ fibonacci. We have ${F{_h} = \frac{\gamma^h}{\sqrt{5}}}$, with ${\gamma = 1.61803398875...}$, (golden ratio).

With ${N{_h} = n}$ (the number of nodes in the tree).

${ n > \frac{\gamma^h}{\sqrt{5}} => h < log{_\gamma}n => h < 1.440log{_2}n }$.

### 2.2. Second approach

${=> N{_ h} = 1 + N{_ {h-1}} + N{_{h-2}}}$

${=> N{_ h} > 1 + 2N{_{h-2}}}$

${=> N{_ h} > 2N{_{h-2}}}$

${=> h < 2log{_2}n}$

Therefore, ${h = O(logn)}$.

## 3. AVL tree operations

### 3.1. Node insertion, node deletion, search node

The above operations in an AVL tree are the same as in a binary search tree, with ${h = O(logn)}$. The difference in node insertion and deletion is that after performing those operations, we need to do an extra step of tree balancing to ensure the integrity of the tree ${(1)}$.

### 3.2. Tree balancing activities

The following example demonstrates the need for tree rebalancing

Suppose we have the following tree

We want to insert ${23}$ into the tree, perform the insertion as in a binary search tree. After inserting, we see the property ${(1)}$ violated. We need to rebalance the tree to get

#### 3.2.1. Balance factor

In a binary tree, the balance factor is defined as follows:

${BF(x)}$ = height of left subtree if ${x}$ ${-}$ height of right subtree of ${x}$.

Thus, in the AVL tree, we have ${BF(x) \in \\{-1, 0, 1\\} }$.

#### 3.2.2. Tree balancing operations

When the BF of a certain node has a value that is not in the above set of values, then we need to re-balancing the tree. We have two basic types of balancing operations of AVL trees: **right rotation** and **left rotation**

### 3.3. Tree balancing in specific cases

#### 3.3.1. Left left case

This case occurs when a node has BF = 2 and its left subtree has BF = 1. Then, we only need 1 **right rotation** at the node to be considered, then the tree is balanced.

#### 3.3.2. Left right case

This case occurs when a node has BF = 2 and its left subtree has BF = -1. Then, we need to do the following 2 steps in turn

**Left rotation**left subtree.**Right rotation**the node to be considered.

#### 3.3.3. Right right case

This case occurs when a node has BF = -2 and its right subtree has BF = -1. Then, we only need 1 **left rotation** at the node to be considered, then the tree is balanced.

#### 3.3.4. Right left case

This case occurs when a node has BF = -2 and its left subtree has BF = 1. Then, we need to do the following 2 steps in turn

**Right rotation**right subtree.**Left rotation**the node to be considered.

## 4. Python code for tree balancing activities

`# ---------------------------METHOD TO HELP BALANCE THE TREE---------------------------`

# y x

# / \ Right Rotation / \

# x T3 - - - - - - - > T1 y

# / \ < - - - - - - - / \

# T1 T2 Left Rotation T2 T3

# ---------------------------BALANCE THE TREE IN PARTICULAR CASES---------------------------

# -----Left Left Case

# z y

# / \ / \

# y T4 Right Rotate (z) x z

# / \ - - - - - - - - -> / \ / \

# x T3 T1 T2 T3 T4

# / \

# T1 T2

# -----Left Right Case

# z z x

# / \ / \ / \

# y T4 Left Rotate (y) x T4 Right Rotate(z) y z

# / \ - - - - - - - - -> / \ - - - - - - - -> / \ / \

# T1 x y T3 T1 T2 T3 T4

# / \ / \

# T2 T3 T1 T2

# -----Right Right Case

# z y

# / \ / \

# T1 y Left Rotate(z) z x

# / \ - - - - - - - -> / \ / \

# T2 x T1 T2 T3 T4

# / \

# T3 T4

# -----Right Left Case

# z z x

# / \ / \ / \

# T1 y Right Rotate (y) T1 x Left Rotate(z) z y

# / \ - - - - - - - - -> / \ - - - - - - - -> / \ / \

# x T4 T2 y T1 T2 T3 T4

# / \ / \

# T2 T3 T3 T4

class AVLNode:

def __init__(self, val):

self.left = None

self.right = None

self.val = val

self.height = 1

class AVLTree:

def insert(self, root, key):

# perform bst

if not root:

return AVLNode(key)

if root.val < key:

root.right = self.insert(root.right, key)

if root.val > key:

root.left = self.insert(root.left, key)

# update the height of the ancestor node

root.height = 1 + max(self.get_height(root.left),

self.get_height(root.right))

# get balance factor

balance = self.get_balance(root)

# perform balance

# left left

if balance > 1 and key < root.left.val:

return self.right_rotate(root)

# right right

if balance < -1 and key > root.right.val:

return self.left_rotate(root)

# left right

if balance > 1 and key > root.left.val:

root.left = self.left_rotate(root.left)

return self.right_rotate(root)

# right left

if balance < -1 and key < root.left.val:

root.right = self.right_rotate(root.right)

return self.left_rotate(root)

return root

def left_rotate(self, x):

y = x.right

T2 = y.left

y.left = x

x.right = T2

x.height = 1 + max(self.get_height(x.left), self.get_height(x.right))

y.height = 1 + max(self.get_height(y.left), self.get_height(y.right))

return y

def right_rotate(self, y):

x = y.left

T2 = x.right

x.right = y

y.left = T2

x.height = 1 + max(self.get_height(x.left), self.get_height(x.right))

y.height = 1 + max(self.get_height(y.left), self.get_height(y.right))

return x

def get_height(self, root):

if not root:

return 0

return root.height

def get_balance(self, root):

if not root:

return 0

return self.get_height(root.left) - self.get_height(root.right)

def inorder(self, root):

if root is not None:

self.inorder(root.left)

print(root.val)

self.inorder(root.right)

avl_tree = AVLTree()

root = None

root = avl_tree.insert(root, 20)

root = avl_tree.insert(root, 10)

root = avl_tree.insert(root, 30)

root = avl_tree.insert(root, 40)

root = avl_tree.insert(root, 50)

root = avl_tree.insert(root, 5)

root = avl_tree.insert(root, 15)

root = avl_tree.insert(root, 25)

root = avl_tree.insert(root, 55)

avl_tree.inorder(root)

## 5. AVL sorting algorithm

Given an array of ${n}$ elements, the AVL sorting algorithm is done through the following steps

- Perform inserts ${n}$ elements into AVL tree. Each inserted operation costs ${O(logn)}$ time (as in a binary search tree). We need to insert ${n}$ elements, so the time complexity of the process will be ${O(nlogn)}$.
- We perform inorder traversal (as in a binary search tree). This causes us to go through all the elements, so the time complexity of the process is ${O(n)}$.

Therefore, the total time complexity is ${O(n + nlogn) = O(nlogn)}$. However, because of the extra ${O(n)}$ makes this AVL sorting algorithm inefficient and less practical than the other **sorting algorithms** that I have listed.

## 6. Additional notes

Readers can find visualizations for AVL tree operations at **USFCA website**.