Fast Splay Tree

Common errors

• TypeError: SplayTree is not a constructor

  cause Attempting to instantiate `SplayTree` after an incorrect CommonJS `require()` or a named import when it's a default export.
  fix Ensure you are importing `SplayTree` correctly. For ESM, use `import SplayTree from 'splaytree';`. For CommonJS in some contexts, you may need `const SplayTree = require('splaytree').default;`.

• RangeError: Maximum call stack size exceeded

  cause This error often indicates an infinite recursion, commonly stemming from an incorrectly implemented custom comparator function that does not consistently provide a strict weak ordering, leading to an unbalanced or malformed tree.
  fix Carefully review and test your custom comparator function. Ensure it handles all edge cases, returns 0 for equality, a negative number for 'a < b', and a positive number for 'a > b', and that its logic is consistent for `comparator(a,b)` and `comparator(b,a)`.

Warnings

• gotcha Incorrectly implemented comparator function can lead to a malformed tree or unpredictable search results and performance issues.
  Fix: Thoroughly test your custom comparator function (function(a,b)) to ensure it returns 0 for equality, <0 if a<b, and >0 if a>b. Verify behavior with `comparator(a,b)` and `comparator(b,a)`.
• breaking The package requires Node.js version 18.20 or 20 and above. Older Node.js versions are not supported.
  Fix: Upgrade your Node.js environment to a compatible version (18.20+ or 20+). Check the `engines` field in `package.json` for precise requirements.
• gotcha The `insert()` method allows duplicate keys, creating a new node for each insertion. The `add()` method, however, will not insert a new node if the key is already present in the tree.
  Fix: Choose `insert()` if you need to store multiple items with the same key, or `add()` if you require keys to be unique within the tree.
• gotcha Recent patch versions (v3.2.1-v3.2.3) addressed broken `.cjs` and `.mjs` links in the distribution. While resolved, ensure your bundler or environment correctly handles dual CommonJS/ESM packages to avoid module resolution errors.
  Fix: Prefer modern `import` statements over `require()` where possible. If using `require()`, be aware that you might need to access the default export via `.default` (e.g., `require('splaytree').default`) depending on your Node.js version and configuration.

Install

• npm install splaytree npm
• yarn add splaytree yarn
• pnpm add splaytree pnpm

Imports

• SplayTree
  wrong:

  import { SplayTree } from 'splaytree';
  const SplayTree = require('splaytree');

  correct:

  import SplayTree from 'splaytree';

  Since v3.x, the package provides both ESM and CJS bundles. For ESM, `import SplayTree from 'splaytree'` is the direct default export. For CommonJS, you might need `const SplayTree = require('splaytree').default;` in some environments, as `require('splaytree')` might resolve to the module namespace object.
• Node

  import type { Node } from 'splaytree';

  For TypeScript, import the `Node` type to correctly type the return values from methods like `insert()`, `find()`, `minNode()`, etc., which return a Node instance or null.

Quickstart

This example demonstrates creating a SplayTree, inserting and adding elements, retrieving keys and values, finding specific nodes, and checking the min/max keys, showcasing basic tree operations.

import SplayTree from "splaytree";

const tree = new SplayTree();

// Insert various key-value pairs
tree.insert(5, "apple");
tree.insert(-10, "banana");
tree.add(0, "cherry"); // Using add to prevent duplicates if 0 already existed
tree.insert(33, "date");
tree.insert(2, "elderberry");
tree.insert(5, "fig"); // Demonstrates duplicate key insertion with 'insert'

console.log("Keys in sorted order:", tree.keys());
console.log("Values in sorted order:", tree.values());
console.log("Node with key 0:", tree.find(0)?.data); // Finds data associated with key 0
console.log("Minimum key:", tree.min());
console.log("Maximum key:", tree.max());
console.log("Tree size:", tree.size);