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 --save
yarn
yarn add red-black-tree-typed
methods
snippet
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 // 12API docs & Examples
API Docs
Live Examples
Examples Repository
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
rb-tree
| 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 |
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. |
