🌴 A high-performance, feature-rich AVL Tree (self-balancing binary search tree) implementation for JavaScript/TypeScript
npm install sawit.js
> A high-performance, feature-rich AVL Tree (self-balancing binary search tree) implementation for JavaScript/TypeScript.
Sawit (Indonesian for "palm oil tree") provides a sorted set data structure with O(log n) operations, perfect for scenarios where you need fast insertion, deletion, and ordered queries.
- 🚀 O(log n) insert, delete, search, and order statistics
- 🎯 Order Statistics: kthSmallest, kthLargest, rank, select
- 📊 Range Queries: range, rangeCount, floor, ceiling
- 🔄 Set Operations: union, intersection, difference
- 🎪 Iterators: for...of, inOrder, preOrder, postOrder, levelOrder
- 🧩 Functional API: map, filter, reduce, every, some, find
- 📦 Zero Dependencies: Pure TypeScript implementation
- 📘 Full TypeScript Support: Complete type definitions included
``bash`
npm install sawit.jsor
yarn add sawit.jsor
bun add sawit.js
`typescript
import { SawitTree } from 'sawit.js';
// Create a tree
const tree = new SawitTree
// Insert values (chainable)
tree.insert(5).insert(3).insert(7).insert(1).insert(9);
// Check existence
console.log(tree.has(5)); // true
console.log(tree.size); // 5
// Get min/max
console.log(tree.min()); // 1
console.log(tree.max()); // 9
// Iterate in sorted order
for (const value of tree) {
console.log(value); // 1, 3, 5, 7, 9
}
// Convert to array
console.log(tree.toArray()); // [1, 3, 5, 7, 9]
`
`typescript
// Objects with custom comparison
interface User {
id: number;
name: string;
score: number;
}
const leaderboard = new SawitTree
leaderboard.insert({ id: 1, name: 'Alice', score: 100 });
leaderboard.insert({ id: 2, name: 'Bob', score: 150 });
leaderboard.insert({ id: 3, name: 'Charlie', score: 120 });
// Get top player
const top = leaderboard.kthSmallest(1);
console.log(top?.name); // 'Bob'
`
`typescript
const tree = SawitTree.from([1, 3, 5, 7, 9, 11, 13, 15]);
// Get all values in range [5, 11]
console.log(tree.range(5, 11)); // [5, 7, 9, 11]
// Floor & Ceiling
console.log(tree.floor(6)); // 5 (largest ≤ 6)
console.log(tree.ceiling(6)); // 7 (smallest ≥ 6)
// Count elements in range
console.log(tree.rangeCount(5, 11)); // 4
`
`typescript
const tree = SawitTree.from([10, 20, 30, 40, 50]);
// Rank: how many elements < value
console.log(tree.rank(30)); // 2
// Select: get element at rank
console.log(tree.select(2)); // 30
// Kth smallest/largest
console.log(tree.kthSmallest(2)); // 20 (2nd smallest)
console.log(tree.kthLargest(2)); // 40 (2nd largest)
`
`typescript
const numbers = SawitTree.from([1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);
// Filter even numbers
const evens = numbers.filter(n => n % 2 === 0);
console.log(evens.toArray()); // [2, 4, 6, 8, 10]
// Map to squares
const squares = numbers.map(n => n * n);
console.log(squares.toArray()); // [1, 4, 9, 16, 25, 36, 49, 64, 81, 100]
// Reduce to sum
const sum = numbers.reduce((acc, n) => acc + n, 0);
console.log(sum); // 55
`
`typescript
const a = SawitTree.from([1, 2, 3, 4, 5]);
const b = SawitTree.from([4, 5, 6, 7, 8]);
console.log(a.union(b).toArray()); // [1, 2, 3, 4, 5, 6, 7, 8]
console.log(a.intersection(b).toArray()); // [4, 5]
console.log(a.difference(b).toArray()); // [1, 2, 3]
`
| Method | Description |
| --------------------------------------- | ------------------------------------------ |
| new SawitTree | Create empty tree with optional comparator |SawitTree.from(iterable, comparator?)
| | Create tree from iterable |SawitTree.of(...values)
| | Create tree from arguments |
| Property | Type | Description | Complexity |
| --------- | --------- | ------------------ | ---------- |
| size | number | Number of elements | O(1) |height
| | number | Tree height | O(1) |isEmpty
| | boolean | True if empty | O(1) |
| Method | Returns | Description | Complexity |
| ------------------- | --------- | --------------- | ---------- |
| insert(value) | this | Insert value | O(log n) |insertAll(values)
| | this | Insert multiple | O(k log n) |delete(value)
| | boolean | Remove value | O(log n) |has(value)
| | boolean | Check existence | O(log n) |clear()
| | void | Remove all | O(1) |
| Method | Returns | Description | Complexity |
| -------------- | ---------------- | ------------------- | ---------- |
| min() | T \| undefined | Minimum value | O(log n) |max()
| | T \| undefined | Maximum value | O(log n) |extractMin()
| | T \| undefined | Remove & return min | O(log n) |extractMax()
| | T \| undefined | Remove & return max | O(log n) |
| Method | Returns | Description | Complexity |
| ---------------- | ---------------- | ---------------- | ---------- |
| floor(value) | T \| undefined | Largest ≤ value | O(log n) |ceiling(value)
| | T \| undefined | Smallest ≥ value | O(log n) |lower(value)
| | T \| undefined | Largest < value | O(log n) |higher(value)
| | T \| undefined | Smallest > value | O(log n) |
| Method | Returns | Description | Complexity |
| ---------------- | ---------------- | ----------------------------- | ---------- |
| rank(value) | number | Count of elements < value | O(log n) |select(k)
| | T \| undefined | Element at rank k (0-indexed) | O(log n) |kthSmallest(k)
| | T \| undefined | K-th smallest (1-indexed) | O(log n) |kthLargest(k)
| | T \| undefined | K-th largest (1-indexed) | O(log n) |
| Method | Returns | Description | Complexity |
| ----------------------- | -------- | ----------------------- | ------------ |
| range(low, high) | T[] | Elements in [low, high] | O(k + log n) |rangeCount(low, high)
| | number | Count in range | O(log n) |
| Method | Returns | Description |
| --------------------- | -------------- | ----------------- |
| [Symbol.iterator]() | Iterator | In-order iterator |inOrder()
| | Generator | Left, Root, Right |preOrder()
| | Generator | Root, Left, Right |postOrder()
| | Generator | Left, Right, Root |levelOrder()
| | Generator | BFS traversal |reverseInOrder()
| | Generator | Descending order |
| Method | Returns | Description | Complexity |
| ---------------------- | ---------------- | --------------------- | ---------- |
| forEach(callback) | void | Execute for each | O(n) |map(fn, comparator?)
| | SawitTree | Transform to new tree | O(n log n) |filter(predicate)
| | SawitTree | Filter elements | O(n log n) |reduce(fn, initial)
| | U | Reduce to value | O(n) |every(predicate)
| | boolean | All match? | O(n) |some(predicate)
| | boolean | Any match? | O(n) |find(predicate)
| | T \| undefined | First match | O(n) |
| Method | Returns | Description | Complexity |
| ---------------------------- | -------------- | ---------------------- | ----------------- |
| union(other) | SawitTree | All from both | O((n+m) log(n+m)) |intersection(other)
| | SawitTree | Common elements | O(n log m) |difference(other)
| | SawitTree | In this, not other | O(n log m) |symmetricDifference(other)
| | SawitTree | In one, not both | O((n+m) log(n+m)) |isSubsetOf(other)
| | boolean | All in other? | O(n log m) |isSupersetOf(other)
| | boolean | Contains all of other? | O(m log n) |
| Method | Returns | Description | Complexity |
| ------------ | -------------- | -------------- | ---------- |
| toArray() | T[] | Sorted array | O(n) |toSet()
| | Set | Convert to Set | O(n) |clone()
| | SawitTree | Deep copy | O(n log n) |toString()
| | string` | JSON structure | O(n) |
| Operation | Sawit.js (AVL) | Array | Sorted Array |
| ----------- | -------------- | ---------- | ------------ |
| Insert | O(log n) | O(1)* | O(n) |
| Delete | O(log n) | O(n) | O(n) |
| Search | O(log n) | O(n) | O(log n) |
| Min/Max | O(log n) | O(n) | O(1) |
| Kth Element | O(log n) | O(n log n) | O(1) |
| Range Query | O(k + log n) | O(n) | O(k + log n) |
*Array insert is O(1) amortized at end, O(n) at arbitrary position.
MIT © xirf
Contributions welcome! Please read our Contributing Guide first.
---
Made with ❤️ and 🌴