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:

• 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/

• 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 }