Implementing a Treap Data Structure in JavaScript

Treaps are a fascinating data structure that combine the properties of binary search trees and heaps. They offer a probabilistic guarantee of logarithmic time complexity for common operations like insertion, deletion, and search, making them a powerful alternative to balanced binary search trees like AVL or Red-Black trees. This challenge asks you to implement a Treap data structure in JavaScript.

Problem Description

You are tasked with creating a Treap data structure in JavaScript. A Treap is a binary search tree where each node also has a priority (a random number). The tree is ordered like a binary search tree (left child < parent < right child), but it is also heap-ordered by priority (parent's priority > children's priorities). This heap property is maintained through rotations after insertions and deletions.

Your implementation should include the following methods:

• insert(key, priority): Inserts a new node with the given key and priority into the Treap.
• delete(key): Deletes the node with the given key from the Treap.
• search(key): Searches for a node with the given key and returns the node if found, otherwise returns null.
• rotateRight(): Performs a right rotation on the root node.
• rotateLeft(): Performs a left rotation on the root node.
• toString(): Returns a string representation of the treap (for debugging purposes - can be a simple in-order traversal).

Key Requirements:

• The Treap must maintain the binary search tree property (left < parent < right).
• The Treap must maintain the heap property (parent priority > child priorities).
• Rotations must be performed to maintain both properties after insertions and deletions.
• Handle edge cases gracefully (e.g., empty tree, key not found).

Expected Behavior:

The insert, delete, and search methods should operate with logarithmic time complexity on average. The rotations should correctly rebalance the tree to maintain both the BST and heap properties. The toString() method should provide a readable representation of the tree's contents.

Edge Cases to Consider:

• Empty Treap: Handle insertions and deletions on an empty tree.
• Duplicate Keys: Decide how to handle duplicate keys (e.g., allow them, disallow them, store multiple nodes with the same key). For this challenge, disallowing duplicates is preferred.
• Deleting the Root: Handle the case where the root node is deleted.
• Deleting a Node with No Children: Handle the case where a node to be deleted has no children.
• Deleting a Node with One Child: Handle the case where a node to be deleted has one child.
• Deleting a Node with Two Children: Handle the case where a node to be deleted has two children.

Examples

Example 1:

Input:
  insert(1, 0.8)
  insert(2, 0.5)
  insert(3, 0.9)
Output: (String representation of the treap)
"1 0.8, 2 0.5, 3 0.9" (or similar in-order traversal)
Explanation: The tree is constructed with the given keys and priorities. The heap property dictates the rotations.

Example 2:

Input:
  insert(1, 0.8)
  insert(2, 0.5)
  insert(3, 0.9)
  delete(2)
Output: (String representation of the treap)
"1 0.8, 3 0.9" (or similar in-order traversal)
Explanation: Node with key 2 is deleted, and the tree is rebalanced.

Example 3: (Edge Case - Deleting Root)

Input:
  insert(1, 0.9)
  delete(1)
Output: (String representation of the treap)
"" (empty string, indicating an empty tree)
Explanation: The root node is deleted, resulting in an empty tree.

Constraints

• key must be a number.
• priority must be a number between 0 and 1 (inclusive).
• The number of insertions and deletions will be less than 1000.
• The keys will be unique.
• Performance: The average time complexity of insert, delete, and search should be O(log n), where n is the number of nodes in the Treap.

Notes

• Consider using recursion for the rotation operations.
• The toString() method is primarily for debugging and doesn't need to be highly optimized. A simple in-order traversal is sufficient.
• Think carefully about how to handle the heap property during rotations. The node with the higher priority should always become the parent.
• Remember to update the root of the Treap after rotations.
• You can use Math.random() to generate priorities.
• The structure of a Treap node should include key, priority, left, and right.