| test name | time taken (ms) | executions per sec | sample deviation |
|---|---|---|---|
| 100,000 add | 85.85 | 11.65 | 0.00 |
| 100,000 add & delete randomly | 211.54 | 4.73 | 0.00 |
| 100,000 getNode | 37.92 | 26.37 | 1.65e-4 |
red-black-tree-typed
v2.2.8TypeScript
red black tree
red blacktreered black treered-black-treeredblacktreered black tree data structureself-balancingselfbalancingselfbalanceself balance
124/weekUpdated 1 weeks agoMITUnpacked: 4.6 MB
Published by Pablo Zeng zrwusa@gmail.com
npm install red-black-tree-typed!NPM
!GitHub top language
!npm
!eslint
!npm bundle size
!npm bundle size
!npm
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
$3
``bash`
npm i red-black-tree-typed --save
$3
`bash`
yarn add red-black-tree-typed
$3
#### TS
`typescript
import {RedBlackTree} from 'data-structure-typed';
// / or if you prefer / import {RedBlackTree} from '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);
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 // 12
`
#### JS
`javascript
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 // 12
`
[//]: # (No deletion!!! Start of Example Replace Section)
$3
`
typescript
// 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;
`$3
typescript
interface Employee {
id: number;
name: string;
} // Create tree with employee data
const employees = new RedBlackTree([
[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];
`$3
typescript
interface Product {
name: string;
price: number;
} const products = new RedBlackTree([
[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'];
`$3
typescript
interface StockPrice {
symbol: string;
volume: number;
timestamp: Date;
} // Simulate real-time stock price index
const priceIndex = new RedBlackTree([
[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;
``[//]: # (No deletion!!! End of Example Replace Section)
API docs & Examples
Data Structures
| Data Structure | Unit Test | Performance Test | API Docs |
|---|---|---|---|
| Red Black Tree |  | | RedBlackTree |
Standard library data structure comparison
| Data Structure Typed | C++ STL | java.util | Python collections |
|---|---|---|---|
| RedBlackTree<K, V> | map<K, V> | TreeMap<K, V> | - |
Benchmark
[//]: # (No deletion!!! Start of Replace Section)
rb-tree
[//]: # (No deletion!!! End of Replace Section)
Built-in classic algorithms
| Algorithm | Function Description | Iteration Type |
|---|---|---|
| Binary Tree DFS | Traverse a binary tree in a depth-first manner, starting from the root node, first visiting the left subtree, and then the right subtree, using recursion. | Recursion + Iteration |
| Binary Tree BFS | Traverse a binary tree in a breadth-first manner, starting from the root node, visiting nodes level by level from left to right. | Iteration |
| Binary Tree Morris | Morris traversal is an in-order traversal algorithm for binary trees with O(1) space complexity. It allows tree traversal without additional stack or recursion. | Iteration |
Software Engineering Design Standards
| Principle | Description |
|---|---|
| Practicality | Follows ES6 and ESNext standards, offering unified and considerate optional parameters, and simplifies method names. |
| Extensibility | Adheres to OOP (Object-Oriented Programming) principles, allowing inheritance for all data structures. |
| Modularization | Includes data structure modularization and independent NPM packages. |
| Efficiency | All methods provide time and space complexity, comparable to native JS performance. |
| Maintainability | Follows open-source community development standards, complete documentation, continuous integration, and adheres to TDD (Test-Driven Development) patterns. |
| Testability | Automated and customized unit testing, performance testing, and integration testing. |
| Portability | Plans for porting to Java, Python, and C++, currently achieved to 80%. |
| Reusability | Fully decoupled, minimized side effects, and adheres to OOP. |
| Security | Carefully designed security for member variables and methods. Read-write separation. Data structure software does not need to consider other security aspects. |
| Scalability | Data structure software does not involve load issues. |