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