Collection Kit

SplayTree

Tree

A SplayTree is a self-adjusting binary search tree that moves frequently accessed elements closer to the root. This self-adjusting property allows for efficient access to recently accessed elements, making it particularly useful for scenarios where certain elements are accessed more frequently than others.

Import Statement
import { SplayTree } from "collection-kit";

Key Features

  • Self-Adjusting: After every access (search, insert, or delete), the accessed node is moved to the root of the tree, improving access times for frequently used elements.
  • Amortized Efficiency: Provides O(log n) amortized time complexity for search, insertion, and deletion operations, even though individual operations can take O(n) time in the worst case.
  • No Extra Storage: Unlike other balanced trees, SplayTrees do not require additional storage for balancing information.

Common Operations

Splay
Move a specific node to the root of the tree through a series of tree rotations.
Insert
Add a new element to the tree and splay it to the root.
Remove
Delete an element from the tree and splay the last accessed node to the root.
Search
Retrieve an element from the tree and splay it to the root.

Example Code

import { SplayTree } from "collection-kit";

const tree = new SplayTree();
tree.insert(10);
tree.insert(20);
tree.insert(5);

console.log("Search 20:", tree.search(20)); // true, 20 is now root
tree.remove(20);
console.log("Search 20:", tree.search(20)); // false