Introduction to AVL Trees
Introduction to AVL Trees
An 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.
Simple Example
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.
Properties of AVL Trees
AVL Trees have several important properties:
- Height-Balanced: The heights of the left and right subtrees of any node differ by at most one.
- Binary Search Tree: Follows the binary search tree property where the left subtree contains values less than the node's value, and the right subtree contains values greater than the node's value.
- Rotations: To maintain balance after insertions and deletions, AVL trees perform rotations: single right rotation, single left rotation, double right-left rotation, and double left-right rotation.
- Efficient Operations: Ensures O(log n) time complexity for search, insertion, and deletion operations.
Python Code to Implement an AVL Tree
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.
Types of AVL Tree Rotations
There are four types of rotations used to maintain the balance of an AVL tree:
- Single Right Rotation (LL Rotation): Performed when a node is inserted into the left subtree of the left child of an unbalanced node.
- Single Left Rotation (RR Rotation): Performed when a node is inserted into the right subtree of the right child of an unbalanced node.
- Double Right-Left Rotation (RL Rotation): Performed when a node is inserted into the right subtree of the left child of an unbalanced node.
- Double Left-Right Rotation (LR Rotation): Performed when a node is inserted into the left subtree of the right child of an unbalanced node.
Conclusion
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.