In this article let’s understand the concept of the AVL Tree in Python; popularly known as the self-balancing binary search tree. The tree is named in honor of its inventors G.M.Adelson-Velsky and E.M.Landis. To understand the AVL tree thoroughly one should have the prerequisite knowledge of the binary search tree.
The essential advantage of using this data structure is that it takes O(log N) time to perform any operation in an average case and the worst case. Whether it be insertion, deletion, or search operation, the time complexity remains the same for all functions.
Also read: Binary Search Tree Implementation in Python
Balance Factor of AVL Tree in Python
The structure of the AVL Tree is similar to a standard binary tree, but the AVL tree has one additional variable known as the balance factor in its structure. This variable is assigned to every node of the tree. The balance factor is calculated by subtracting the height of its right subtree from the height of its left subtree.
Balance Factor = Height(Left Sub-tree) – Height(Right sub-tree)
The Implementation of the function to calculate the Balance Factor in Python is as follows:
The value of the balance factor itself describes the tree. It is either 1, 0, or -1 in the case of a height-balanced tree. If any node of the tree has any other value, then it is an unbalanced tree and needs to be rebalanced.
- If the balance factor = 1, then the tree is known as the Left-Heavy Tree, which means the tree has a left subtree one level higher than its right subtree.
- If the balance factor = 0, then the tree is said to be perfectly balanced, which means the left subtree is equal to the right subtree.
- If the balance factor = -1, then the tree is known as the Right-Heavy Tree, which means the tree has a left subtree one level lower than its right subtree.
Searching for node in an AVL tree in Python
The searching operation in AVL Tree is exactly the same as that in a binary search tree. Since search operations don’t modify the structure of the tree in any possible way, there is no need for any kind of special provisions. The time complexity for the operation remains O(Logn)
Inserting a node in an AVL tree in Python
The insertion operation is also the same as that in a binary search tree, but the insertion is followed by one extra step in AVL tree in Python. If after insertion of the new node in the tree, the balance factor of the tree changes, then an additional step known as rotation is required to restore the balance of the tree.
The new node is always inserted as a leaf node, being a leaf node the balance factor of the new node is equal to zero. The position of the new node is decided by comparing the value of the new node with the value of the root node recursively. If the value of the new node is lesser than the value of the root node, then move the node to the left subtree, or else move the node to the right subtree.
The balance factor of all the nodes that lie in the path from the root node to the newly inserted node. Consider the following examples for better understanding.
Now, after the insertion of a node, there are four ways to rebalance the tree depending on the position of the newly inserted node. The four types of rotation are
- LL Rotation: when a node is inserted to the left side of the left subtree of the critical node.
- RR Rotation: when a node is inserted to the right side of the right subtree of the critical node.
- LR Rotation: when a node is inserted to the right side of the left subtree of the critical node.
- RL Rotation: when a node is inserted to the left side of the right subtree of the critical node.
LL Rotation
Consider the tree given in the Figure below. Tree (a) is an AVL tree in Python. In tree (b), a new node is inserted in the left sub-tree of the left sub-tree of the critical node A (node A is the critical node because it is the closest ancestor whose balance factor is not -1, 0, or 1), so we apply LL rotation as shown in the tree (c).
Tree (a) is an AVL tree. In tree (b), a new node is inserted in the left sub-tree of the left sub-tree of the critical node A (node A is the critical node because it is the closest ancestor whose balance factor is not -1, 0, or 1), so we apply LL rotation as shown in the tree (c). While rotation, node B becomes the root, with T1, and A as its left and right child. T2, and T3, become the left and right sub-trees of A.
RR Rotation
Consider the tree given in the Figure below.
Tree (a) is an AVL tree in Python. In tree (b), a new node is inserted in the right sub-tree of the right sub-tree of the critical node A (node A is the critical node because it is the closest ancestor whose balance factor is not -1, 0, or 1), so we apply RR rotation as shown in the tree (c).
Note that the new node has now become a part of tree T3. While rotation, node B becomes the root, with A and T3 as its left and right child. T1 and T2 become the left and right sub-trees of A.
LR Rotation
Consider the tree given in the Figure below. Tree (a) is an AVL tree in Python. In tree (b), a new node is inserted in the right sub-tree of the left sub-tree of the critical node A (node A is the critical node because it is the closest ancestor whose balance factor is not -1, 0, or 1), so we apply LR rotation as shown in the tree (c). Note that the new node has now become a part of tree T2. While rotation, node C becomes the root, with B and A as its left and right children. Node B has T1 and T2 as its left and right sub-trees and T3 and T4 become the left and right sub-trees of node A.
RL Rotation
Consider the tree given in the Figure below. Tree (a) is an AVL tree in Python. In tree (b), a new node is inserted in the left sub-tree of the right sub-tree of the critical node A (node A is the critical node because it is the closest ancestor whose balance factor is not -1, 0, or 1), so we apply RL rotation as shown in the tree (c). Note that the new node has now become a part of tree T2. While rotation, node C becomes the root, with A and B as its left and right children. Node A has T1 and T2 as its left and right sub-trees and T3 and T4 become the left and right sub-trees of node B.
Deleting a node from an AVL tree in Python
Deleting a node from an AVL tree in Python is similar to the deletion of a node from a binary search tree. But in the case AVL tree, one step is added which is rebalancing the tree after the deletion of the node. Before deleting the node, we first check the position of the node that is to be deleted.
Also read: Decision Trees in Python – Step-By-Step Implementation
If the node is a leaf node (node which has no children), then we simply delete the node. In the case of the node having a single child, we store the value of the child node in the node that is to be deleted and then delete the child node. And lastly, if the node has two children, then we find a successor of the node which does not have further children and store the value of this successor node into the node that is to be deleted, then delete the successor node.
Python Functions
Define the class and initialize the nodes
class avl_Node(object):
def __init__(self, value):
self.value = value
self.leaf = None
self.root = None
self.height = 1
Define a function to calculate height and Balance Factor.
def avl_Height(self, root):
if not root:
return 0
return root.height
def avl_BalanceFactor(self, root):
//base case for leaf nodes
if not root:
return 0
//implementing the above mentioned formula
return self.avl_Height(root.l) - self.avl_Height(root.r)
Define a function to find an empty node
def avl_MinValue(self, root):
if root is None or root.left is None:
return root
return self.avl_MinValue(root.left)
Define a function to traverse the tree in a preorder way.
def preOrder(self, root):
if not root:
return
print("{0} ".format(root.value), end=" ")
self.preOrder(root.left)
self.preOrder(root.right)
Define functions for rotations
def leftRotate(self, b):
a = b.right
T2 = a.left
a.left = b
b.right = T2
b.height = 1 + max(self.avl_Height(b.left),
self.avl_Height(b.right))
a.height = 1 + max(self.avl_Height(a.left),
self.avl_Height(a.right))
return a
def rightRotate(self, b):
a = b.left
T3 = a.right
a.right = z
b.left = T3
b.height = 1 + max(self.avl_Height(b.left),
self.avl_Height(b.right))
a.height = 1 + max(self.avl_Height(a.left),
self.avl_Height(a.right))
return a
Define a function for inserting a node in AVL tree in Python
def insert_node(self, root, value):
if not root:
return avl_Node(value)
elif value < root.value:
root.left = self.insert_node(root.left, value)
else:
root.right = self.insert_node(root.right, value)
root.height = 1 + max(self.avl_Height(root.left),
self.avl_Height(root.right))
# Update the balance factor and balance the tree
balanceFactor = self.avl_BalanceFactor(root)
if balanceFactor > 1:
if value < root.left.value:
return self.rightRotate(root)
else:
root.left = self.leftRotate(root.left)
return self.rightRotate(root)
if balanceFactor < -1:
if value > root.right.value:
return self.leftRotate(root)
else:
root.right = self.rightRotate(root.right)
return self.leftRotate(root)
return root
Define a function for deleting a node from the AVL tree in Python
def delete_node(self, root, value):
# Find the node to be deleted and remove it
if not root:
return root
elif value < root.value:
root.left = self.delete_node(root.left, value)
elif value > root.value:
root.right = self.delete_node(root.right, value)
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.avl_MinValue(root.right)
root.value = temp.key
root.right = self.delete_node(root.right, temp.value)
if root is None:
return root
# Update the balance factor of nodes
root.height = 1 + max(self.avl_Height(root.left), self.avl_Height(root.right))
balanceFactor = self.avl_BalanceFactor(root)
# Balance the tree
if balanceFactor > 1:
if self.avl_BalanceFactor(root.left) >= 0:
return self.rightRotate(root)
else:
root.left = self.leftRotate(root.left)
return self.rightRotate(root)
if balanceFactor < -1:
if self.avl_BalanceFactor(root.right) <= 0:
return self.leftRotate(root)
else:
root.right = self.rightRotate(root.right)
return self.leftRotate(root)
return root
Complete Code for AVL Tree in Python
class avl_Node(object):
def __init__(self, value):
self.value = value
self.left = None
self.right = None
self.height = 1
class AVLTree(object):
def insert_node(self, root, value):
if not root:
return avl_Node(value)
elif value < root.value:
root.left = self.insert_node(root.left, value)
else:
root.right = self.insert_node(root.right, value)
root.height = 1 + max(self.avl_Height(root.left),
self.avl_Height(root.right))
# Update the balance factor and balance the tree
balanceFactor = self.avl_BalanceFactor(root)
if balanceFactor > 1:
if value < root.left.value:
return self.rightRotate(root)
else:
root.left = self.leftRotate(root.left)
return self.rightRotate(root)
if balanceFactor < -1:
if value > root.right.value:
return self.leftRotate(root)
else:
root.right = self.rightRotate(root.right)
return self.leftRotate(root)
return root
def avl_Height(self, root):
if not root:
return 0
return root.height
# Get balance factore of the node
def avl_BalanceFactor(self, root):
if not root:
return 0
return self.avl_Height(root.left) - self.avl_Height(root.right)
def avl_MinValue(self, root):
if root is None or root.left is None:
return root
return self.avl_MinValue(root.left)
def preOrder(self, root):
if not root:
return
print("{0} ".format(root.value), end=" ")
self.preOrder(root.left)
self.preOrder(root.right)
def leftRotate(self, b):
a = b.right
T2 = a.left
a.left = b
b.right = T2
b.height = 1 + max(self.avl_Height(b.left),
self.avl_Height(b.right))
a.height = 1 + max(self.avl_Height(a.left),
self.avl_Height(a.right))
return a
def rightRotate(self, b):
a = b.left
T3 = a.right
a.right = b
b.left = T3
b.height = 1 + max(self.avl_Height(b.left),
self.avl_Height(b.right))
a.height = 1 + max(self.avl_Height(a.left),
self.avl_Height(a.right))
return a
def delete_node(self, root, value):
# Find the node to be deleted and remove it
if not root:
return root
elif value < root.value:
root.left = self.delete_node(root.left, value)
elif value > root.value:
root.right = self.delete_node(root.right, value)
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.avl_MinValue(root.right)
root.value = temp.key
root.right = self.delete_node(root.right, temp.value)
if root is None:
return root
# Update the balance factor of nodes
root.height = 1 + max(self.avl_Height(root.left), self.avl_Height(root.right))
balanceFactor = self.avl_BalanceFactor(root)
# Balance the tree
if balanceFactor > 1:
if self.avl_BalanceFactor(root.left) >= 0:
return self.rightRotate(root)
else:
root.left = self.leftRotate(root.left)
return self.rightRotate(root)
if balanceFactor < -1:
if self.avl_BalanceFactor(root.right) <= 0:
return self.leftRotate(root)
else:
root.right = self.rightRotate(root.right)
return self.leftRotate(root)
return root
Tree = AVLTree()
root = None
root = Tree.insert_node(root,40)
root = Tree.insert_node(root,60)
root = Tree.insert_node(root,50)
root = Tree.insert_node(root,70)
print("PREORDER")
Tree.preOrder(root)
Output:
PREORDER
50 40 60 70
Summary:
AVL Tree is one of the efficient implementations of the binary search tree. This article covers both theoretical knowledges as well as the practical implementation of the AVL Tree.
To understand more about binary search trees click here for reference. Also check out abstract syntax trees in Python.