The Project | About Us | Contribute | Donations | License

HOME

Introduction to AVL Trees

AVL Trees are a type of self-balancing binary search tree (BST). Named after their inventors Adelson-Velsky and Landis, AVL trees maintain their balance through rotations, ensuring that the height difference between the left and right subtrees of any node is no more than one. This balance guarantees O(log n) time complexity for search, insertion, and deletion operations.

Key Concepts

Balance Factor: The balance factor of a node in an AVL tree is the difference between the heights of its left and right subtrees. It can be calculated as: \[ \text{Balance Factor} = \text{Height of Left Subtree} - \text{Height of Right Subtree} \] The balance factor should be -1, 0, or 1 for the tree to be balanced.
Rotations: To maintain balance, AVL trees use four types of rotations:
- Right Rotation (RR)
- Left Rotation (LL)
- Left-Right Rotation (LR)
- Right-Left Rotation (RL)

Rotations Explained

Right Rotation (RR)

A right rotation is performed when a node's left subtree is taller than its right subtree by more than one level.

Example:

Before Rotation:

After Right Rotation:

    y
   / \
  x   z

Left Rotation (LL)

A left rotation is performed when a node's right subtree is taller than its left subtree by more than one level.

Example:

Before Rotation:

After Left Rotation:

    y
   / \
  x   z

Left-Right Rotation (LR)

A left-right rotation is a combination of a left rotation followed by a right rotation.

Example:

Before Rotation:

After Left-Right Rotation:

    y
   / \
  x   z

Right-Left Rotation (RL)

A right-left rotation is a combination of a right rotation followed by a left rotation.

Example:

Before Rotation:

  x
   \
    z
   /
  y

After Right-Left Rotation:

    y
   / \
  x   z

AVL Tree Implementation

Node Structure

class AVLNode:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
        self.height = 1

AVL Tree Class

class AVLTree:
    def insert(self, root, key):
        # Step 1: Perform normal BST insertion
        if not root:
            return AVLNode(key)
        elif key < root.key:
            root.left = self.insert(root.left, key)
        else:
            root.right = self.insert(root.right, key)

        # Step 2: Update the height of the ancestor node
        root.height = 1 + max(self.get_height(root.left), self.get_height(root.right))

        # Step 3: Get the balance factor
        balance = self.get_balance(root)

        # Step 4: If the node is unbalanced, then try the 4 cases of rotations

        # Left Left Case
        if balance > 1 and key < root.left.key:
            return self.right_rotate(root)

        # Right Right Case
        if balance < -1 and key > root.right.key:
            return self.left_rotate(root)

        # Left Right Case
        if balance > 1 and key > root.left.key:
            root.left = self.left_rotate(root.left)
            return self.right_rotate(root)

        # Right Left Case
        if balance < -1 and key < root.right.key:
            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

        # Perform rotation
        y.left = z
        z.right = T2

        # Update heights
        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 the new root
        return y

    def right_rotate(self, z):
        y = z.left
        T3 = y.right

        # Perform rotation
        y.right = z
        z.left = T3

        # Update heights
        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 the new root
        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 pre_order(self, root):
        if not root:
            return
        print("{0} ".format(root.key), end="")
        self.pre_order(root.left)
        self.pre_order(root.right)

Example Usage

avl = AVLTree()
root = None

# Insert nodes
nodes = [10, 20, 30, 40, 50, 25]
for node in nodes:
    root = avl.insert(root, node)

# Pre-order traversal
print("Pre-order traversal of the constructed AVL tree is:")
avl.pre_order(root)

Explanation

Insertion: The insert function performs a standard BST insertion and then updates the height of the ancestor node. It checks the balance factor and performs the necessary rotations to maintain the AVL property.
Rotations: The left_rotate and right_rotate functions perform the necessary rotations to balance the tree.
Height and Balance Factor: The get_height and get_balance functions are utility functions to get the height of a node and the balance factor, respectively.
Traversal: The pre_order function is used to print the tree in pre-order traversal.

Exercises with AVL Trees

Exercise 1: Insertions

Task: Insert the following sequence of numbers into an AVL tree and show the tree structure after each insertion: [15, 10, 20, 8, 12, 25, 30, 16].

Solution:

Insert 15:
```
15
```
Insert 10:
```
  15
 /
10
```
Insert 20:
```
  15
 /  
   10  20
```
Insert 8:
```
  15
 /  
   10  20
```

/ 8


5. Insert 12:

 15
/  
   10  20

/
8 12


6. Insert 25:

 15
/  
   10  20

/ \
8 12 25


7. Insert 30:

 15
/  
   10  20

/ \
8 12 25
30


8. Insert 16 (requires balancing):

 15
/  
   10  25

/ \ /
8 12 20 30 / 16

Exercise 2: Deletions

Task: Delete the node with key 20 from the AVL tree constructed in Exercise 1 and show the tree structure after deletion.

Solution:

Delete 20:
```
  15
 /  
   10  25
```

/ \ /
8 12 16 30

Common Mistakes and Tips

Ignoring Balance Factor: Always check the balance factor after insertion or deletion to ensure the tree remains balanced.
Incorrect Rotations: Ensure that rotations are performed correctly. A common mistake is to mix up left and right rotations.
Updating Heights: After performing rotations, always update the heights of the affected nodes.

Conclusion

In this section, we learned about AVL trees, a type of self-balancing binary search tree. We covered the key concepts, including balance factors and rotations, and provided a detailed implementation in Python. We also included practical exercises to reinforce the concepts. Understanding AVL trees is crucial for ensuring efficient search, insertion, and deletion operations in various applications.

AVL Trees

Introduction to AVL Trees

Key Concepts

Rotations Explained

Right Rotation (RR)

Left Rotation (LL)

Left-Right Rotation (LR)

Right-Left Rotation (RL)

AVL Tree Implementation

Node Structure

AVL Tree Class

Example Usage

Explanation

Exercises with AVL Trees

Exercise 1: Insertions

Exercise 2: Deletions

Common Mistakes and Tips

Conclusion

Data Structures Course

Module 1: Introduction to Data Structures

Module 2: Lists

Module 3: Stacks

Module 4: Queues

Module 5: Trees

Module 6: Graphs

Module 7: Conclusions and Additional Resources