red-black-tree-typed v2.0.3

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

Standard library data structure comparison

Benchmark

Built-in classic algorithms

Software Engineering Design Standards