@tyriar/avl-tree
TypeScript icon, indicating that this package has built-in type declarations

2.0.6 • Public • Published

ts-avl-tree

Build Status Coverage Status

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)

Package Sidebar

Install

npm i @tyriar/avl-tree

Weekly Downloads

5

Version

2.0.6

License

MIT

Unpacked Size

39.9 kB

Total Files

10

Last publish

Collaborators

  • tyriar