Updated March 14, 2023

## Introduction to AVL Tree Rotation

The following article provides an outline for AVL Tree Rotation. AVL Tree is a Binary Search Tree and is also known as a self-balancing tree in which each node is connected to a balance factor which is calculated by subtracting the heights of the right subtree from that of the left subtree of a particular node. The tree is defined as a balanced AVL tree when the balance factor of each node is between -1 and 1. On the other hand, when the balance factor is less than -1 or greater than 1, then the tree is known as an unbalanced tree and needs to be balanced to get the perfect AVL tree.

- If the balance factor obtained is -1 for a particular node, it defines that the node’s left subtree is one level higher than the right subtree.
- If the balance factor obtained is 0 for a particular node, it defines that the node’s left subtree and right subtree are at an equal level.
- If the balance factor obtained is 1 for a particular node, it defines that the left subtree is one level lower than the node’s right subtree.

**Balanced AVL Tree Example:**

### Rotation Operations in AVL Tree

Rotation is performed in AVL Tree to turn the unbalanced tree into a balanced tree by performing various rotation operations.

In general, there are four types of Rotations in the AVL tree:

- Left Rotation
- Right Rotation
- Left-Right Rotation
- Right-Left Rotation

The first two rotations are known as single rotations, and the next two are known as double rotations.

#### 1. Left Rotation (LL)

When a node is inserted into the left subtree or deleted from the left subtree, the AVL tree becomes unbalanced, and we need to balance it using LL rotation. This LL rotation is also known as clockwise rotation applied on edge, which has the highest balance factor.

#### 2. Right Rotation(RR)

When a node gets inserted into the right subtree or deleted from the right subtree, the AVL tree becomes unbalanced, and we need to balance it by rotating the node in the anti-clockwise direction. This rotation technique is applied on the edge of the node which is having the highest balance factor.

#### 3. Left-Right Rotation(LR)

Left-Right Rotation is the combination of RR rotation and LL rotation. At first, RR rotation is performed on the subtree then, LL rotation is performed on the part of the full tree from inserted node to the first node

#### 4. Right-Left Rotation(RL)

Right-left Rotation is the combination of LL rotation and RR rotation. In this case, the first LL rotation is performed on the subtree where the change has been made; then, the RR rotation is performed on the part of the full tree from the inserted node to the top of the tree, that is, the first node.

### Example of AVL Tree Rotation

Given below is the example of AVL Tree Rotation:

**AVL tree in Python.**

**Code:**

`import sys`

# Create a node

class TreeNode(object):

def __init__(self, key):

self.key = key

self.left = None

self.right = None

self.height = 1

class AVLTree(object):

# Function to insert a node

def insert_node(self, root, key):

# Insert the node at the correct location

if not root:

return TreeNode(key)

elif key < root.key:

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

else:

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

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

self.getHeight(root.right))

# Balance the tree by updating the balance factor

balanceFactor = self.getBalance(root)

if balanceFactor > 1:

if key < root.left.key:

return self.rightRotate(root)

else:

root.left = self.leftRotate(root.left)

return self.rightRotate(root)

if balanceFactor < -1:

if key > root.right.key:

return self.leftRotate(root)

else:

root.right = self.rightRotate(root.right)

return self.leftRotate(root)

return root

#Function to delete a node

def delete_node(self, root, key):

# Remove the deleted node

if not root:

return root

elif key < root.key:

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

elif key > root.key:

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

else:

if root.left is None:

temp = root.right

root = None

return temp

elif root.right is None:

temp=root.left

root = None

return temp

temp = self.getMinValueNode(root.right)

root.key = temp.key

root.right = self.delete_node(root.right,

temp.key)

if root is None:

return root

# Update the nodes balance factor

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

self.getHeight(root.right))

balanceFactor = self.getBalance(root)

# Balance the tree

if balanceFactor > 1:

if self.getBalance(root.left) >= 0:

return self.rightRotate(root)

else:

root.left = self.leftRotate(root.left)

return self.rightRotate(root)

if balanceFactor < -1:

if self.getBalance(root.right) <= 0:

return self.leftRotate(root)

else:

root.right = self.rightRotate(root.right)

return self.leftRotate(root)

return root

# Function to perform tree’s left rotation

def leftRotate(self, z):

y = z.right

T2 = y.left

y.left = z

z.right = T2

z.height = 1 + max(self.getHeight(z.left),

self.getHeight(z.right))

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

self.getHeight(y.right))

return y

# Function to perform tree’s right rotation

def rightRotate(self, z):

y = z.left

T3 = y.right

y.right = z

z.left = T3

z.height = 1 + max(self.getHeight(z.left),

self.getHeight(z.right))

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

self.getHeight(y.right))

return y

# Get the height of the node

def getHeight(self, root):

if not root:

return 0

return root.height

# Get the node balance factor

def getBalance(self, root):

if not root:

return 0

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

def getMinValueNode(self, root):

if root is None or root.left is None:

return root

return self.getMinValueNode(root.left)

def preOrder(self, root):

if not root:

return

print("{0} ".format(root.key), end="")

self.preOrder(root.left)

self.preOrder(root.right)

# Print the AVL tree

def printHelper(self, currPtr, indent, last):

if currPtr != None:

sys.stdout.write(indent)

if last:

sys.stdout.write("R----")

indent += " "

else:

sys.stdout.write("L----")

indent += "| "

print(currPtr.key)

self.printHelper(currPtr.left, indent, False)

self.printHelper(currPtr.right, indent, True)

myTree = AVLTree()

root = None

nums = [33, 13, 52, 9, 21, 61, 8, 11]
for num in nums:

root = myTree.insert_node(root, num)

myTree.printHelper(root, "", True)

key = 13

root = myTree.delete_node(root, key)

print("After Deletion: ")

myTree.printHelper(root, "", True)

**Output:**

### Conclusion

AVL tree is a self-balancing binary tree in which each node is connected to a balance factor. This tree is named in honor of the inventors GM Adelson-Velsky and EM Landis in 1962. The balance factor is calculated by subtracting the heights of the right subtree from the left subtree of a particular node. There are four types of Rotations in the AVL tree: Left rotation, Right rotation, Left-Right rotation, Right-Left rotation.

### Recommended Articles

This is a guide to AVL Tree Rotation. Here we discuss the introduction, rotation operations in AVL tree and example, respectively. You may also have a look at the following articles to learn more –