splaytree

library3.2.3jsnpmunverified

splaytree is a JavaScript library providing a fast, non-recursive implementation of a Splay tree data structure. It is designed for use in both Node.js environments (requiring Node.js >=18.20 or >=20) and modern browsers. The current stable version is 3.2.3, with recent patch releases indicating active maintenance and quick fixes for module resolution issues. Key differentiators include its simplicity (under 1000 lines of code) and high performance, offering amortized O(log n) time complexity for search, insert, and delete operations. It supports splitting, merging, key updates, bulk loading, and allows for optional duplicate keys. Its API is similar to w8r/avl, making it familiar to users of that library, and the implementation is adapted directly from Wikipedia's top-down splaying algorithm.

database serialization

npm install splaytree

github ↗package ↗

INSTALL

IMPORT

SIG · SPLAYTREE

splaytree

databasejavascriptv3.2.3

Install

—

Import

—

Disk

—

Pass rate

0/ 6

Env Coverage0 / 6

glibc

18–22

musl

18–22

Install & Compatibility

Where this runs

tested against v? · npm install

Install × environment matrix

Each cell = how many times install + import succeeded across repeated harness runs. Partial = flaky.
glibc = Debian/Ubuntu slim · musl = Alpine Linux

musl

node 18–226 runs

build_error

glibc

node 18–226 runs

build_error

Code

Verified usage

Verified import paths — ran on the pinned version, not inferred.

SplayTree

✓ import SplayTree from 'splaytree';

✗ import { SplayTree } from 'splaytree'; const SplayTree = require('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.

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);

Debug

Known issues

gotchaIncorrectly 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)`.

affects: >=1.0.0

breakingThe 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.

affects: >=3.0.0

gotchaThe `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.

affects: >=1.0.0

gotchaRecent 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.

affects: >=3.2.0

Errors

Common errors & fixes

TypeError: SplayTree is not a constructor

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

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)`.

Upgrade

Version history

3.2.3latest on npm

Audit

Dependencies

No dependency data recorded yet.

Agent activity

14 hits · last 30 days

node