Implementing a Splay Tree in JavaScript

Splay trees are self-balancing binary search trees that move recently accessed nodes closer to the root. This improves performance for frequently accessed elements, making them a valuable data structure for scenarios where access patterns are predictable. Your task is to implement a splay tree in JavaScript, including insertion, deletion, and splaying operations.

Problem Description

You are required to implement a Splay Tree data structure in JavaScript. The Splay Tree should support the following operations:

• insert(key, value): Inserts a new node with the given key and value into the tree. If a node with the same key already exists, its value should be updated. After insertion, the newly inserted (or updated) node should be splayed to the root.
• delete(key): Deletes the node with the given key from the tree. If the node doesn't exist, the function should return false. After deletion, the parent of the deleted node (or the node that replaced it) should be splayed to the root. If the tree is empty, return false.
• search(key): Searches for the node with the given key and returns its value. If the key is not found, return undefined. After the search, the accessed node should be splayed to the root.
• getMin(): Returns the minimum key in the tree. If the tree is empty, return undefined. Splay the minimum node to the root.
• getMax(): Returns the maximum key in the tree. If the tree is empty, return undefined. Splay the maximum node to the root.
• isEmpty(): Returns true if the tree is empty, false otherwise.

The core of the challenge lies in implementing the splaying operation correctly. Splaying involves a series of rotations (zig, zig-zig, zig-zog) to move a node to the root. You must handle all possible rotation scenarios.

Examples

Example 1:

Input:
insert(3, "apple")
insert(1, "banana")
insert(2, "cherry")

Output: (Tree structure after operations - conceptually)
      3 (apple)
     /  \
    2 (cherry) 1 (banana)

Explanation: The tree is built and each insertion splayed the inserted node to the root.

Example 2:

Input:
insert(3, "apple")
delete(2)
search(1)

Output: (Tree structure after operations - conceptually)
      1 (banana)
       \
        3 (apple)

Explanation: Node 2 is deleted. Then, searching for 1 splayed it to the root.

Example 3:

Input:
insert(10, "a")
insert(20, "b")
insert(30, "c")
getMax()
delete(20)
getMin()

Output: 30, 10

Explanation: getMax() returns 30 and splays it to the root. delete(20) removes 20 and splays the replacement node. getMin() returns 10 and splays it to the root.

Constraints

• The keys will be integers.
• The values can be any JavaScript data type.
• The number of insertion, deletion, and search operations will be between 1 and 1000.
• The key values will be within the range of -1000 to 1000.
• Performance: Insertion, deletion, search, getMin, and getMax should have an average time complexity of O(log n), where n is the number of nodes in the tree. Splaying itself is O(1) amortized.

Notes

• Consider using a Node class to represent each node in the tree, with properties for key, value, left, right, and parent.
• The splaying operation is the most complex part of the implementation. Carefully consider the different rotation cases (zig, zig-zig, zig-zog) and ensure they are handled correctly.
• Remember to update the parent pointers correctly during rotations.
• Thoroughly test your implementation with various input sequences, including edge cases like inserting duplicate keys, deleting non-existent keys, and operating on an empty tree.
• The tree structure is not required to be visually represented in the output. The key is that the operations are performed correctly and the splaying is implemented as expected. You can represent the tree structure conceptually in your explanation.