A Typescript implementation of an AVL tree, which is a self-balancing binary search tree.
Implements the Map interface.
Named after the inventors Adelson-Velsky and Landis, an AVL tree enforces an invariant where the heights of the subtrees of a node differ by at most one. Rebalancing is performed after each insert or remove operation, if that operation made the tree imbalanced.
npm install quick-avl
The main reason of using an AVL tree is performance. Because of its self-balancing property, worst case lookup is O(log(n)), compared to the plain binary search trees where this is O(n).
| Operation | Average time complexity | Worst case complexity |
|---|---|---|
| find | O(log n) | O(log n) |
| insert | O(log n) | O(log n) |
| remove | O(log n) | O(log n) |
| traversal | O(n) | O(n) |
This AVL tree implementation acts like a map to store key-value pairs in.
import { AvlTree } from 'quick-avl';
const users = new AvlTree<number, string>();
users.set(100, 'Bob').set(200, 'Carol').set(0, 'Alice');
users.get(100); // --> 'Bob'
users.has(100); // --> true
users.delete(200); // --> true
users.valueList(); // --> ['Alice', 'Carol']
for (const [key, value] of users) {
console.log(`Key: ${key}, value: ${value}`);
}While there are some excellent AVL libraries available within NPM, these libraries swap out tree node values while performing tree balancing. I required an AVL library that does not replace keys or values within a node. That way, a reference to a tree node will always keep the same value.