tree-set-typed
v2.4.4
Published
TreeSet - A sorted set implementation based on Red-Black Tree
Maintainers
zrwusa.orgReadme
What
Brief
This is a standalone Red Black Tree data structure from the data-structure-typed collection. If you wish to access more data structures or advanced features, you can transition to directly installing the complete data-structure-typed package
How
install
npm
npm i red-black-tree-typed --saveyarn
yarn add red-black-tree-typedsnippet
TS
import {RedBlackTree} from 'data-structure-typed';
// /* or if you prefer */ import {RedBlackTree} from 'red-black-tree-typed';
const rbTree = new RedBlackTree<number>();
const idsOrVals = [11, 3, 15, 1, 8, 13, 16, 2, 6, 9, 12, 14, 4, 7, 10, 5];
rbTree.addMany(idsOrVals);
const node6 = rbTree.getNode(6);
node6 && rbTree.getHeight(node6) // 3
node6 && rbTree.getDepth(node6) // 1
const getNodeById = rbTree.getNodeByKey(10);
getNodeById?.id // 10
const getMinNodeByRoot = rbTree.getLeftMost();
getMinNodeByRoot?.id // 1
const node15 = rbTree.getNodeByKey(15);
const getMinNodeBySpecificNode = node15 && rbTree.getLeftMost(node15);
getMinNodeBySpecificNode?.id // 12
const lesserSum = rbTree.lesserSum(10);
lesserSum // 45
const node11 = rbTree.getNodeByKey(11);
node11?.id // 11
const dfs = rbTree.dfs('in');
dfs[0].id // 1
rbTree.perfectlyBalance();
const bfs = rbTree.bfs('node');
rbTree.isPerfectlyBalanced() && bfs[0].id // 8
rbTree.delete(11, true)[0].deleted?.id // 11
rbTree.isAVLBalanced(); // true
node15 && rbTree.getHeight(node15) // 2
rbTree.delete(1, true)[0].deleted?.id // 1
rbTree.isAVLBalanced(); // true
rbTree.getHeight() // 4
rbTree.delete(4, true)[0].deleted?.id // 4
rbTree.isAVLBalanced(); // true
rbTree.getHeight() // 4
rbTree.delete(10, true)[0].deleted?.id // 10
rbTree.isAVLBalanced(); // true
rbTree.getHeight() // 3
rbTree.delete(15, true)[0].deleted?.id // 15
rbTree.isAVLBalanced(); // true
rbTree.getHeight() // 3
rbTree.delete(5, true)[0].deleted?.id // 5
rbTree.isAVLBalanced(); // true
rbTree.getHeight() // 3
rbTree.delete(13, true)[0].deleted?.id // 13
rbTree.isAVLBalanced(); // true
rbTree.getHeight() // 3
rbTree.delete(3, true)[0].deleted?.id // 3
rbTree.isAVLBalanced(); // true
rbTree.getHeight() // 3
rbTree.delete(8, true)[0].deleted?.id // 8
rbTree.isAVLBalanced(); // true
rbTree.getHeight() // 3
rbTree.delete(6, true)[0].deleted?.id // 6
rbTree.delete(6, true).length // 0
rbTree.isAVLBalanced(); // true
rbTree.getHeight() // 2
rbTree.delete(7, true)[0].deleted?.id // 7
rbTree.isAVLBalanced(); // true
rbTree.getHeight() // 2
rbTree.delete(9, true)[0].deleted?.id // 9
rbTree.isAVLBalanced(); // true
rbTree.getHeight() // 2
rbTree.delete(14, true)[0].deleted?.id // 14
rbTree.isAVLBalanced(); // true
rbTree.getHeight() // 1
rbTree.isAVLBalanced(); // true
const lastBFSIds = rbTree.BFS();
lastBFSIds[0] // 12
const lastBFSNodes = rbTree.BFS('node');
lastBFSNodes[0].id // 12JS
const {RedBlackTree} = require('data-structure-typed');
// /* or if you prefer */ const {RedBlackTree} = require('red-black-tree-typed');
const rbTree = new RedBlackTree();
const idsOrVals = [11, 3, 15, 1, 8, 13, 16, 2, 6, 9, 12, 14, 4, 7, 10, 5];
rbTree.addMany(idsOrVals, idsOrVals);
const node6 = rbTree.getNodeByKey(6);
node6 && rbTree.getHeight(node6) // 3
node6 && rbTree.getDepth(node6) // 1
const getNodeById = rbTree.get(10, 'id');
getNodeById?.id // 10
const getMinNodeByRoot = rbTree.getLeftMost();
getMinNodeByRoot?.id // 1
const node15 = rbTree.getNodeByKey(15);
const getMinNodeBySpecificNode = node15 && rbTree.getLeftMost(node15);
getMinNodeBySpecificNode?.id // 12
const node11 = rbTree.getNodeByKey(11);
node11?.id // 11
const dfs = rbTree.dfs('in');
dfs[0].id // 1
rbTree.perfectlyBalance();
const bfs = rbTree.bfs('node');
rbTree.isPerfectlyBalanced() && bfs[0].id // 8
rbTree.delete(11, true)[0].deleted?.id // 11
rbTree.isAVLBalanced(); // true
node15 && rbTree.getHeight(node15) // 2
rbTree.delete(1, true)[0].deleted?.id // 1
rbTree.isAVLBalanced(); // true
rbTree.getHeight() // 4
rbTree.delete(4, true)[0].deleted?.id // 4
rbTree.isAVLBalanced(); // true
rbTree.getHeight() // 4
rbTree.delete(10, true)[0].deleted?.id // 10
rbTree.isAVLBalanced(); // true
rbTree.getHeight() // 3
rbTree.delete(15, true)[0].deleted?.id // 15
rbTree.isAVLBalanced(); // true
rbTree.getHeight() // 3
rbTree.delete(5, true)[0].deleted?.id // 5
rbTree.isAVLBalanced(); // true
rbTree.getHeight() // 3
rbTree.delete(13, true)[0].deleted?.id // 13
rbTree.isAVLBalanced(); // true
rbTree.getHeight() // 3
rbTree.delete(3, true)[0].deleted?.id // 3
rbTree.isAVLBalanced(); // true
rbTree.getHeight() // 3
rbTree.delete(8, true)[0].deleted?.id // 8
rbTree.isAVLBalanced(); // true
rbTree.getHeight() // 3
rbTree.delete(6, true)[0].deleted?.id // 6
rbTree.delete(6, true).length // 0
rbTree.isAVLBalanced(); // true
rbTree.getHeight() // 2
rbTree.delete(7, true)[0].deleted?.id // 7
rbTree.isAVLBalanced(); // true
rbTree.getHeight() // 2
rbTree.delete(9, true)[0].deleted?.id // 9
rbTree.isAVLBalanced(); // true
rbTree.getHeight() // 2
rbTree.delete(14, true)[0].deleted?.id // 14
rbTree.isAVLBalanced(); // true
rbTree.getHeight() // 1
rbTree.isAVLBalanced(); // true
const lastBFSIds = rbTree.bfs();
lastBFSIds[0] // 12
const lastBFSNodes = rbTree.bfs('node');
lastBFSNodes[0].id // 12basic Red-Black Tree with simple number keys
// Create a simple Red-Black Tree with numeric keys
const tree = new RedBlackTree([5, 2, 8, 1, 9]);
tree.print();
// _2___
// / \
// 1 _8_
// / \
// 5 9
// Verify the tree maintains sorted order
console.log([...tree.keys()]); // [1, 2, 5, 8, 9];
// Check size
console.log(tree.size); // 5;Red-Black Tree with key-value pairs for lookups
interface Employee {
id: number;
name: string;
}
// Create tree with employee data
const employees = new RedBlackTree<number, Employee>([
[1, { id: 1, name: 'Alice' }],
[3, { id: 3, name: 'Charlie' }],
[2, { id: 2, name: 'Bob' }]
]);
// Retrieve employee by ID
const alice = employees.get(1);
console.log(alice?.name); // 'Alice';
// Verify sorted order by ID
console.log([...employees.keys()]); // [1, 2, 3];Red-Black Tree range search for filtering
interface Product {
name: string;
price: number;
}
const products = new RedBlackTree<number, Product>([
[10, { name: 'Item A', price: 10 }],
[25, { name: 'Item B', price: 25 }],
[40, { name: 'Item C', price: 40 }],
[50, { name: 'Item D', price: 50 }]
]);
// Find products in price range [20, 45]
const pricesInRange = products.rangeSearch([20, 45], node => {
return products.get(node)?.name;
});
console.log(pricesInRange); // ['Item B', 'Item C'];Red-Black Tree as database index for stock market data
interface StockPrice {
symbol: string;
volume: number;
timestamp: Date;
}
// Simulate real-time stock price index
const priceIndex = new RedBlackTree<number, StockPrice>([
[142.5, { symbol: 'AAPL', volume: 1000000, timestamp: new Date() }],
[335.2, { symbol: 'MSFT', volume: 800000, timestamp: new Date() }],
[3285.04, { symbol: 'AMZN', volume: 500000, timestamp: new Date() }],
[267.98, { symbol: 'META', volume: 750000, timestamp: new Date() }],
[234.57, { symbol: 'GOOGL', volume: 900000, timestamp: new Date() }]
]);
// Find highest-priced stock
const maxPrice = priceIndex.getRightMost();
console.log(priceIndex.get(maxPrice)?.symbol); // 'AMZN';
// Find stocks in price range [200, 400] for portfolio balancing
const stocksInRange = priceIndex.rangeSearch([200, 400], node => {
const stock = priceIndex.get(node);
return {
symbol: stock?.symbol,
price: node,
volume: stock?.volume
};
});
console.log(stocksInRange.length); // 3;
console.log(stocksInRange.some((s: any) => s.symbol === 'GOOGL')); // true;
console.log(stocksInRange.some((s: any) => s.symbol === 'META')); // true;
console.log(stocksInRange.some((s: any) => s.symbol === 'MSFT')); // true;API docs & Examples
Examples Repository