Security News

### vlt Debuts New JavaScript Package Manager and Serverless Registry at NodeConf EU

vlt introduced its new package manager and a serverless registry this week, innovating in a space where npm has stagnated.

Huge News!Announcing our $40M Series B led by Abstract Ventures.Learn More →

The splaytree npm package provides an implementation of a splay tree, which is a self-adjusting binary search tree. It allows for efficient access, insertion, and deletion operations by moving frequently accessed elements closer to the root, thus optimizing subsequent operations.

Insertion

This feature allows you to insert elements into the splay tree. The tree adjusts itself so that the most recently accessed element is moved to the root.

```
const SplayTree = require('splaytree');
const tree = new SplayTree();
tree.insert(10);
tree.insert(20);
tree.insert(5);
console.log(tree.root.key); // 5
```

Search

This feature allows you to search for elements in the splay tree. The tree adjusts itself so that the most recently accessed element is moved to the root.

```
const SplayTree = require('splaytree');
const tree = new SplayTree();
tree.insert(10);
tree.insert(20);
tree.insert(5);
const node = tree.find(20);
console.log(node.key); // 20
console.log(tree.root.key); // 20
```

Deletion

This feature allows you to delete elements from the splay tree. The tree adjusts itself to maintain its properties after the deletion.

```
const SplayTree = require('splaytree');
const tree = new SplayTree();
tree.insert(10);
tree.insert(20);
tree.insert(5);
tree.remove(10);
console.log(tree.find(10)); // null
```

The avl package provides an implementation of an AVL tree, which is a self-balancing binary search tree. Unlike splay trees, AVL trees maintain a strict balance by ensuring that the heights of the two child subtrees of any node differ by at most one. This guarantees O(log n) time complexity for search, insertion, and deletion operations.

The bintrees package offers implementations of various binary search trees, including AVL trees and Red-Black trees. Red-Black trees are another type of self-balancing binary search tree that ensures O(log n) time complexity for search, insertion, and deletion operations. Unlike splay trees, Red-Black trees do not move frequently accessed elements closer to the root.

The js-sdsl package provides a variety of data structures, including splay trees, AVL trees, and Red-Black trees. This package offers a more comprehensive set of data structures compared to splaytree, making it a versatile choice for different use cases.

Splay-tree: **fast**(non-recursive) and **simple**(< 1000 lines of code)
Implementation is adapted directly from Wikipedia with the same API as w8r/avl, to run the benchmarks against other trees.

This tree is based on **top-down** splaying algorithm by D.Sleator. It supports

- splitting, merging
- updating of the keys
- bulk loading of the items into an empty or non-empty tree
- insertion with duplicates or no duplicates
- lookup without splaying

Operation | Average | Worst case |
---|---|---|

Space | O(n) | O(n) |

Search | O(log n) | amortized O(log n) |

Insert | O(log n) | amortized O(log n) |

Delete | O(log n) | amortized O(log n) |

```
npm i -S splaytree
```

```
import SplayTree from "splaytree";
const tree = new SplayTree();
```

Or get it from CDN

```
<script src="https://unpkg.com/splaytree"></script>
<script>
var tree = new SplayTree();
...
</script>
```

Or use the compiled version 'dist/splay.js'.

`new SplayTree([comparator])`

, where`comparator`

is optional comparison function`tree.insert(key:any, [data:any]):Node`

- Insert item, allow duplicate keys`tree.add(key:any, [data:any]):Node`

- Insert item if it is not present`tree.remove(key:any)`

- Remove item`tree.find(key):Node|Null`

- Return node by its key`tree.findStatic(key):Node|Null`

- Return node by its key (doesn't re-balance the tree)`tree.at(index:Number):Node|Null`

- Return node by its index in sorted order of keys`tree.contains(key):Boolean`

- Whether a node with the given key is in the tree`tree.forEach(function(node) {...}):Tree`

In-order traversal`tree.keys():Array<key>`

- Returns the array of keys in order`tree.values():Array<*>`

- Returns the array of data fields in order`tree.range(lo, high, function(node) {} [, context]):Tree`

- Walks the range of keys in order. Stops, if the visitor function returns a non-zero value.`tree.pop():Node`

- Removes smallest node`tree.min():key`

- Returns min key`tree.max():key`

- Returns max key`tree.minNode():Node`

- Returns the node with smallest key`tree.maxNode():Node`

- Returns the node with highest key`tree.prev(node):Node`

- Predecessor node`tree.next(node):Node`

- Successor node`tree.load(keys:Array<*>, [values:Array<*>][,presort=false]):Tree`

- Bulk-load items. It expects values and keys to be sorted, but if`presort`

is`true`

, it will sort keys and values using the comparator(in-place, your arrays are going to be altered).

**Comparator**

`function(a:key,b:key):Number`

- Comparator function between two keys, it returns

`0`

if the keys are equal`<0`

if`a < b`

`>0`

if`a > b`

The comparator function is extremely important, in case of errors you might end
up with a wrongly constructed tree or would not be able to retrieve your items.
It is crucial to test the return values of your `comparator(a,b)`

and `comparator(b,a)`

to make sure it's working correctly, otherwise you may have bugs that are very
unpredictable and hard to catch.

**Duplicate keys**

`insert()`

method allows duplicate keys. This can be useful in certain applications (example: overlapping points in 2D).`add()`

method will not allow duplicate keys - if key is already present in the tree, no new node is created

```
import Tree from "splaytree";
const t = new Tree();
t.insert(5);
t.insert(-10);
t.insert(0);
t.insert(33);
t.insert(2);
console.log(t.keys()); // [-10, 0, 2, 5, 33]
console.log(t.size); // 5
console.log(t.min()); // -10
console.log(t.max()); // -33
t.remove(0);
console.log(t.size); // 4
```

**Custom comparator (reverse sort)**

```
import Tree from "splaytree";
const t = new Tree((a, b) => b - a);
t.insert(5);
t.insert(-10);
t.insert(0);
t.insert(33);
t.insert(2);
console.log(t.keys()); // [33, 5, 2, 0, -10]
```

**Bulk insert**

```
import Tree from "splaytree";
const t = new Tree();
t.load([3, 2, -10, 20], ["C", "B", "A", "D"]);
console.log(t.keys()); // [-10, 2, 3, 20]
console.log(t.values()); // ['A', 'B', 'C', 'D']
```

```
npm run benchmark
```

```
Insert (x1000)
- Bintrees RB x 5,779 ops/sec ±1.37% (85 runs sampled) mean 0.173ms
- Splay (current) x 9,264 ops/sec ±2.70% (88 runs sampled) mean 0.108ms
- AVL x 7,459 ops/sec ±1.07% (91 runs sampled) mean 0.134ms
- Fastest is Splay (current)
Random read (x1000)
- Bintrees RB x 19,317 ops/sec ±0.52% (90 runs sampled) mean 0.052ms
- Splay (current) x 7,635 ops/sec ±0.92% (91 runs sampled) mean 0.131ms
- Splay (current) - static x 16,350 ops/sec ±0.75% (87 runs sampled) mean 0.061ms
- AVL x 15,782 ops/sec ±0.57% (91 runs sampled) mean 0.063ms
- Fastest is Bintrees RB
Remove (x1000)
- Bintrees RB x 195,282 ops/sec ±0.85% (90 runs sampled) mean 0.005ms
- Splay (current) x 364,630 ops/sec ±6.05% (87 runs sampled) mean 0.003ms
- AVL x 95,946 ops/sec ±0.76% (93 runs sampled) mean 0.010ms
- Fastest is Splay (current)
Bulk-load (x10000)
- 1 by 1 x 266 ops/sec ±1.58% (83 runs sampled) mean 3.755ms
- bulk load (build) x 287 ops/sec ±3.02% (76 runs sampled) mean 3.487ms
- Fastest is bulk load (build)
Bulk-add (x1000) to 1000
- 1 by 1 x 2,859 ops/sec ±3.35% (77 runs sampled) mean 0.350ms
- bulk add (rebuild) x 3,755 ops/sec ±2.67% (67 runs sampled) mean 0.266ms
- Fastest is bulk add (rebuild)
Bulk-remove-insert (10%) of 10000
- 1 by 1 x 771 ops/sec ±4.31% (68 runs sampled) mean 1.297ms
- bulk add (rebuild) x 706 ops/sec ±1.12% (88 runs sampled) mean 1.416ms
- Fastest is 1 by 1
Bulk-update (10%) of 10000
- 1 by 1 x 717 ops/sec ±1.96% (79 runs sampled) mean 1.394ms
- split-merge x 705 ops/sec ±1.68% (85 runs sampled) mean 1.419ms
- Fastest is 1 by 1
```

Adding google closure library to the benchmark is, of course, unfair, cause the node.js version of it is not optimized by the compiler, but in this case it plays the role of straight-forward robust implementation.

```
npm i
npm t
npm run build
```

- try and add parent fields for efficient
`.prev()`

and`.next()`

, or iterators

The MIT License (MIT)

Copyright (c) 2019 Alexander Milevski info@w8r.name

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

FAQs

Fast Splay tree for Node and browser

We found that splaytree demonstrated a **not healthy** version release cadence and project activity because the last version was released a year ago. It has **1 open source maintainer** collaborating on the project.

Did you know?

Socket for GitHub automatically highlights issues in each pull request and monitors the health of all your open source dependencies. Discover the contents of your packages and block harmful activity before you install or update your dependencies.

Security News

vlt introduced its new package manager and a serverless registry this week, innovating in a space where npm has stagnated.

By Sarah Gooding - Nov 08, 2024

Security News

Research

The Socket Research Team uncovered a malicious Python package typosquatting the popular 'fabric' SSH library, silently exfiltrating AWS credentials from unsuspecting developers.

By Socket Research Team - Nov 06, 2024

Security News

At its inaugural meeting, the JSR Working Group outlined plans for an open governance model and a roadmap to enhance JavaScript package management.

By Sarah Gooding - Nov 05, 2024