@tyriar/avl-tree

ts-avl-tree

A TypeScript implementation of the AVL tree data structure.

Note that the primary purpose of this library is education but it should work in a production environment as well. It's certainly not as performant as it could be as it optimises for readability, abstraction and safety over raw performance.

Features

• 100% test coverage
• Supports all common tree operations
• Store keys with optional associated values
• Optional custom compare function that can utilize both key and value to give full control over the order of the data

Install

npm install --save @tyriar/avl-tree

Usage

See the typings file for the full API.

// Import npm module
import { AvlTree } from '@tyriar/avl-tree';

// Construct AvlTree
const tree = new AvlTree<number, number>();

// Insert keys
tree.insert(1);
tree.insert(2);
tree.insert(3);
tree.insert(4);
tree.insert(5);
console.log('size: ' + tree.size);
console.log('contains 2: ' + tree.contains(2));
console.log('contains 7: ' + tree.contains(7));
// > size: 5
// > contains 2: true
// > contains 7: false

// Delete a key
tree.delete(2);
console.log('size: ' + tree.size);
console.log('contains 2: ' + tree.contains(2));
// > size: 4
// > contains 2: false

// Construct custom compare AvlTree
const tree2 = new AvlTree<string, string>(function (a, b) {
  return a.localeCompare(b);
});
tree2.insert('a');
tree2.insert('A');
tree2.insert('b');
tree2.insert('B');

// Delete the minimum key
const minKey = tree2.findMinimum();
tree2.delete(minKey);
console.log('minKey: ' + minKey);
console.log('new minKey: ' + tree2.findMinimum());
// > min key: 'a'
// > new min key: 'A'

Operation time complexity

Operation	Complexity
contains	O(log n)
delete	O(log n)
findMaximum	O(log n)
findMinimum	O(log n)
get	O(log n)
insert	O(log n)
isEmpty	Θ(1)
size	Θ(1)