Chapter 13 – AVL Trees and Red-Black Trees

Chapter 13: AVL Trees and Red-Black Trees

---

In this chapter, we will dive into AVL Trees and Red-Black Trees, two important types of self-balancing binary search trees. These trees ensure that the height of the tree remains balanced, providing improved efficiency for operations such as insertion, deletion, and searching.

Self-balancing trees like AVL Trees and Red-Black Trees guarantee that the operations on the tree have a time complexity of O(log n), even in the worst-case scenario.

Let’s explore them in detail!

---

What are AVL Trees?

An AVL Tree is a type of self-balancing binary search tree where the difference between the heights of the left and right subtrees of any node (known as the balance factor) is at most 1.

The AVL Tree is named after its inventors Adelson-Velsky and Landis, who introduced the concept in 1962.

Key Properties of AVL Trees:

1. Balance Factor: For every node in an AVL tree, the balance factor must be either -1, 0, or +1.

   • Balance Factor = Height of Left Subtree – Height of Right Subtree
   • If the balance factor is not within this range, the tree is considered unbalanced and requires rotation to rebalance.

2. Rotations: To maintain the balance of an AVL tree, we use rotations when an insertion or deletion operation causes the tree to become unbalanced.

   • Single Rotations: Right or Left rotation.
   • Double Rotations: A combination of right and left rotations.

---

Example of an AVL Tree

Consider inserting the elements 10, 20, and 30 into an empty AVL Tree.

1. Step 1: Insert 10:

   10
   

2. Step 2: Insert 20:

     10
       \
        20
   

3. Step 3: Insert 30. This causes the tree to become unbalanced because the balance factor of node 10 becomes -2 (left height = 0, right height = 2).

   To rebalance the tree, we perform a left rotation at node 10:

   Before rotation:

     10
       \
        20
          \
           30
   

   After rotation:

       20
      /  \
     10   30
   

Now, the tree is balanced again.

---

Rotations in AVL Trees

To maintain the balance factor of AVL trees, we perform rotations. There are four types of rotations used to rebalance an AVL tree:

1. Left Rotation (LL Rotation)

A left rotation is performed when a node becomes unbalanced due to the right subtree being taller than the left subtree. This happens when a new node is inserted into the right subtree of the right child.

Example:
Before left rotation:

     10
       \
        20
          \
           30

After left rotation:

     20
    /  \
   10   30

2. Right Rotation (RR Rotation)

A right rotation is performed when a node becomes unbalanced due to the left subtree being taller than the right subtree. This happens when a new node is inserted into the left subtree of the left child.

Example:
Before right rotation:

       30
      /
    20
   /
  10

After right rotation:

     20
    /  \
   10   30

3. Left-Right Rotation (LR Rotation)

A left-right rotation is a combination of left and right rotations. It is performed when a new node is inserted into the right subtree of the left child.

Example:
Before LR rotation:

       30
      /
    10
      \
       20

First, perform a left rotation on the left child (10), then perform a right rotation on the root (30):

After LR rotation:

      20
     /  \
    10   30

4. Right-Left Rotation (RL Rotation)

A right-left rotation is a combination of right and left rotations. It is performed when a new node is inserted into the left subtree of the right child.

Example:
Before RL rotation:

     10
       \
        30
       /
     20

First, perform a right rotation on the right child (30), then perform a left rotation on the root (10):

After RL rotation:

      20
     /  \
   10    30

---

What are Red-Black Trees?

A Red-Black Tree is another type of self-balancing binary search tree. It is similar to an AVL tree, but it has a more relaxed balancing criterion, which makes it faster for insertion and deletion operations. The key feature of a Red-Black Tree is the use of colors to maintain balance.

Key Properties of Red-Black Trees:

1. Each node is colored either red or black.
2. The root node must always be black.
3. No two consecutive red nodes can appear on the same path (i.e., a red node cannot have a red parent or red child).
4. Every path from a node to its descendant null nodes must contain the same number of black nodes.
5. The longest path from the root to a leaf is no more than twice as long as the shortest path (this ensures that the tree is balanced).

---

Example of a Red-Black Tree

Consider inserting the elements 10, 20, and 30 into an empty Red-Black Tree.

1. Step 1: Insert 10 (the root node is always black).

   10 (black)
   

2. Step 2: Insert 20. Since it is greater than 10, it is inserted as the right child and colored red:

     10 (black)
         \
          20 (red)
   

3. Step 3: Insert 30. Since this creates a violation of two consecutive red nodes (20 and 30), we perform a left rotation at node 10 and recolor:

Before rotation:

     10 (black)
         \
          20 (red)
             \
              30 (red)

After rotation and recoloring:

     20 (black)
    /  \
  10 (red) 30 (red)

Now, the tree satisfies all the Red-Black Tree properties.

---

Rotations in Red-Black Trees

Similar to AVL trees, Red-Black Trees also use rotations to restore balance when a violation occurs. The rotations are the same as those in AVL trees: left rotation, right rotation, left-right rotation, and right-left rotation.

---

Comparison: AVL Trees vs. Red-Black Trees

Feature	AVL Trees	Red-Black Trees
Balancing Method	Strictly balanced	Loosely balanced
Height Difference	At most 1	No more than twice the shortest path
Rebalancing	Frequent rotations	Fewer rotations
Efficiency in Insertion/Deletion	Slower in large trees	Faster for insertion/deletion
Search Efficiency	Slightly better	Slightly worse than AVL trees

---

Applications of AVL and Red-Black Trees

1. Database Indexing: Both AVL and Red-Black Trees are widely used in databases for maintaining ordered records efficiently.
2. Memory Management: Red-Black Trees are often used in memory allocators (e.g., Linux kernel uses Red-Black Trees).
3. Networking: AVL and Red-Black Trees are useful in routing algorithms and network management systems.

---

Conclusion

Both AVL Trees and Red-Black Trees are powerful self-balancing binary search trees, but they are suited for different applications depending on the frequency of operations and the balance requirements. Understanding the subtle differences between these trees allows you to make informed decisions when implementing them in real-world scenarios.

In the next chapter, we will discuss Tree Traversal Methods, which are essential for interacting with the data stored in trees.

Don’t forget to check out digilearn.cloud for free access to this book and other learning materials provided by Emancipation Edutech Private Limited!

---