AVL Tree Implementation in Python

1. Introduction

An AVL Tree (named after its inventors Adelson-Velsky and Landis) is a balanced binary search tree. In an AVL Tree, the height of the two child subtrees for every node differs by at most one, ensuring O(log n) time complexity for search, insert, and delete operations.

2. Implementation Steps

1. Define a Node class which will contain data, a height, a left child, and a right child.

2. Implement the AVLTree class which initializes the root node.

3. Implement methods for tree rotations to maintain tree balance: leftRotate, rightRotate, leftRightRotate, and rightLeftRotate.

4. Provide methods to insert, delete, and display the tree using inorder traversal.

3. Implementation in Python

class Node:
    def __init__(self, data):
        self.data = data  # Holds the data for the node
        self.height = 1  # Default height for a new node is 1
        self.left = None  # Pointer to the left child node
        self.right = None  # Pointer to the right child node
class AVLTree:
    def __init__(self):
        self.root = None  # Initialize the root of the tree as None
    def _height(self, node):
        if not node:
            return 0
        return node.height
    def _balance(self, node):
        if not node:
            return 0
        return self._height(node.left) - self._height(node.right)
    def leftRotate(self, z):
        y = z.right
        T2 = y.left
        y.left = z
        z.right = T2
        z.height = 1 + max(self._height(z.left), self._height(z.right))
        y.height = 1 + max(self._height(y.left), self._height(y.right))
        return y
    def rightRotate(self, y):
        z = y.left
        T3 = z.right
        z.right = y
        y.left = T3
        y.height = 1 + max(self._height(y.left), self._height(y.right))
        z.height = 1 + max(self._height(z.left), self._height(z.right))
        return z
    def insert(self, root, data):
        if not root:
            return Node(data)
        elif data < root.data:
            root.left = self.insert(root.left, data)
        else:
            root.right = self.insert(root.right, data)
        root.height = 1 + max(self._height(root.left), self._height(root.right))
        balance = self._balance(root)
        if balance > 1:
            if data < root.left.data:
                return self.rightRotate(root)
            else:
                root.left = self.leftRotate(root.left)
                return self.rightRotate(root)
        if balance < -1:
            if data > root.right.data:
                return self.leftRotate(root)
            else:
                root.right = self.rightRotate(root.right)
                return self.leftRotate(root)
        return root
    def inorder(self, root):
        result = []
        if root:
            result += self.inorder(root.left)
            result.append(root.data)
            result += self.inorder(root.right)
        return result
# Test the AVLTree class
avl = AVLTree()
root = None
data_list = [33, 44, 20, 55, 10]
for data in data_list:
    root = avl.insert(root, data)
print("Inorder traversal:", avl.inorder(root))

Output:

Inorder traversal: [10, 20, 33, 44, 55]

Explanation:

1. The Node class holds the data, its height, and pointers to its left and right children.

2. In the AVLTree class, auxiliary methods _height and _balance provide the height of a node and the balance factor, respectively.

3. The leftRotate and rightRotate methods are used to maintain the AVL tree property by performing rotations. In some cases, a combination of rotations is needed (leftRightRotate and rightLeftRotate), but in this basic example, we only illustrate the primary two.

4. The insert method adds a node and ensures that the tree remains balanced by checking the balance factor and rotating if necessary.

5. Finally, the inorder method provides an inorder traversal of the tree, which, for an AVL, should be a sorted sequence.

6. In the test, we create an AVL tree and insert multiple values into it.

Note: This is a basic implementation of AVL trees. Additional methods like delete and more comprehensive handling for different cases can be added for a complete implementation.

Related Data Structures in Python


Comments

Post a Comment