Package Exports

@datastructures-js/binary-search-tree

This package does not declare an exports field, so the exports above have been automatically detected and optimized by JSPM instead. If any package subpath is missing, it is recommended to post an issue to the original package (@datastructures-js/binary-search-tree) to support the "exports" field. If that is not possible, create a JSPM override to customize the exports field for this package.

Readme

@datastructures-js/binary-search-tree

Binary Search Tree & AVL Tree (Self Balancing Tree) implementation in javascript.

Binary Search Tree

AVL Tree (Self Balancing Tree)

Install
API
Build
License

install

npm install --save @datastructures-js/binary-search-tree

API

require

Both trees have the same interface except that AVL tree will maintain itself balance due to rotating nodes that becomes unbalanced on insertion and deletion. If your code requires a strictly balanced tree that always benefits from the log(n) runtime of insert & remove, you should use AVL.

const { BinarySearchTree, AvlTree } = require('@datastructures-js/binary-search-tree');

import

import { BinarySearchTree } from '@datastructures-js/binary-search-tree';

Create a Tree

const bst = new BinarySearchTree();

// OR a self balancing tree

const bst = new AvlTree();

.insert(key, value)

inserts a node with key/value into the tree. Inserting an node with existing key, would update the existing node's value with the new inserted one. AVL tree will rotate nodes properly if the tree becomes unbalanced with the insertion.

runtime	params	return
O(log(n))	key: {number} or {string} value: {object}	{BinarySearchTreeNode} for BinarySearchTree .getKey() {number\|string} returns the node's key that is used to compare with other nodes. .setValue(value) change the value that is associated with a node. .getValue() {object} returns the value that is associated with a node. .getLeft() {BinarySearchTreeNode} returns node's left child node. .getRight() {BinarySearchTreeNode} returns node's right child node. .getParent() {BinarySearchTreeNode} returns node's parent node. {AvlTreeNode} for AvlTree. It extends the BinarySearchTreeNode and adds the following methods: .getHeight() {number} the height of the node in the tree. root is 1. .getLeftHeight() {number} the height of the left child. 0 if no left child. .getRightHeight() {number} the height of the right child. 0 if no right child.

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.

runtime	params	return
O(log(n))	key: {number} or {string}	{boolean}

bst.has(50); // true
bst.has(100); // false

.find(key)

finds a node in the tree by its key.

runtime	params	return
O(log(n))	key: {number} or {string}	{BinarySearchTreeNode} for BinarySearchTree {AvlTreeNode} for AvlTree

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.

runtime	return
O(log(n))	{BinarySearchTreeNode} for BinarySearchTree {AvlTreeNode} for AvlTree

const min = bst.min();
console.log(min.getKey()); // 20
console.log(min.getValue()); // v7

.max()

finds the node with max key in the tree.

runtime	return
O(log(n))	{BinarySearchTreeNode} for BinarySearchTree {AvlTreeNode} for AvlTree

const max = bst.max();
console.log(max.getKey()); // 90
console.log(max.getValue()); // v4

.root()

returns the root node of the tree.

runtime	return
O(1)	{BinarySearchTreeNode} for BinarySearchTree {AvlTreeNode} for AvlTree

const root = bst.root();
console.log(root.getKey()); // 50
console.log(root.getValue()); // v1

.count()

returns the count of nodes in the tree.

runtime	return
O(1)	{number}

console.log(bst.count()); // 7

.traverseInOrder(cb)

traverses the tree in order (left-node-right).

runtime	param
O(n)	cb: {function}

bst.traverseInOrder((node) => console.log(node.getKey()));

/*
20
30
40
50
60
80
90
*/

.traversePreOrder(cb)

traverses the tree pre order (node-left-right).

runtime	param
O(n)	cb: {function}

bst.traversePreOrder((node) => console.log(node.getKey()));

/*
50
30
20
40
80
60
90
*/

.traversePostOrder(cb)

traverses the tree post order (left-right-node).

runtime	param
O(n)	cb: {function}

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 with the deletion.

runtime	params	return
O(log(n))	key: {number} or {string}	{boolean}

bst.remove(20); // true
bst.remove(100); // false
console.log(bst.count()); // 6

.clear()

clears the tree.

runtime
O(1)

bst.clear();
console.log(bst.count()); // 0
console.log(bst.root()); // null

Build

grunt build

License

The MIT License. Full License is here