@foxglove/avl
TypeScript icon, indicating that this package has built-in type declarations

1.0.0 • Public • Published

@foxglove/avl

Adelson-Velsky-Landis (AVL) self-balancing binary trees in TypeScript

Introduction

AVL trees are self-balancing binary trees that are commonly used to implement sorted sets. In addition to the common insertion, deletion, and retrieval operations, this implementation also supports range queries, greater than, and less than searches.

Usage

import { AVLTree } from "@foxglove/avl";

const tree = new AVLTree<number, string>();
tree.set(0, "zero");
tree.set(1, "1");
tree.set(1, "one");
tree.set(3, "three");
tree.set(2, "two");
tree.delete(0);
console.log(tree.has(0)); // false
console.log(tree.get(1)); // "one"
console.log(tree.size); // 3
console.log(tree.minEntry()); // [1, "one"]
console.log(tree.maxEntry()); // [3, "three"]
console.log(tree.findLessThan(2)); // [1, "one"]
console.log(tree.findGreaterThanOrEqual(2)); // [2, "two"]
tree.forEach((value, key) => console.log(value)); // "one" "two" "three"
tree.range(2, 3, (value, key) => console.log(value)); // "two" "three"
console.log(tree.pop()); // [3, "three"]
console.log(tree.shift()); // [1, "one"]
tree.clear();

// Use a custom comparator for non-Number keys
const bigintTree = new AVLTree<bigint, string>((a, b) => Number(a - b));
bigintTree.set(1n, "one");

Alternatives

avl - Optional support for duplicate keys, but return values can mutate after delete() calls, missing range query optimization, no find[Less/Greater]Than[OrEqual] queries, no iterators, and naming conventions do not follow ES6 container patterns.

License

@foxglove/avl is licensed under MIT License.

Releasing

  1. Run yarn version --[major|minor|patch] to bump version
  2. Run git push && git push --tags to push new tag
  3. GitHub Actions will take care of the rest

Stay in touch

Join our Slack channel to ask questions, share feedback, and stay up to date on what our team is working on.

/@foxglove/avl/

    Package Sidebar

    Install

    npm i @foxglove/avl

    Weekly Downloads

    328

    Version

    1.0.0

    License

    MIT

    Unpacked Size

    121 kB

    Total Files

    26

    Last publish

    Collaborators

    • foxglovebot
    • amacneil