ProgramGuruAn AVL Tree is a self-balancing binary search tree where the difference in heights of left and right subtrees for any node is at most one. AVL Trees are named after their inventors, Adelson-Velsky and Landis, and they ensure O(log n) time complexity for search, insertion, and deletion operations.
Consider an AVL tree with the following structure:
30
/ \
20 40
/ \ \
10 25 50
In this AVL tree, the balance factor of each node (difference in heights of left and right subtrees) is within the allowed range of -1 to 1.
AVL Trees have several important properties:
class Node:
def __init__(self, key):
self.left = None
self.right = None
self.val = key
self.height = 1
class AVLTree:
def insert(self, root, key):
if not root:
return Node(key)
elif key < root.val:
root.left = self.insert(root.left, key)
else:
root.right = self.insert(root.right, key)
root.height = 1 + max(self.get_height(root.left), self.get_height(root.right))
balance = self.get_balance(root)
# Left Left
if balance > 1 and key < root.left.val:
return self.right_rotate(root)
# Right Right
if balance < -1 and key > root.right.val:
return self.left_rotate(root)
# Left Right
if balance > 1 and key > root.left.val:
root.left = self.left_rotate(root.left)
return self.right_rotate(root)
# Right Left
if balance < -1 and key < root.right.val:
root.right = self.right_rotate(root.right)
return self.left_rotate(root)
return root
def delete(self, root, key):
if not root:
return root
elif key < root.val:
root.left = self.delete(root.left, key)
elif key > root.val:
root.right = self.delete(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.get_min_value_node(root.right)
root.val = temp.val
root.right = self.delete(root.right, temp.val)
if root is None:
return root
root.height = 1 + max(self.get_height(root.left), self.get_height(root.right))
balance = self.get_balance(root)
# Left Left
if balance > 1 and self.get_balance(root.left) >= 0:
return self.right_rotate(root)
# Left Right
if balance > 1 and self.get_balance(root.left) < 0:
root.left = self.left_rotate(root.left)
return self.right_rotate(root)
# Right Right
if balance < -1 and self.get_balance(root.right) <= 0:
return self.left_rotate(root)
# Right Left
if balance < -1 and self.get_balance(root.right) > 0:
root.right = self.right_rotate(root.right)
return self.left_rotate(root)
return root
def left_rotate(self, z):
y = z.right
T2 = y.left
y.left = z
z.right = T2
z.height = 1 + max(self.get_height(z.left), self.get_height(z.right))
y.height = 1 + max(self.get_height(y.left), self.get_height(y.right))
return y
def right_rotate(self, z):
y = z.left
T3 = y.right
y.right = z
z.left = T3
z.height = 1 + max(self.get_height(z.left), self.get_height(z.right))
y.height = 1 + max(self.get_height(y.left), self.get_height(y.right))
return y
def get_height(self, root):
if not root:
return 0
return root.height
def get_balance(self, root):
if not root:
return 0
return self.get_height(root.left) - self.get_height(root.right)
def get_min_value_node(self, root):
if root is None or root.left is None:
return root
return self.get_min_value_node(root.left)
def pre_order(self, root):
if not root:
return
print("{0} ".format(root.val), end="")
self.pre_order(root.left)
self.pre_order(root.right)
# Example usage:
avl = AVLTree()
root = None
keys = [10, 20, 30, 40, 50, 25]
for key in keys:
root = avl.insert(root, key)
print("Pre-order traversal of the constructed AVL tree is:")
avl.pre_order(root)
This code defines an AVL tree with methods for inserting and deleting nodes, as well as performing rotations to maintain balance.
There are four types of rotations used to maintain the balance of an AVL tree:
AVL Trees are a type of self-balancing binary search tree that ensures efficient searching, insertion, and deletion operations. Understanding their components, properties, and rotation techniques is crucial for implementing balanced trees in various applications.