avl-tree-typed
Advanced tools
AVLTree(Adelson-Velsky and Landis Tree). Javascript & Typescript Data Structure.
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
npm i avl-tree-typed --save
yarn add avl-tree-typed
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
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
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 }
// ]
| Data Structure | Unit Test | Performance Test | API Docs |
|---|---|---|---|
| AVL Tree |  | | AVLTree |
| Data Structure Typed | C++ STL | java.util | Python collections |
|---|---|---|---|
| AVLTree<K, V> | - | - | - |
| test name | time taken (ms) | executions per sec | sample deviation |
|---|---|---|---|
| 10,000 add randomly | 31.32 | 31.93 | 3.67e-4 |
| 10,000 add & delete randomly | 70.90 | 14.10 | 0.00 |
| 10,000 addMany | 40.58 | 24.64 | 4.87e-4 |
| 10,000 get | 27.31 | 36.62 | 2.00e-4 |
| 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 |
| 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. |
FAQs
AVLTree(Adelson-Velsky and Landis Tree). Javascript & Typescript Data Structure.
The npm package avl-tree-typed receives a total of 19 weekly downloads. As such, avl-tree-typed popularity was classified as not popular.
We found that avl-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
Create React App is officially deprecated due to React 19 issues and lack of maintenance—developers should switch to Vite or other modern alternatives.
Security News
Oracle seeks to dismiss fraud claims in the JavaScript trademark dispute, delaying the case and avoiding questions about its right to the name.
Security News
The Linux Foundation is warning open source developers that compliance with global sanctions is mandatory, highlighting legal risks and restrictions on contributions.