@datastructures-js/binary-search-tree
Binary Search Tree & AVL Tree (Self Balancing Tree) implementation in javascript.
Binary Search Tree |
|
AVL Tree (Self Balancing Tree) |
|
Contents
install
npm install --save @datastructures-js/binary-search-tree
require
const {
BinarySearchTree,
BinarySearchTreeNode,
AvlTree,
AvlTreeNode
} = require('@datastructures-js/binary-search-tree');
import
import {
BinarySearchTree,
BinarySearchTreeNode,
AvlTree,
AvlTreeNode
} from '@datastructures-js/binary-search-tree';
API
constructor
JS
const bst = new BinarySearchTree();
// self balancing tree
const bst = new AvlTree();
TS
// BinarySearchTree<T extends number|string, U = undefined>
const bst = new BinarySearchTree<number, string>();
// AvlTree<T extends number|string, U = undefined>
const bst = new AvlTree<number, { id: string, count: number }>();
.insert(key[, value])
inserts a node with key/value into the tree and returns the inserted node. Inserting an node with existing key, will update the existing node's value with the new one.
bst.insert(50, 'v1');
bst.insert(80, 'v2');
bst.insert(30, 'v3');
bst.insert(90, 'v4');
bst.insert(60, 'v5');
bst.insert(40, 'v6');
bst.insert(20, 'v7');
.has(key)
checks if a node exists by its key.
params |
return |
runtime |
key: T (number | string)
|
boolean |
O(log(n)) |
bst.has(50); // true
bst.has(100); // false
.find(key)
finds a node in the tree by its key.
const n60 = bst.find(60);
console.log(n60.getKey()); // 60
console.log(n60.getValue()); // v5
console.log(bst.find(100)); // null
.min()
finds the node with min key in the tree.
const min = bst.min();
console.log(min.getKey()); // 20
console.log(min.getValue()); // v7
.max()
finds the node with max key in the tree.
const max = bst.max();
console.log(max.getKey()); // 90
console.log(max.getValue()); // v4
.lowerBound(k[, includeEqual]) (.floor)
finds the node with the biggest key less or equal a given value k. You can eliminate equal keys by passing second param as false. .floor
is a delegate to the same function.
console.log(bst.lowerBound(60).getKey()); // 60
console.log(bst.lowerBound(60, false).getKey()); // 50
console.log(bst.lowerBound(10)); // null
.upperBound(k[, includeEqual]) (.ceil)
finds the node with the smallest key bigger or equal a given value k. You can eliminate equal keys by passing second param as false. .ceil
is a delegate to the same function.
console.log(bst.upperBound(75).getKey()); // 80
console.log(bst.upperBound(80).getKey()); // 80
console.log(bst.upperBound(80, false).getKey()); // 90
console.log(bst.upperBound(110)); // null
.root()
returns the root node of the tree.
const root = bst.root();
console.log(root.getKey()); // 50
console.log(root.getValue()); // v1
.count()
returns the count of nodes in the tree.
return |
runtime |
number |
O(1) |
console.log(bst.count()); // 7
.traverseInOrder(cb)
traverses the tree in order (left-node-right).
bst.traverseInOrder((node) => console.log(node.getKey()));
/*
20
30
40
50
60
80
90
*/
.traversePreOrder(cb)
traverses the tree pre order (node-left-right).
bst.traversePreOrder((node) => console.log(node.getKey()));
/*
50
30
20
40
80
60
90
*/
.traversePostOrder(cb)
traverses the tree post order (left-right-node).
bst.traversePostOrder((node) => console.log(node.getKey()));
/*
20
40
30
60
90
80
50
*/
.remove(key)
removes a node from the tree by its key. AVL tree will rotate nodes properly if the tree becomes unbalanced during deletion.
params |
return |
runtime |
key: T |
boolean |
O(log(n)) |
bst.remove(20); // true
bst.remove(100); // false
console.log(bst.count()); // 6
.clear()
clears the tree.
bst.clear();
console.log(bst.count()); // 0
console.log(bst.root()); // null
BinarySearchTreeNode<T, U>
.getKey()
return |
T (number | string) |
.setValue(value)
.getValue()
.setLeft(left)
.getLeft()
.hasLeft()
.setRight(right)
.getRight()
.hasRight()
.setParent(parent)
.getParent()
.hasParent()
.isLeaf()
.isRoot()
AvlTreeNode<T, U>
extends BinarySearchTreeNode<T, U> and adds the following methods:
.rotateLeft()
Rotates self left (counter-clockwise).
.rotateRight()
Rotates self right (clockwise).
.rotateLeftRight()
Rotates left child to left then self to right.
.rotateRightLeft()
Rotates right child to right then self to left.
.getHeight()
Gets the height of the node in the tree. root height is 1.
.getLeftHeight()
Gets the height of left child. 0 if no left child.
.getRightHeight()
Gets the height of right child. 0 if no right child.
.getBalance()
returns the node's balance as the diff between left and right heights.
.isBalanced()
checks if the node is balanced. (height diff is not more/less than 1/-1)
Build
grunt build
License
The MIT License. Full License is here