# @foxglove/avl

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.

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

## Package Sidebar

### Install

`npm i @foxglove/avl`

### Repository

github.com/foxglove/avl

### Homepage

github.com/foxglove/avl

443

1.0.0

MIT

121 kB

26