AVL Tree

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 §

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 §

     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

Right rotation §

Let’s check the example of right rotating y in the above Right Left Case

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 Left Right Case, we need to perform the left rotation on y as following snippet:

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 Insertion in AVL Tree