{"id":12060,"library":"splaytree","title":"Fast Splay Tree","description":"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.","status":"active","version":"3.2.3","language":"javascript","source_language":"en","source_url":"https://github.com/w8r/splay-tree","tags":["javascript","binary-tree","bst","splay-tree","splay","balanced-search-tree","typescript"],"install":[{"cmd":"npm install splaytree","lang":"bash","label":"npm"},{"cmd":"yarn add splaytree","lang":"bash","label":"yarn"},{"cmd":"pnpm add splaytree","lang":"bash","label":"pnpm"}],"dependencies":[],"imports":[{"note":"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.","wrong":"import { SplayTree } from 'splaytree';\nconst SplayTree = require('splaytree');","symbol":"SplayTree","correct":"import SplayTree from 'splaytree';"},{"note":"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.","symbol":"Node","correct":"import type { Node } from 'splaytree';"}],"quickstart":{"code":"import SplayTree from \"splaytree\";\n\nconst tree = new SplayTree();\n\n// Insert various key-value pairs\ntree.insert(5, \"apple\");\ntree.insert(-10, \"banana\");\ntree.add(0, \"cherry\"); // Using add to prevent duplicates if 0 already existed\ntree.insert(33, \"date\");\ntree.insert(2, \"elderberry\");\ntree.insert(5, \"fig\"); // Demonstrates duplicate key insertion with 'insert'\n\nconsole.log(\"Keys in sorted order:\", tree.keys());\nconsole.log(\"Values in sorted order:\", tree.values());\nconsole.log(\"Node with key 0:\", tree.find(0)?.data); // Finds data associated with key 0\nconsole.log(\"Minimum key:\", tree.min());\nconsole.log(\"Maximum key:\", tree.max());\nconsole.log(\"Tree size:\", tree.size);","lang":"javascript","description":"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."},"warnings":[{"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)`.","message":"Incorrectly implemented comparator function can lead to a malformed tree or unpredictable search results and performance issues.","severity":"gotcha","affected_versions":">=1.0.0"},{"fix":"Upgrade your Node.js environment to a compatible version (18.20+ or 20+). Check the `engines` field in `package.json` for precise requirements.","message":"The package requires Node.js version 18.20 or 20 and above. Older Node.js versions are not supported.","severity":"breaking","affected_versions":">=3.0.0"},{"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.","message":"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.","severity":"gotcha","affected_versions":">=1.0.0"},{"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.","message":"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.","severity":"gotcha","affected_versions":">=3.2.0"}],"env_vars":null,"last_verified":"2026-04-19T00:00:00.000Z","next_check":"2026-07-18T00:00:00.000Z","problems":[{"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;`.","cause":"Attempting to instantiate `SplayTree` after an incorrect CommonJS `require()` or a named import when it's a default export.","error":"TypeError: SplayTree is not a constructor"},{"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)`.","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.","error":"RangeError: Maximum call stack size exceeded"}],"ecosystem":"npm"}