Detalhes do pacote

avl-tree-typed

zrwusa598MIT2.0.3

Standard AVL tree

avl, AVL, tree, Tree

readme (leia-me)

NPM GitHub top language npm eslint npm bundle size npm bundle size npm

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

Data Structure Unit Test Performance Test API Docs
AVL Tree AVLTree

Standard library data structure comparison

Data Structure Typed C++ STL java.util Python collections
AVLTree<K, V> - - -

Benchmark

avl-tree
test nametime taken (ms)executions per secsample deviation
10,000 add randomly31.3231.933.67e-4
10,000 add & delete randomly70.9014.100.00
10,000 addMany40.5824.644.87e-4
10,000 get27.3136.622.00e-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.