npm package discovery and stats viewer.

Discover Tips

  • General search

    [free text search, go nuts!]

  • Package details

    pkg:[package-name]

  • User packages

    @[username]

Sponsor

Optimize Toolset

I’ve always been into building performant and accessible sites, but lately I’ve been taking it extremely seriously. So much so that I’ve been building a tool to help me optimize and monitor the sites that I build to make sure that I’m making an attempt to offer the best experience to those who visit them. If you’re into performant, accessible and SEO friendly sites, you might like it too! You can check it out at Optimize Toolset.

About

Hi, 👋, I’m Ryan Hefner  and I built this site for me, and you! The goal of this site was to provide an easy way for me to check the stats on my npm packages, both for prioritizing issues and updates, and to give me a little kick in the pants to keep up on stuff.

As I was building it, I realized that I was actually using the tool to build the tool, and figured I might as well put this out there and hopefully others will find it to be a fast and useful way to search and browse npm packages as I have.

If you’re interested in other things I’m working on, follow me on Twitter or check out the open source projects I’ve been publishing on GitHub.

I am also working on a Twitter bot for this site to tweet the most popular, newest, random packages from npm. Please follow that account now and it will start sending out packages soon–ish.

Open Software & Tools

This site wouldn’t be possible without the immense generosity and tireless efforts from the people who make contributions to the world and share their work via open source initiatives. Thank you 🙏

© 2024 – Pkg Stats / Ryan Hefner

@nesto-software/avl

v1.4.7

Published

Fast AVL tree for Node and browser

Downloads

24

Readme

AVL tree npm version CircleCI

AVL-tree: fast(non-recursive) and simple(< 500 lines of code)

AVL-tree

| Operation | Average | Worst case | | ------------- | ------------- | ------------ | | Space | O(n) | O(n) | | Search | O(log n) | O(log n) | | Insert | O(log n) | O(log n) | | Delete | O(log n) | O(log n) |

Install

npm i -S avl
import AVLTree from 'avl';
const tree = new AVLTree();

Or get it from CDN

<script src="https://unpkg.com/avl"></script>
<script>
  var tree = new AVLTree();
  ...
</script>

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

Try it in your browser

API

  • new AVLTree([comparator], [noDuplicates:Boolean]), where compare is optional comparison function
  • tree.insert(key:any, [data:any]) - Insert item
  • tree.remove(key:any) - Remove item
  • tree.find(key):Node|Null - Return node by its key
  • 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.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.keys():Array<key> - Returns the array of keys in order
  • tree.values():Array<*> - Returns the array of data fields in order
  • tree.pop():Node - Removes smallest node
  • tree.popMax():Node - Removes highest 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<*>]):Tree - Bulk-load items
  • tree.destroy():Tree, tree.clear():Tree - Empty the tree

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

By default, tree allows duplicate keys. You can disable that by passing true as a second parameter to the tree constructor. In that case if you would try to instert an item with the key, that is already present in the tree, it will not be inserted. However, the default behavior allows for duplicate keys, cause there are cases where you cannot predict that the keys would be unique (example: overlapping points in 2D).

Example

import Tree from 'avl';

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 'avl';

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 'avl';

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']

Benchmarks

npm run benchmark
Insert (x1000)
Bintrees x 3,742 ops/sec ±0.89% (90 runs sampled)
Functional red black tree x 1,880 ops/sec ±4.02% (78 runs sampled)
Google Closure library AVL x 622 ops/sec ±4.22% (81 runs sampled)
AVL (current) x 6,151 ops/sec ±8.50% (72 runs sampled)
- Fastest is AVL (current)

Random read (x1000)
Bintrees x 7,371 ops/sec ±2.69% (83 runs sampled)
Functional red black tree x 13,010 ops/sec ±2.93% (83 runs sampled)
Google Closure library AVL x 27.63 ops/sec ±1.04% (49 runs sampled)
AVL (current) x 12,921 ops/sec ±1.83% (86 runs sampled)
- Fastest is AVL (current)

Remove (x1000)
Bintrees x 106,837 ops/sec ±0.74% (86 runs sampled)
Functional red black tree x 25,368 ops/sec ±0.89% (88 runs sampled)
Google Closure library AVL x 31,719 ops/sec ±1.21% (89 runs sampled)
AVL (current) x 108,131 ops/sec ±0.70% (88 runs sampled)
- Fastest is AVL (current)

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

Develop

npm i
npm t
npm run build

License

The MIT License (MIT)

Copyright (c) 2017 Alexander Milevski [email protected]

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.