A JavaScript implementation of the AVL tree data structure.
- 100% test coverage
- Supports all common tree operations
npm install --save @tyriar/avl-tree// Import npm module
var AvlTree = require('@tyriar/avl-tree');
// Construct AvlTree
var tree = new AvlTree();
// 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
tree = new AvlTree(function (a, b) {
return a.localeCompare(b);
});
tree.insert('a');
tree.insert('A');
tree.insert('b');
tree.insert('B');
// Delete the minimum key
var minKey = tree.findMinimum();
tree.delete(minKey);
console.log('minKey: ' + minKey);
console.log('new minKey: ' + tree.findMinimum());
// > min key: 'a'
// > new min key: 'A'| 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) |
Creates a new AVL Tree.
Parameters
customComparefunction An optional custom compare function.
Gets whether a node with a specific key is within the tree.
Parameters
keyObject The key being searched for.
Returns boolean Whether a node with the key exists.
Deletes a node with a specific key from the tree.
Parameters
keyObject The key being deleted.
Returns Object The maximum key in the tree.
Returns Object The minimum key in the tree.
Gets the value of a node within the tree with a specific key.
Parameters
keyObject The key being searched for.
Returns Object The value of the node or null if it doesn't exist.
Inserts a new node with a specific key into the tree.
Parameters
keyObject The key being inserted.valueObject The value being inserted.
Returns boolean Whether the tree is empty.
Returns number The size of the tree.