red-black-tree-typed
Advanced tools
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
npm i red-black-tree-typed --save
yarn add red-black-tree-typed
import {RedBlackTree, RedBlackTreeNode} from 'data-structure-typed';
// /* or if you prefer */ import {RedBlackTree} from 'red-black-tree-typed';
const rbTree = new RedBlackTree<RedBlackTreeNode<number>>();
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.get(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.get(15);
const getMinNodeBySpecificNode = node15 && rbTree.getLeftMost(node15);
getMinNodeBySpecificNode?.id // 12
const subTreeSum = node15 && rbTree.subTreeSum(node15);
subTreeSum // 70
const lesserSum = rbTree.lesserSum(10);
lesserSum // 45
const node11 = rbTree.get(11);
node11?.id // 11
const dfs = rbTree.dfs('in', 'node');
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
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.get(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.get(15);
const getMinNodeBySpecificNode = node15 && rbTree.getLeftMost(node15);
getMinNodeBySpecificNode?.id // 12
const subTreeSum = node15 && rbTree.subTreeSum(node15);
subTreeSum // 70
const lesserSum = rbTree.lesserSum(10);
lesserSum // 45
const node11 = rbTree.get(11);
node11?.id // 11
const dfs = rbTree.DFS('in', 'node');
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
| Data Structure | Unit Test | Performance Test | API Documentation | Implemented |
|---|---|---|---|---|
| Binary Tree | 
|
| Binary Tree | |
| Binary Search Tree (BST) | | | BST | |
| Red Black Tree | | | RedBlackTree | |
| Tree Multiset | | | TreeMultimap | |
| Segment Tree | SegmentTree | | ||
| Binary Indexed Tree | | BinaryIndexedTree | | |
| Graph | | | AbstractGraph | |
| Directed Graph | | | DirectedGraph | |
| Undirected Graph | | | UndirectedGraph | |
| Linked List | | | SinglyLinkedList | |
| Singly Linked List | | | SinglyLinkedList | |
| Doubly Linked List | | | DoublyLinkedList | |
| Queue | | | Queue | |
| Object Deque | | | ObjectDeque | |
| Array Deque | | | ArrayDeque | |
| Stack | | Stack | | |
| Coordinate Set | CoordinateSet | | ||
| Coordinate Map | CoordinateMap | | ||
| Heap | | | Heap | |
| Priority Queue | | | PriorityQueue | |
| Max Priority Queue | | | MaxPriorityQueue | |
| Min Priority Queue | | | MinPriorityQueue | |
| Trie | | Trie | |
| Big O Notation | Type | Computations for 10 elements | Computations for 100 elements | Computations for 1000 elements |
|---|---|---|---|---|
| O(1) | Constant | 1 | 1 | 1 |
| O(log N) | Logarithmic | 3 | 6 | 9 |
| O(N) | Linear | 10 | 100 | 1000 |
| O(N log N) | n log(n) | 30 | 600 | 9000 |
| O(N^2) | Quadratic | 100 | 10000 | 1000000 |
| O(2^N) | Exponential | 1024 | 1.26e+29 | 1.07e+301 |
| O(N!) | Factorial | 3628800 | 9.3e+157 | 4.02e+2567 |
| Data Structure | Access | Search | Insertion | Deletion | Comments |
|---|---|---|---|---|---|
| Array | 1 | n | n | n | |
| Stack | n | n | 1 | 1 | |
| Queue | n | n | 1 | 1 | |
| Linked List | n | n | 1 | n | |
| Hash Table | - | n | n | n | In case of perfect hash function costs would be O(1) |
| Binary Search Tree | n | n | n | n | In case of balanced tree costs would be O(log(n)) |
| B-Tree | log(n) | log(n) | log(n) | log(n) | |
| Red-Black Tree | log(n) | log(n) | log(n) | log(n) | |
| Red Black Tree | log(n) | log(n) | log(n) | log(n) | |
| Bloom Filter | - | 1 | 1 | - | False positives are possible while searching |
| Name | Best | Average | Worst | Memory | Stable | Comments |
|---|---|---|---|---|---|---|
| Bubble sort | n | n2 | n2 | 1 | Yes | |
| Insertion sort | n | n2 | n2 | 1 | Yes | |
| Selection sort | n2 | n2 | n2 | 1 | No | |
| Heap sort | n log(n) | n log(n) | n log(n) | 1 | No | |
| Merge sort | n log(n) | n log(n) | n log(n) | n | Yes | |
| Quick sort | n log(n) | n log(n) | n2 | log(n) | No | Quicksort is usually done in-place with O(log(n)) stack space |
| Shell sort | n log(n) | depends on gap sequence | n (log(n))2 | 1 | No | |
| Counting sort | n + r | n + r | n + r | n + r | Yes | r - biggest number in array |
| Radix sort | n * k | n * k | n * k | n + k | Yes | k - length of longest key |
FAQs
RedBlackTree. Javascript & Typescript Data Structure.
The npm package red-black-tree-typed receives a total of 20 weekly downloads. As such, red-black-tree-typed popularity was classified as not popular.
We found that red-black-tree-typed demonstrated a healthy version release cadence and project activity because the last version was released less than a year ago. It has 0 open source maintainers collaborating on the project.
Did you know?
Socket for GitHub automatically highlights issues in each pull request and monitors the health of all your open source dependencies. Discover the contents of your packages and block harmful activity before you install or update your dependencies.
Security News
Ransomware payment rates hit an all-time low in 2024 as law enforcement crackdowns, stronger defenses, and shifting policies make attacks riskier and less profitable.
Security News
require(esm) backported to Node.js 20, easing the transition to ESM-only packages and reducing complexity for developers as Node 18 nears end-of-life.
Security News
PyPI now supports iOS and Android wheels, making it easier for Python developers to distribute mobile packages.