quick-avl

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.

Installation

npm install quick-avl

Performance

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) |

Usage

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}`);
}

Why another AVL library

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.