AVL Tree

Last updated Jan 29, 2023

# What is AVL Tree?

AVL Tree is a type of self-balancing Binary Search Tree. It is named after its inventor Adelson-Velsky and Landis. It’s a Binary Search Tree with the following properties:

It is a BST
The height of the left and right subtrees of any node in the tree can differ by at most 1. The AVL Tree is designed to maintain balance so that the height of the tree remains logarithmic with respect to the number of the nodes in the tree. This allows operations such as insertion, deletion and searching to be performed in O(log n) time.

# Insertion in AVL Tree

https://www.geeksforgeeks.org/insertion-in-an-avl-tree/

Steps to follow for insertion:

Perform standard BST insertion for w.
Rebalance the tree, there four cases to handle:
- Left-Left Case (LL)
- Left Right Case (LR)
- Right-Right Case (LR)
- Right Left Case (RL)

# Left-Left Case

1
2
3
4
5
6
7
8
T1, T2, T3 and T4 are subtrees.
         z                                      y 
        / \                                   /   \
       y   T4      Right Rotate (z)          x      z
      / \          - - - - - - - - ->      /  \    /  \ 
     x   T3                               T1  T2  T3  T4
    / \
  T1   T2

# Left Right Case

1
2
3
4
5
6
7
     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

1
2
3
4
5
6
7
  z                                y
 /  \                            /   \ 
T1   y     Left Rotate(z)       z      x
    /  \   - - - - - - - ->    / \    / \
   T2   x                     T1  T2 T3  T4
       / \
     T3  T4

# Right Left Case

1
2
3
4
5
6
7
   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

# Right rotation

Let’s check the example of right rotating y in the above AVL Tree

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
fun rightRotate(y: Node): Node? {
	var x: Node? = y.left
	var t3 = x?.right

	// rotate
	if (x != null) {
		x.right = x
	}
	y.left = t3
	// update heights
	if (x != null) {
		x.height = max(height(x.left), height(x.right)) + 1
	}
	y.height = max(height(y.left), height(y.right)) + 1
	
	return x
}

# Left rotation

With the case AVL Tree, we need to perform the left rotation on y as following snippet:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
fun leftRotate(y: Node): Node? {
	var x: Node? = y.right
	var t2 = x?.left

	// rotate
	if (x != null) {
		x.left = y
	}
	y.right = t2
	
	// update heights
	if (x != null) {
		x.height = max(height(x.left), height(x.right)) + 1
	}
	y.height = max(height(y.left), height(y.right)) + 1
	
	return x
}

https://www.youtube.com/watch?v=_8qqlVH5NC0&list=PLdo5W4Nhv31bbKJzrsKfMpo_grxuLl8LU&index=62

Full implementation: https://github.com/namtx/dsa-kotlin/commit/c897166735d11e69eac72b42b77931a652cb8f86#diff-a9a0f8f66896171cafd1d2dd5de2d561609bb4a84891055a5bb4370592b5d8d6

# Deletion in an AVL Tree

Steps to perform deletion in an AVL Tree:

Perform normal BST deletion.
The current node must be one of the ancestor of the deleted node. Update the height of the current node.
Check the balance factor of the current node and make suitable rotation same as AVL Tree

Obsidian