Implementing a Red-Black Tree in JavaScript

Red-Black Trees are self-balancing binary search trees that guarantee logarithmic time complexity for search, insertion, and deletion operations. Implementing one from scratch is a challenging but rewarding exercise in data structures and algorithms, providing a deep understanding of tree balancing techniques. This challenge asks you to implement a Red-Black Tree in JavaScript, focusing on core operations and maintaining the tree's properties.

Problem Description

You are tasked with creating a Red-Black Tree data structure in JavaScript. The tree should support the following operations:

• insert(key, value): Inserts a new node with the given key and value into the tree. The key must be comparable (e.g., numbers or strings).
• search(key): Searches for a node with the given key and returns its value if found. Returns undefined if the key is not present.
• delete(key): Deletes the node with the given key from the tree.
• toArray(): Returns an array representation of the tree's keys in ascending order (in-order traversal).

The Red-Black Tree must adhere to the following properties:

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

You are responsible for implementing the balancing logic (rotations and color flips) to maintain these properties after insertion and deletion. Assume that null or undefined represents a NIL leaf node.

Examples

Example 1:

Input:
  insert(10, "A")
  insert(5, "B")
  insert(15, "C")
  search(5)
  toArray()
Output:
  "B"
  [5, 10, 15]
Explanation:
  The tree is initially empty. Inserting 10, 5, and 15 creates a basic binary search tree.  Searching for 5 returns "B".  The toArray() method performs an in-order traversal, resulting in [5, 10, 15].

Example 2:

Input:
  insert(10, "A")
  insert(7, "B")
  insert(13, "C")
  insert(11, "D")
  delete(10)
  toArray()
Output:
  [7, 11, 13]
Explanation:
  The initial insertions create a tree. Deleting the root (10) requires rebalancing, which may involve rotations and color changes. The final in-order traversal yields [7, 11, 13].

Example 3: (Edge Case - Duplicate Keys)

Input:
  insert(5, "A")
  insert(5, "B")
  search(5)
  toArray()
Output:
  "B"
  [5]
Explanation:
  The tree should handle duplicate keys.  The second insertion with key 5 should overwrite the existing value.  The toArray() method should return only the unique key.

Constraints

• Key Type: Keys must be comparable using standard JavaScript comparison operators (<, >, ==, etc.).
• Value Type: Values can be of any JavaScript data type.
• Number of Operations: The number of insert, search, and delete operations can vary significantly (up to 10,000).
• Tree Size: The maximum number of nodes in the tree will be 1000.
• Performance: All operations (insert, search, delete, toArray) should have an average time complexity of O(log n), where n is the number of nodes in the tree. While strict performance testing isn't required, the implementation should be reasonably efficient.

Notes

• You'll need to define a Node class or object to represent nodes in the tree, including properties for key, value, color (red or black), left, and right children.
• Consider using helper functions for rotations (left and right) and color flips to keep the main insert and delete functions more readable.
• The delete operation is the most complex and requires careful handling of different cases to maintain the Red-Black Tree properties. Pay close attention to the various scenarios that can arise during deletion.
• The toArray() method should perform an in-order traversal to return the keys in sorted order.
• Start with the insert operation and thoroughly test it before moving on to delete. A correctly implemented insert is crucial for a functional Red-Black Tree.
• Remember to handle edge cases such as inserting into an empty tree, deleting a non-existent key, and dealing with duplicate keys.