Obsidian

Search

Search IconIcon to open search

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:

# Insertion in AVL Tree

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

Steps to follow for insertion:

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