Red-Black Tree Implementation in JavaScript

Red-black trees are self-balancing binary search trees that guarantee logarithmic time complexity for search, insertion, and deletion operations. This is achieved by maintaining a set of properties that ensure the tree remains relatively balanced, making them a crucial data structure for efficient data management. Your challenge is to implement a Red-Black Tree in JavaScript, including its core operations.

Problem Description

You are tasked with creating a RedBlackTree class in JavaScript that adheres to the rules of a red-black tree. This implementation should support insertion and deletion of nodes while maintaining the red-black properties.

Key Requirements:

1. Node Structure: Each node in the tree must have:

   • key: The value of the node.
   • color: Either 'RED' or 'BLACK'.
   • left: Pointer to the left child node.
   • right: Pointer to the right child node.
   • parent: Pointer to the parent node.
   • A sentinel node (often NIL or null) should represent null children and its color should be 'BLACK'.

2. Red-Black Tree Properties: The tree must always satisfy the following properties:

   • Property 1 (Color): Every node is either red or black.
   • Property 2 (Root): The root of the tree is always black.
   • Property 3 (Leaf): All leaves (NIL nodes) are black.
   • Property 4 (Red Children): If a node is red, then both its children are black.
   • Property 5 (Black Height): For each node, all simple paths from the node to descendant leaves contain the same number of black nodes.

3. Operations:

   • insert(key): Inserts a new node with the given key into the tree. After insertion, the tree must be rebalanced to maintain red-black properties.
   • delete(key): Deletes the node with the given key from the tree. After deletion, the tree must be rebalanced.
   • search(key): Returns the node with the given key if it exists, otherwise returns null.
   • inOrderTraversal(): Returns an array of keys in the tree in ascending order.

Expected Behavior:

• Insertion of duplicate keys should either be ignored or handled gracefully (e.g., by not creating a new node). For this challenge, let's assume duplicate keys are ignored.
• Deletion of a non-existent key should do nothing.
• The NIL node should be a shared instance for all leaf nodes.

Edge Cases:

• Inserting into an empty tree.
• Deleting the root node.
• Deleting a node with one or two children.
• Cases that require various rotations and color changes to restore red-black properties.

Examples

Example 1: Basic Insertion and Traversal

Input:
const tree = new RedBlackTree();
tree.insert(10);
tree.insert(20);
tree.insert(30);
tree.insert(15);
tree.insert(25);

Output of tree.inOrderTraversal():
[10, 15, 20, 25, 30]

Explanation:
The keys are inserted and the tree rebalances. The in-order traversal correctly reflects the sorted order of the keys.

Example 2: Deletion

Input:
const tree = new RedBlackTree();
tree.insert(10);
tree.insert(20);
tree.insert(30);
tree.insert(5);
tree.insert(15);
tree.insert(25);
tree.insert(35);

// Initial in-order: [5, 10, 15, 20, 25, 30, 35]

tree.delete(20); // Deleting a node with two children

Output of tree.inOrderTraversal() after deleting 20:
[5, 10, 15, 25, 30, 35]

Explanation:
Node 20 is deleted. The tree rebalances, and the in-order traversal still produces the sorted sequence of the remaining keys.

Example 3: Complex Rebalancing Scenario

Input:
const tree = new RedBlackTree();
tree.insert(7);
tree.insert(3);
tree.insert(18);
tree.insert(10);
tree.insert(22);
tree.insert(8);
tree.insert(11);
tree.insert(26);
tree.insert(2);
tree.insert(6);
tree.insert(13);

// Initial in-order: [2, 3, 6, 7, 8, 10, 11, 13, 18, 22, 26]

tree.delete(18); // This deletion might trigger complex rebalancing

Output of tree.inOrderTraversal() after deleting 18:
[2, 3, 6, 7, 8, 10, 11, 13, 22, 26]

Explanation:
Deleting node 18 requires several rebalancing operations (rotations and color changes) to maintain the red-black properties. The in-order traversal should remain consistent.

Constraints

• The key values will be integers.
• The number of operations (insertions/deletions) can be up to 1000.
• The tree should have a maximum depth that is O(log N), where N is the number of nodes.
• The implementation should be in plain JavaScript, without relying on external libraries for the tree structure itself.

Notes

• You'll need helper functions for rotations (left and right) and fixing the tree properties after insertion and deletion.
• Consider how you will represent the NIL node. A common approach is to use a singleton NIL object.
• The delete operation is generally more complex than insertion and requires careful handling of different cases based on the color of the node to be deleted and its successor.
• Think about the invariant that needs to be maintained at each step of rebalancing.