Avl Tree
Example: Let's create an AVL Tree and perform some operations on it.
# Node class definition
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
self.height = 1
# AVL Tree class definition
class AVLTree:
def __init__(self):
self.root = None
# Get the height of a node
def get_height(self, node):
if node is None:
return 0
return node.height
# Get the balance factor of a node
def get_balance(self, node):
if node is None:
return 0
return self.get_height(node.left) - self.get_height(node.right)
# Perform left rotation
def left_rotate(self, node):
y = node.right
T2 = y.left
y.left = node
node.right = T2
# Update heights
node.height = 1 + max(self.get_height(node.left), self.get_height(node.right))
y.height = 1 + max(self.get_height(y.left), self.get_height(y.right))
return y
# Perform right rotation
def right_rotate(self, node):
x = node.left
T2 = x.right
x.right = node
node.left = T2
# Update heights
node.height = 1 + max(self.get_height(node.left), self.get_height(node.right))
x.height = 1 + max(self.get_height(x.left), self.get_height(x.right))
return x
# Perform insertion
def insert(self, node, value):
if node is None:
return Node(value)
elif value < node.value:
node.left = self.insert(node.left, value)
else:
node.right = self.insert(node.right, value)
# Update the height of the ancestor node
node.height = 1 + max(self.get_height(node.left), self.get_height(node.right))
# Check balance factor and perform rotations if necessary
balance = self.get_balance(node)
# Left-Left case
if balance > 1 and value < node.left.value:
return self.right_rotate(node)
# Right-Right case
if balance < -1 and value > node.right.value:
return self.left_rotate(node)
# Left-Right case
if balance > 1 and value > node.left.value:
node.left = self.left_rotate(node.left)
return self.right_rotate(node)
# Right-Left case
if balance < -1 and value < node.right.value:
node.right = self.right_rotate(node.right)
return self.left_rotate(node)
return node
# Perform in-order traversal
def inorder_traversal(self, node):
if node is not None:
self.inorder_traversal(node.left)
print(node.value, end=" ")
self.inorder_traversal(node.right)
# Create an instance of AVL Tree
avl_tree = AVLTree()
# Insert nodes into AVL Tree
avl_tree.root = avl_tree.insert(avl_tree.root, 10)
avl_tree.root = avl_tree.insert(avl_tree.root, 20)
avl_tree.root = avl_tree.insert(avl_tree.root, 30)
avl_tree.root = avl_tree.insert(avl_tree.root, 40)
avl_tree.root = avl_tree.insert(avl_tree.root, 50)
avl_tree.root = avl_tree.insert(avl_tree.root, 25)
# Perform in-order traversal
avl_tree.inorder_traversal(avl_tree.root)
# Output: 10 20 25 30 40 50
In this example, we define a Node
class that represents a node in the AVL Tree. Each node has a value, left child, right child, and height. We also define an AVLTree
class to perform AVL Tree operations.
The AVL Tree operations include:
get_height
: Computes the height of a node. The height of a node is the maximum height between its left and right subtrees plus one.get_balance
: Computes the balance factor of a node. The balance factor is the difference between the heights of its left and right subtrees.left_rotate
: Performs a left rotation to balance the tree. It updates the heights of the rotated nodes.right_rotate
: Performs a right rotation to balance the tree. It updates the heights of the rotated nodes.insert
: Inserts a new node into the AVL Tree while maintaining the height balance property. It performs necessary rotations based on the balance factor to ensure the tree remains balanced.inorder_traversal
: Performs an in-order traversal of the AVL Tree and prints the values of the nodes in sorted order.
Let's solve a question using the concept of AVL Tree. The question is "Balanced Binary Tree," which requires determining whether a given binary tree is balanced.
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
class Solution:
def is_balanced(self, root):
def check_height(node):
if node is None:
return 0
left_height = check_height(node.left)
right_height = check_height(node.right)
if left_height == -1 or right_height == -1 or abs(left_height - right_height) > 1:
return -1
return max(left_height, right_height) + 1
return check_height(root) != -1
# Create an instance of Solution
solution = Solution()
# Create a binary tree
root = Node(3)
root.left = Node(9)
root.right = Node(20)
root.right.left = Node(15)
root.right.right = Node(7)
# Check if the binary tree is balanced
print(solution.is_balanced(root))
# Output: True
In this solution, we define a Node
class to represent a node in the binary tree. We also define a Solution
class that contains the is_balanced
method to check if a given binary tree is balanced.
The is_balanced
method uses a helper function check_height
to recursively check the height balance of each node in the binary tree. It returns the height of the subtree rooted at the current node. If the left or right subtree is unbalanced (difference in heights > 1) or any subtree has a height of -1 (indicating unbalance), it returns -1. Otherwise, it returns the maximum height of the left and right subtrees plus one.
The time complexity of the solution is O(n), where n is the number of nodes in the binary tree, as we visit each node once. The space complexity is O(h), where h is the height of the binary tree, as the recursive calls consume stack space. In the worst case, when the tree is skewed, the height is O(n), resulting in O(n) space complexity.