Red-Black Tree

Data Structures: Red-Black Tree Data Structure

The Definition of a Red-Black Tree

A Red-Black Tree (RBT) data structure is a self-balancing binary search tree where each node has a color (either red or black) and satisfies certain properties to maintain balance during operations. These properties ensure that the tree remains approximately balanced, resulting in O(log n) time for most operations.

---

---

Instructions for Creating a Red-Black Tree

The main properties of a Red-Black Tree are:

1. Every node is either red or black.
2. The root node is black.
3. All leaves (NIL) are black.
4. If a red node has children then, the children are always black.
5. Every path from a node to its descendant NIL nodes has the same number of black nodes.

Let's go through the steps to create a Red-Black Tree:

1. Define the Node

class RBTNode {
    constructor(key, color, left = null, right = null, parent = null) {
        this.key = key;
        this.color = color;
        this.left = left;
        this.right = right;
        this.parent = parent;
    }
}

2. Define the Red-Black Tree

const RED = 'RED';
const BLACK = 'BLACK';

class RedBlackTree {
    constructor() {
        this.NIL_LEAF = new RBTNode(null, BLACK);
        this.root = this.NIL_LEAF;
    }
}

3. Implement Rotations

• Left Rotation
• Right Rotation

These are essential for maintaining tree properties after insertion and deletion.

4. Insertion

Insertion is a bit involved:

a. Insert the node as you would in a typical binary search tree. b. Color the node red. c. Fix any red-black tree violations.

5. Deletion

Deletion involves:

a. Remove the node as you would in a typical binary search tree. b. Fix any red-black tree violations.

6. Fixing Tree Violations

This is the crux of maintaining the Red-Black Tree properties. The logic can get quite intricate depending on the structure of the tree and where violations occur.

7. Auxiliary Functions

For both insertions and deletions in the Red-Black Tree, you'll often need to check the color of a node, the sibling of a node, the uncle of a node, etc. Implement helper methods to make these tasks easier.

8. Traversals

As with other binary search trees, you can implement in-order, pre-order, and post-order traversals.

Summary

Red-Black Trees are complex because they involve many cases and sub-cases to handle when fixing tree violations. The creation and maintenance of a Red-Black Tree require a deep understanding of its properties and the reasoning behind them. This overview provides a roadmap, but to implement a full-fledged Red-Black Tree, you'll need a comprehensive guide or tutorial, as covering every detail and edge case is beyond the scope of this brief rundown.

---

Code Example

Here's a basic outline:

class Node {
  constructor(data, color, parent, left, right) {
    this.data = data;
    this.color = color;
    this.parent = parent;
    this.left = left;
    this.right = right;
  }
}

class RedBlackTree {
  constructor() {
    this.NIL_LEAF = new Node(null, 'black');
    this.root = this.NIL_LEAF;
  }

  insert(value) {
    let newNode = new Node(value, 'red', null, this.NIL_LEAF, this.NIL_LEAF);
    this.insertNode(this.root, newNode);
    this.fixInsert(newNode);
  }

  insertNode(root, node) {
    if (root === this.NIL_LEAF) {
      this.root = node;
      return;
    }

    if (node.data < root.data) {
      if (root.left === this.NIL_LEAF) {
        root.left = node;
        node.parent = root;
      } else {
        this.insertNode(root.left, node);
      }
    } else {
      if (root.right === this.NIL_LEAF) {
        root.right = node;
        node.parent = root;
      } else {
        this.insertNode(root.right, node);
      }
    }
  }

  rotateLeft(x) {
    let y = x.right;
    x.right = y.left;

    if (y.left !== this.NIL_LEAF) {
      y.left.parent = x;
    }

    y.parent = x.parent;

    if (x.parent === null) {
      this.root = y;
    } else if (x === x.parent.left) {
      x.parent.left = y;
    } else {
      x.parent.right = y;
    }

    y.left = x;
    x.parent = y;
  }

  rotateRight(x) {
    // Similar to rotateLeft but mirrored
  }

  fixInsert(k) {
    // Fix the rb tree
    let u;
    while (k.parent.color === 'red') {
      if (k.parent === k.parent.parent.right) {
        u = k.parent.parent.left;
        if (u.color === 'red') {
          u.color = 'black';
          k.parent.color = 'black';
          k.parent.parent.color = 'red';
          k = k.parent.parent;
        } else {
          if (k === k.parent.left) {
            k = k.parent;
            this.rotateRight(k);
          }
          k.parent.color = 'black';
          k.parent.parent.color = 'red';
          this.rotateLeft(k.parent.parent);
        }
      } else {
        // Mirror the previous case
      }
    }
    this.root.color = 'black';
  }
}

let tree = new RedBlackTree();
tree.insert(5);
tree.insert(3);
tree.insert(7);

---

Note

This code provides a basic structure for a Red-Black Tree in JavaScript, focusing on insertion. You would need to add methods for deletion and searching, and further enhance the fix methods to cover all edge cases for a complete implementation.

---

Complexity

A Red-Black Tree is a type of self-balancing binary search tree where each node has an extra bit for denoting the color of the node, either red or black. Here are the time and space complexities for common operations on a Red-Black Tree:

Operation	Average Time Complexity	Worst Time Complexity	Space Complexity
Insertion	O(log n)	O(log n)	O(n)
Deletion	O(log n)	O(log n)	O(n)
Search	O(log n)	O(log n)	O(1)
Minimum/Maximum	O(log n)	O(log n)	O(1)
Successor/Predecessor	O(log n)	O(log n)	O(1)

Notes:

1. Insertion: After inserting a node in a Red-Black Tree, we might need to perform certain rotations and color changes to maintain the Red-Black properties, but this still falls within ( O(\log n) ) time.

2. Deletion: Deleting a node may again require rotations and color changes, but the operations are bounded by ( O(\log n) ).

3. Search: As with all balanced binary search trees, searching for a value is ( O(\log n) ).

4. Minimum/Maximum: Although in a regular binary search tree you could get the minimum and maximum values in ( O(\log n) ) average time (by following the leftmost or rightmost paths), the balancing of the Red-Black Tree ensures the height is always logarithmic with respect to the number of nodes.

5. Successor/Predecessor: Finding the next larger (successor) or next smaller (predecessor) node for a given node is ( O(\log n) ).

6. Space Complexity: Each node requires space for the data, pointers to left and right children, and the color bit. The total space for ( n ) nodes is ( O(n) ).

These complexities highlight the efficiency and advantage of using Red-Black Trees in scenarios where balanced operations are required, such as in certain map and set implementations in the standard libraries of many programming languages.