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.