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

---

Made with ❤️ and 🌴