Hone logo
Hone
Problems

Implement Splay Tree in JavaScript

This challenge asks you to implement a Splay Tree data structure in JavaScript. Splay trees are a type of self-adjusting binary search tree that automatically move frequently accessed nodes to the root, improving performance for common operations. Understanding and implementing splay trees is a great way to deepen your knowledge of tree structures and their dynamic optimization techniques.

Problem Description

You are tasked with creating a JavaScript class SplayTree that supports the following operations:

  • insert(value): Inserts a new value into the tree. After insertion, the newly inserted node should be splayed to the root.
  • search(value): Searches for a given value in the tree. If the value is found, the corresponding node should be splayed to the root. If not found, the last accessed node (where the search terminated) should be splayed to the root.
  • delete(value): Deletes a given value from the tree. After deletion, the new root of the tree should be the inorder successor (or predecessor if successor doesn't exist) of the deleted node. If the tree becomes empty, the root should be null.
  • inorder(): Returns an array of all values in the tree in inorder traversal.

Key Requirements:

  1. Node Structure: Each node in the tree should store a value, a left child, and a right child.
  2. Splaying Logic: Implement the splay operation correctly for zig, zig-zig, and zig-zag rotations. The splay operation should happen after each insert, search, and delete operation.
  3. Root Management: The SplayTree class should maintain a reference to its root node.
  4. Correctness: All BST properties must be maintained throughout the operations.

Expected Behavior:

  • insert: New nodes are placed according to BST rules, and then the new node is splayed to the root.
  • search: If the value exists, the node containing that value becomes the root. If it doesn't exist, the node that would be its parent (or the last node visited) becomes the root.
  • delete: The node is removed, and its inorder successor (or predecessor) takes its place. Then, this successor/predecessor (which is now the root of its subtree) is splayed to become the new root of the entire tree.
  • inorder: Returns values in ascending order.

Edge Cases:

  • Inserting into an empty tree.
  • Searching for a value that doesn't exist in an empty tree.
  • Deleting the root node.
  • Deleting a node with only one child.
  • Deleting a leaf node.
  • Tree becoming empty after deletion.

Examples

Example 1: Insertion and Splaying

Input:
tree = new SplayTree();
tree.insert(10); // [10]
tree.insert(5);  // [5, 10]
tree.insert(15); // [5, 10, 15]
tree.insert(3);  // [3, 5, 10, 15]
tree.insert(7);  // [3, 5, 7, 10, 15]

Output (after inserting 7):
Root value: 7
Inorder traversal: [3, 5, 7, 10, 15]

Explanation:
1. Insert 10: root is 10.
2. Insert 5: 5 is left of 10. Splay 5. Tree: 5 (root) -> 10.
3. Insert 15: 15 is right of 10. Splay 15. Tree: 10 (root) -> 5, 15.
4. Insert 3: 3 is left of 5. Splay 3. Tree: 3 (root) -> 5 -> 10 -> 15.
5. Insert 7: 7 is right of 5. Splay 7. Tree: 7 (root) -> 3, 5 -> 10, 15.
The node with value 7 becomes the root.

Example 2: Search and Splaying

Input:
tree = new SplayTree();
tree.insert(50);
tree.insert(30);
tree.insert(70);
tree.insert(20);
tree.insert(40);
tree.insert(60);
tree.insert(80);
// Current root is likely 50 or one of its children depending on insertion order.
// Let's assume after insertions and splays, the tree is: 40 (root) -> 30 -> 20, 50 -> 70 -> 60, 80

found = tree.search(20); // Search for 20

Output:
Root value: 20
Inorder traversal: [20, 30, 40, 50, 60, 70, 80]

Explanation:
The search for 20 will find it. The splay operation will then move the node with value 20 to the root.

Example 3: Deletion and Splaying

Input:
tree = new SplayTree();
tree.insert(50);
tree.insert(30);
tree.insert(70);
tree.insert(20);
tree.insert(40);
tree.insert(60);
tree.insert(80);
// After insertions, assume root is 50 or a similar balanced structure.
// Let's assume the tree is: 40 (root) -> 30 -> 20, 50 -> 70 -> 60, 80

tree.delete(40); // Delete the current root

Output:
Root value: 50
Inorder traversal: [20, 30, 50, 60, 70, 80]

Explanation:
1. The value 40 is deleted.
2. Its inorder successor is 50.
3. The node with 50 becomes the new root of the overall tree.
4. The splay operation ensures the new root (50) is correctly positioned.

Example 4: Deleting a Non-existent Node

Input:
tree = new SplayTree();
tree.insert(10);
tree.insert(5);
tree.insert(15);

tree.search(7); // Last accessed node would be 5

tree.delete(7); // Attempt to delete a non-existent node

Output:
Root value: 5
Inorder traversal: [5, 10, 15]

Explanation:
The search for 7 would have splayed 5 to the root.
The delete operation for 7 does nothing as it's not found. The tree remains unchanged with 5 at the root.

Constraints

  • The number of operations (insert, search, delete) will be between 1 and 1000.
  • Node values will be integers between -10^9 and 10^9.
  • The implementation should aim for an average time complexity of O(log N) per operation, where N is the number of nodes in the tree. Worst-case can be O(N) without proper splaying, but the goal is to achieve amortized O(log N).

Notes

  • You will need to implement the core BST insert, search, and delete logic first, and then layer the splay operation on top of these.
  • The splay operation typically involves a series of rotations (zig, zig-zig, zig-zag) to bring the accessed node to the root.
  • Consider how to handle the parent pointer for rotations. If you choose not to use explicit parent pointers, you'll need to pass parent nodes down through recursive calls or manage them during the rotation process.
  • For deletion, the logic for finding the inorder successor and merging subtrees after removal is crucial.
  • A robust inorder() traversal function is necessary to verify the correctness of your tree structure.
  • Helper functions for rotations will be extremely useful.
Loading editor...
javascript