# sonic-forest

> High-performance (binary) tree and sorted map implementation (AVL, Splay, Radix, Red-Black)

Latest version **1.2.1** (published 2025-08-01) · Apache-2.0 license · 0 weekly downloads

## Install

```sh
npm install sonic-forest
pnpm add sonic-forest
yarn add sonic-forest
bun add sonic-forest
```

## Health

**Score 35/100 (D)** — status: maintenance-mode.

Positive: has types; no vulnerabilities; high quality score.

Warnings: low downloads; no esm support.

Negative: stale; low maintenance score.

## Facts

| | |
|---|---|
| Version | 1.2.1 |
| Published | 2025-08-01 |
| First published | 2024-04-20 |
| Weekly downloads | 0 |
| License | Apache-2.0 |
| TypeScript types | bundled |
| Module format | CommonJS |
| Node | >=10.0 |
| Dependencies | 1 |
| Unpacked size | 148.1 KB |
| Known vulnerabilities | 0 |
| Install scripts | no |
| GitHub stars | 23 |
| Author | streamich |
| Maintainers | streamich |
| Keywords | tree, binary tree, binary search tree, bst, avl, red-black, rb-tree, avl-tree, splay, splay tree, radix |

## Links

- npm: https://www.npmjs.com/package/sonic-forest
- Repository: https://github.com/streamich/sonic-forest
- Issues: https://github.com/streamich/sonic-forest/issues
- Funding: https://github.com/sponsors/streamich
- npm.io page: https://npm.io/package/sonic-forest

## Dependencies (1)

- [tree-dump](https://npm.io/package/tree-dump.md) ^1.0.0

## Alternatives

- [jsforce](https://npm.io/package/jsforce.md) — 851.2K weekly downloads
- [react-native-qrcode-svg](https://npm.io/package/react-native-qrcode-svg.md) — 693.5K weekly downloads
- [@salesforce/plugin-data](https://npm.io/package/@salesforce/plugin-data.md) — 394.9K weekly downloads
- [@backstage/plugin-search-common](https://npm.io/package/@backstage/plugin-search-common.md) — 308.5K weekly downloads
- [@chain-registry/types](https://npm.io/package/@chain-registry/types.md) — 38.4K weekly downloads

## Recent versions

- 1.2.1 (latest) — 2025-08-01
- 1.2.0 — 2025-02-13
- 1.1.0 — 2025-02-02
- 1.0.3 — 2024-05-08
- 1.0.2 — 2024-05-01
- 1.0.1 — 2024-04-30
- 1.0.0 — 2024-04-20

## README

# Sonic Forest

High performance (binary) tree and sorted map implementation for JavaScript in TypeScript.

## Features

- AVL tree implementation
- AVL sorted map implementation
- AVL sorted set implementation
- Red-black (RB) tree implementation
- Red-black (RB) tree sorted map implementation
- Left-leaning Red-black (LLRB) tree implementation
- Radix tree implementation (string keys)
- Binary radix tree implementation (Uint8Array keys)
- Splay tree implementation
- Various utility methods for binary trees

This package implements the fastest insertion into self-balancing binary tree out of any
NPM package. Both, AVL and Red-black tree insertion implementations of `sonic-forest` a faster
than inserts in [`js-sdsl`](https://www.npmjs.com/package/js-sdsl) implementation.

However, deletions from a binary tree are faster in `js-sdsl`. But, deletions in `sonic-forest`
delete exactly the node, which contains the key. Unlike, in `js-sdsl` and all other
binary tree libraries, where those libraries find the in-order-sucessor or -predecessor, which
is a leaf node, and delete that instead. As such, one can keep pointers to `sonic-forest` AVL
and Red-black tree nodes, and those pointers will stay valid even after deletions.

## Binary Radix Tree

The binary radix tree implementation supports `Uint8Array` keys, making it suitable for binary data like:

- Binary protocol routing
- File system paths as binary data
- Cryptographic hashes
- Network packet classification
- Any binary blob keys

### Key Features

- **Efficient slicing**: Uses `Slice` class to reference portions of `Uint8Array` without copying data
- **Prefix compression**: Automatically compresses common prefixes to save memory
- **Binary-safe**: Works with any byte sequence, including null bytes
- **Same API**: Provides similar interface to the string-based radix tree

### Usage Example

```typescript
import { BinaryRadixTree } from 'sonic-forest';

const tree = new BinaryRadixTree<string>();

// Insert binary keys
tree.set(new Uint8Array([0x47, 0x45, 0x54, 0x20]), 'GET ');     // "GET "
tree.set(new Uint8Array([0x50, 0x4F, 0x53, 0x54]), 'POST');      // "POST"
tree.set(new Uint8Array([0x50, 0x55, 0x54, 0x20]), 'PUT ');      // "PUT "

// Retrieve values
console.log(tree.get(new Uint8Array([0x47, 0x45, 0x54, 0x20]))); // "GET "

// Delete keys
tree.delete(new Uint8Array([0x50, 0x4F, 0x53, 0x54])); // Remove POST

console.log(tree.size); // 2
```

---
_Source: https://npm.io/package/sonic-forest · Machine-readable twin of the npm.io package page. Health data is recomputed on every publish._