avl-tree-typed v2.0.3

What

Brief

This is a standalone AVL 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 avl-tree-typed --save

yarn

yarn add avl-tree-typed

snippet

TS

import {AVLTree, AVLTreeNode} from 'data-structure-typed';
// /* or if you prefer */ import {AVLTree} from 'avl-tree-typed';

const avlTree = new AVLTree<AVLTreeNode<number>>();

const idsOrVals = [11, 3, 15, 1, 8, 13, 16, 2, 6, 9, 12, 14, 4, 7, 10, 5];
avlTree.addMany(idsOrVals, idsOrVals);

const node6 = avlTree.get(6);
node6 && avlTree.getHeight(node6)           // 3
node6 && avlTree.getDepth(node6)            // 1
const getNodeById = avlTree.get(10, 'id');
getNodeById?.id                             // 10

const getMinNodeByRoot = avlTree.getLeftMost();
getMinNodeByRoot?.id                        // 1

const node15 = avlTree.get(15);
const getMinNodeBySpecificNode = node15 && avlTree.getLeftMost(node15);
getMinNodeBySpecificNode?.id                // 12

const subTreeSum = node15 && avlTree.subTreeSum(node15);
subTreeSum                                  // 70

const lesserSum = avlTree.lesserSum(10);
lesserSum                                   // 45

const node11 = avlTree.get(11);
node11?.id                                  // 11

const dfs = avlTree.DFS('in', 'node');
dfs[0].id                                   // 1 
avlTree.perfectlyBalance();
const bfs = avlTree.BFS('node');
avlTree.isPerfectlyBalanced() && bfs[0].id  // 8 

avlTree.remove(11, true)[0].deleted?.id     // 11
avlTree.isAVLBalanced();                    // true
node15 && avlTree.getHeight(node15)         // 2
avlTree.remove(1, true)[0].deleted?.id      // 1
avlTree.isAVLBalanced();                    // true
avlTree.getHeight()                         // 4

avlTree.remove(4, true)[0].deleted?.id      // 4
avlTree.isAVLBalanced();                    // true
avlTree.getHeight()                         // 4

avlTree.remove(10, true)[0].deleted?.id     // 10
avlTree.isAVLBalanced();                    // true
avlTree.getHeight()                         // 3

avlTree.remove(15, true)[0].deleted?.id     // 15
avlTree.isAVLBalanced();                    // true
avlTree.getHeight()                         // 3

avlTree.remove(5, true)[0].deleted?.id      // 5
avlTree.isAVLBalanced();                    // true
avlTree.getHeight()                         // 3

avlTree.remove(13, true)[0].deleted?.id     // 13
avlTree.isAVLBalanced();                    // true
avlTree.getHeight()                         // 3

avlTree.remove(3, true)[0].deleted?.id      // 3
avlTree.isAVLBalanced();                    // true
avlTree.getHeight()                         // 3

avlTree.remove(8, true)[0].deleted?.id      // 8
avlTree.isAVLBalanced();                    // true
avlTree.getHeight()                         // 3

avlTree.remove(6, true)[0].deleted?.id      // 6
avlTree.remove(6, true).length              // 0
avlTree.isAVLBalanced();                    // true
avlTree.getHeight()                         // 2

avlTree.remove(7, true)[0].deleted?.id      // 7
avlTree.isAVLBalanced();                    // true
avlTree.getHeight()                         // 2

avlTree.remove(9, true)[0].deleted?.id      // 9
avlTree.isAVLBalanced();                    // true
avlTree.getHeight()                         // 2

avlTree.remove(14, true)[0].deleted?.id     // 14
avlTree.isAVLBalanced();                    // true
avlTree.getHeight()                         // 1

avlTree.isAVLBalanced();                    // true
const lastBFSIds = avlTree.BFS();
lastBFSIds[0]                               // 12 

const lastBFSNodes = avlTree.BFS('node');
lastBFSNodes[0].id                          // 12

JS

const {AVLTree} = require('data-structure-typed');
// /* or if you prefer */ const {AVLTree} = require('avl-tree-typed');

const avlTree = new AVLTree();

const idsOrVals = [11, 3, 15, 1, 8, 13, 16, 2, 6, 9, 12, 14, 4, 7, 10, 5];
avlTree.addMany(idsOrVals, idsOrVals);

const node6 = avlTree.get(6);
node6 && avlTree.getHeight(node6)           // 3
node6 && avlTree.getDepth(node6)            // 1
const getNodeById = avlTree.get(10, 'id');
getNodeById?.id                             // 10

const getMinNodeByRoot = avlTree.getLeftMost();
getMinNodeByRoot?.id                        // 1

const node15 = avlTree.get(15);
const getMinNodeBySpecificNode = node15 && avlTree.getLeftMost(node15);
getMinNodeBySpecificNode?.id                // 12

const subTreeSum = node15 && avlTree.subTreeSum(node15);
subTreeSum                                  // 70

const lesserSum = avlTree.lesserSum(10);
lesserSum                                   // 45

const node11 = avlTree.get(11);
node11?.id                                  // 11

const dfs = avlTree.DFS('in', 'node');
dfs[0].id                                   // 1 
avlTree.perfectlyBalance();
const bfs = avlTree.BFS('node');
avlTree.isPerfectlyBalanced() && bfs[0].id  // 8 

avlTree.remove(11, true)[0].deleted?.id     // 11
avlTree.isAVLBalanced();                    // true
node15 && avlTree.getHeight(node15)         // 2
avlTree.remove(1, true)[0].deleted?.id      // 1
avlTree.isAVLBalanced();                    // true
avlTree.getHeight()                         // 4

avlTree.remove(4, true)[0].deleted?.id      // 4
avlTree.isAVLBalanced();                    // true
avlTree.getHeight()                         // 4

avlTree.remove(10, true)[0].deleted?.id     // 10
avlTree.isAVLBalanced();                    // true
avlTree.getHeight()                         // 3

avlTree.remove(15, true)[0].deleted?.id     // 15
avlTree.isAVLBalanced();                    // true
avlTree.getHeight()                         // 3

avlTree.remove(5, true)[0].deleted?.id      // 5
avlTree.isAVLBalanced();                    // true
avlTree.getHeight()                         // 3

avlTree.remove(13, true)[0].deleted?.id     // 13
avlTree.isAVLBalanced();                    // true
avlTree.getHeight()                         // 3

avlTree.remove(3, true)[0].deleted?.id      // 3
avlTree.isAVLBalanced();                    // true
avlTree.getHeight()                         // 3

avlTree.remove(8, true)[0].deleted?.id      // 8
avlTree.isAVLBalanced();                    // true
avlTree.getHeight()                         // 3

avlTree.remove(6, true)[0].deleted?.id      // 6
avlTree.remove(6, true).length              // 0
avlTree.isAVLBalanced();                    // true
avlTree.getHeight()                         // 2

avlTree.remove(7, true)[0].deleted?.id      // 7
avlTree.isAVLBalanced();                    // true
avlTree.getHeight()                         // 2

avlTree.remove(9, true)[0].deleted?.id      // 9
avlTree.isAVLBalanced();                    // true
avlTree.getHeight()                         // 2

avlTree.remove(14, true)[0].deleted?.id     // 14
avlTree.isAVLBalanced();                    // true
avlTree.getHeight()                         // 1

avlTree.isAVLBalanced();                    // true
const lastBFSIds = avlTree.BFS();
lastBFSIds[0]                               // 12 

const lastBFSNodes = avlTree.BFS('node');
lastBFSNodes[0].id                          // 12

Find elements in a range

    type Datum = { timestamp: Date; temperature: number };
    // Fixed dataset of CPU temperature readings
    const cpuData: Datum[] = [
      { timestamp: new Date('2024-12-02T00:00:00'), temperature: 55.1 },
      { timestamp: new Date('2024-12-02T00:01:00'), temperature: 56.3 },
      { timestamp: new Date('2024-12-02T00:02:00'), temperature: 54.8 },
      { timestamp: new Date('2024-12-02T00:03:00'), temperature: 57.2 },
      { timestamp: new Date('2024-12-02T00:04:00'), temperature: 58.0 },
      { timestamp: new Date('2024-12-02T00:05:00'), temperature: 59.4 },
      { timestamp: new Date('2024-12-02T00:06:00'), temperature: 60.1 },
      { timestamp: new Date('2024-12-02T00:07:00'), temperature: 61.3 },
      { timestamp: new Date('2024-12-02T00:08:00'), temperature: 62.0 },
      { timestamp: new Date('2024-12-02T00:09:00'), temperature: 63.5 },
      { timestamp: new Date('2024-12-02T00:10:00'), temperature: 64.0 },
      { timestamp: new Date('2024-12-02T00:11:00'), temperature: 62.8 },
      { timestamp: new Date('2024-12-02T00:12:00'), temperature: 61.5 },
      { timestamp: new Date('2024-12-02T00:13:00'), temperature: 60.2 },
      { timestamp: new Date('2024-12-02T00:14:00'), temperature: 59.8 },
      { timestamp: new Date('2024-12-02T00:15:00'), temperature: 58.6 },
      { timestamp: new Date('2024-12-02T00:16:00'), temperature: 57.4 },
      { timestamp: new Date('2024-12-02T00:17:00'), temperature: 56.2 },
      { timestamp: new Date('2024-12-02T00:18:00'), temperature: 55.7 },
      { timestamp: new Date('2024-12-02T00:19:00'), temperature: 54.5 },
      { timestamp: new Date('2024-12-02T00:20:00'), temperature: 53.2 },
      { timestamp: new Date('2024-12-02T00:21:00'), temperature: 52.8 },
      { timestamp: new Date('2024-12-02T00:22:00'), temperature: 51.9 },
      { timestamp: new Date('2024-12-02T00:23:00'), temperature: 50.5 },
      { timestamp: new Date('2024-12-02T00:24:00'), temperature: 49.8 },
      { timestamp: new Date('2024-12-02T00:25:00'), temperature: 48.7 },
      { timestamp: new Date('2024-12-02T00:26:00'), temperature: 47.5 },
      { timestamp: new Date('2024-12-02T00:27:00'), temperature: 46.3 },
      { timestamp: new Date('2024-12-02T00:28:00'), temperature: 45.9 },
      { timestamp: new Date('2024-12-02T00:29:00'), temperature: 45.0 }
    ];

    // Create an AVL tree to store CPU temperature data
    const cpuTemperatureTree = new AVLTree<Date, number, Datum>(cpuData, {
      toEntryFn: ({ timestamp, temperature }) => [timestamp, temperature]
    });

    // Query a specific time range (e.g., from 00:05 to 00:15)
    const rangeStart = new Date('2024-12-02T00:05:00');
    const rangeEnd = new Date('2024-12-02T00:15:00');
    const rangeResults = cpuTemperatureTree.rangeSearch([rangeStart, rangeEnd], node => ({
      minute: node ? node.key.getMinutes() : 0,
      temperature: cpuTemperatureTree.get(node ? node.key : undefined)
    }));

    console.log(rangeResults); //  [
 //            { minute: 5, temperature: 59.4 },
 //            { minute: 6, temperature: 60.1 },
 //            { minute: 7, temperature: 61.3 },
 //            { minute: 8, temperature: 62 },
 //            { minute: 9, temperature: 63.5 },
 //            { minute: 10, temperature: 64 },
 //            { minute: 11, temperature: 62.8 },
 //            { minute: 12, temperature: 61.5 },
 //            { minute: 13, temperature: 60.2 },
 //            { minute: 14, temperature: 59.8 },
 //            { minute: 15, temperature: 58.6 }
 //          ]

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