Package Exports

red-black-tree-typed
red-black-tree-typed/dist/index.js

This package does not declare an exports field, so the exports above have been automatically detected and optimized by JSPM instead. If any package subpath is missing, it is recommended to post an issue to the original package (red-black-tree-typed) to support the "exports" field. If that is not possible, create a JSPM override to customize the exports field for this package.

Readme

NPM GitHub top language npm eslint 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

npm

npm i red-black-tree-typed --save

yarn

yarn add red-black-tree-typed

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                          // 12

JS

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

using Red-Black Tree as a price-based index for stock data

    // Define the structure of individual stock records
    interface StockRecord {
      price: number; // Stock price (key for indexing)
      symbol: string; // Stock ticker symbol
      volume: number; // Trade volume
    }

    // Simulate stock market data as it might come from an external feed
    const marketStockData: StockRecord[] = [
      { price: 142.5, symbol: 'AAPL', volume: 1000000 },
      { price: 335.2, symbol: 'MSFT', volume: 800000 },
      { price: 3285.04, symbol: 'AMZN', volume: 500000 },
      { price: 267.98, symbol: 'META', volume: 750000 },
      { price: 234.57, symbol: 'GOOGL', volume: 900000 }
    ];

    // Extend the stock record type to include metadata for database usage
    type StockTableRecord = StockRecord & { lastUpdated: Date };

    // Create a Red-Black Tree to index stock records by price
    // Simulates a database index with stock price as the key for quick lookups
    const priceIndex = new RedBlackTree<number, StockTableRecord, StockRecord>(marketStockData, {
      toEntryFn: stockRecord => [
        stockRecord.price, // Use stock price as the key
        {
          ...stockRecord,
          lastUpdated: new Date() // Add a timestamp for when the record was indexed
        }
      ]
    });

    // Query the stock with the highest price
    const highestPricedStock = priceIndex.getRightMost();
    console.log(priceIndex.get(highestPricedStock)?.symbol); // 'AMZN' // Amazon has the highest price

    // Query stocks within a specific price range (200 to 400)
    const stocksInRange = priceIndex.rangeSearch(
      [200, 400], // Price range
      node => priceIndex.get(node)?.symbol // Extract stock symbols for the result
    );
    console.log(stocksInRange); // ['GOOGL', 'META', 'MSFT']

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