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

✨ Features

• 🚀 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

📦 Installation

npm install sawit.js
# or
yarn add sawit.js
# or
bun add sawit.js

🚀 Quick Start

import { SawitTree } from 'sawit.js';

// Create a tree
const tree = new SawitTree<number>();

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

📖 Usage Examples

Custom Comparator

// Objects with custom comparison
interface User {
    id: number;
    name: string;
    score: number;
}

const leaderboard = new SawitTree<User>((a, b) => b.score - a.score); // Descending

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'

Range Queries

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

Order Statistics

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)

Functional Operations

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

Set Operations

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]

📚 API Reference

Constructor

| Method | Description | | --------------------------------------- | ------------------------------------------ | | new SawitTree<T>(comparator?) | Create empty tree with optional comparator | | SawitTree.from(iterable, comparator?) | Create tree from iterable | | SawitTree.of(...values) | Create tree from arguments |

Properties

| Property | Type | Description | Complexity | | --------- | --------- | ------------------ | ---------- | | size | number | Number of elements | O(1) | | height | number | Tree height | O(1) | | isEmpty | boolean | True if empty | O(1) |

Core Operations

| 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) |

Min/Max

| 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) |

Floor/Ceiling/Lower/Higher

| 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) |

Order Statistics

| 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) |

Range Queries

| 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) |

Traversal

| Method | Returns | Description | | --------------------- | -------------- | ----------------- | | [Symbol.iterator]() | Iterator<T> | In-order iterator | | inOrder() | Generator<T> | Left, Root, Right | | preOrder() | Generator<T> | Root, Left, Right | | postOrder() | Generator<T> | Left, Right, Root | | levelOrder() | Generator<T> | BFS traversal | | reverseInOrder() | Generator<T> | Descending order |

Functional Methods

| Method | Returns | Description | Complexity | | ---------------------- | ---------------- | --------------------- | ---------- | | forEach(callback) | void | Execute for each | O(n) | | map(fn, comparator?) | SawitTree<U> | Transform to new tree | O(n log n) | | filter(predicate) | SawitTree<T> | 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) |

Set Operations

| Method | Returns | Description | Complexity | | ---------------------------- | -------------- | ---------------------- | ----------------- | | union(other) | SawitTree<T> | All from both | O((n+m) log(n+m)) | | intersection(other) | SawitTree<T> | Common elements | O(n log m) | | difference(other) | SawitTree<T> | In this, not other | O(n log m) | | symmetricDifference(other) | SawitTree<T> | 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) |

Conversion

| Method | Returns | Description | Complexity | | ------------ | -------------- | -------------- | ---------- | | toArray() | T[] | Sorted array | O(n) | | toSet() | Set<T> | Convert to Set | O(n) | | clone() | SawitTree<T> | Deep copy | O(n log n) | | toString() | string | JSON structure | O(n) |

⚡ Performance

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

📄 License

MIT © xirf

🤝 Contributing

Contributions welcome! Please read our Contributing Guide first.