Implement a Treap Data Structure in JavaScript

This challenge requires you to implement a Treap, a randomized binary search tree that combines the properties of a binary search tree (BST) and a heap. Treaps are useful for maintaining dynamic ordered sets or maps with efficient average-case performance for operations like insertion, deletion, and searching.

Problem Description

Your task is to create a Treap class in JavaScript. A Treap node should store a key (which determines its position in the BST ordering) and a priority (which determines its position in the heap ordering). The priority should be randomly assigned to ensure the tree remains balanced on average.

You need to implement the following core operations for the Treap class:

1. insert(key, value): Inserts a new key-value pair into the treap. If a node with the same key already exists, its value should be updated.
2. search(key): Returns the value associated with a given key, or null if the key is not found.
3. delete(key): Removes the node with the given key from the treap. If the key is not found, the treap remains unchanged.
4. inOrderTraversal(): Returns an array of [key, value] pairs in ascending order of keys.

Key Requirements:

• BST Property: For any node, all keys in its left subtree are smaller than its key, and all keys in its right subtree are larger.
• Heap Property: For any node, its priority is greater than or equal to the priorities of its children (max-heap property).
• Random Priorities: Each node should be assigned a random priority upon insertion. This randomization is crucial for achieving the treap's balanced structure on average.
• Node Structure: Each node in the treap should contain:
  • key: The data to be ordered.
  • value: The associated data.
  • priority: A randomly generated number.
  • left: A pointer to the left child node.
  • right: A pointer to the right child node.

Expected Behavior:

• The insert, search, and delete operations should have an average time complexity of O(log n), where n is the number of nodes in the treap.
• The inOrderTraversal should have a time complexity of O(n).
• The treap should correctly maintain both BST and heap properties after each operation.

Edge Cases to Consider:

• Inserting into an empty treap.
• Inserting a key that already exists.
• Searching for a key that doesn't exist.
• Deleting the root node.
• Deleting a node that doesn't exist.
• Deleting a leaf node.
• Deleting a node with one child.
• Deleting a node with two children.

Examples

Example 1: Basic Operations

const treap = new Treap();

treap.insert(10, 'A');
treap.insert(5, 'B');
treap.insert(15, 'C');
treap.insert(3, 'D');
treap.insert(7, 'E');

console.log(treap.search(7));  // Expected Output: 'E'
console.log(treap.search(20)); // Expected Output: null

treap.delete(5);

console.log(treap.inOrderTraversal());
// Expected Output (order of priorities may vary, but keys and values should be correct):
// [ [ 3, 'D' ], [ 7, 'E' ], [ 10, 'A' ], [ 15, 'C' ] ]

Explanation: The treap is built with several insertions. Searching for existing and non-existing keys works as expected. After deleting key 5, an in-order traversal confirms the remaining elements are present and ordered by key.

Example 2: Duplicate Key Insertion and Deletion of Root

const treap = new Treap();

treap.insert(50, 'RootValue');
treap.insert(30, 'LeftChild');
treap.insert(70, 'RightChild');

// Update value for an existing key
treap.insert(50, 'UpdatedRootValue');
console.log(treap.search(50)); // Expected Output: 'UpdatedRootValue'

// Assume after insertions, 50 becomes the root. We'll simulate deleting it.
treap.delete(50);

console.log(treap.inOrderTraversal());
// Expected Output (structure will depend on priorities, but should contain 30 and 70):
// [ [ 30, 'LeftChild' ], [ 70, 'RightChild' ] ]

Explanation: The first insert(50, 'RootValue') creates the root. The second insert(50, 'UpdatedRootValue') updates the value. The deletion of key 50 (which is assumed to be the root at that point) will rearrange the treap, and the in-order traversal will show the remaining elements correctly ordered.

Example 3: Edge Cases (Empty Treap, Deleting Non-existent)

const treap = new Treap();

// Search in an empty treap
console.log(treap.search(10)); // Expected Output: null

// Delete from an empty treap
treap.delete(20); // No error should occur

// Insert and then try to delete a non-existent key
treap.insert(10, 'Ten');
treap.delete(30); // No error should occur

console.log(treap.inOrderTraversal()); // Expected Output: [ [ 10, 'Ten' ] ]

Explanation: This example tests operations on an empty treap and attempts to delete keys that are not present, ensuring the treap handles these gracefully.

Constraints

• The key will be a number.
• The value can be any JavaScript type.
• The number of nodes in the treap will be between 0 and 10^5.
• Insertion, deletion, and search operations should aim for an average time complexity of O(log n).
• Priorities should be generated using Math.random().

Notes

• You will need to implement helper functions for rotations (left and right rotations) to maintain the heap property after insertions and deletions.
• The insert operation typically involves finding the correct position for the new node as in a BST, and then using rotations to bubble it up (or down) based on its priority until the heap property is satisfied.
• The delete operation often involves finding the node to delete, and then rotating it down until it becomes a leaf, at which point it can be easily removed.
• Consider how to handle null pointers for children of leaf nodes.
• The specific structure of the treap (and thus the exact output of inOrderTraversal for a given set of insertions) will vary due to the random priorities. However, the correctness of the BST and heap properties, and the presence/absence of elements, should be consistent.