quick-avl

quick-avl

A Typescript implementation of an AVL tree, which is a self-balancing binary search tree.

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.insert(100, 'Bob'); // --> AvlTreeNode
users.insert(200, 'Carol'); // --> AvlTreeNode
users.insert(0, 'Alice'); // --> AvlTreeNode

users.find(100); // --> 'Bob'
users.contains(100); // --> true

users.remove(200); // --> true

users.values(); // --> ['Alice', 'Carol']

for (const node of users) {
  console.log(`Key: ${node.key}, value: ${node.value}`);
}