BinarySearchTree

BinarySearchTree keep its keys in sorted order, so that lookup and other operations can use the principle of binary search.
This is implemented using Red-black tree. Red-black tree is a kind of self-balancing binary search tree. Each node of the binary tree has an extra bit, and that bit is often interpreted as the color (red or black) of the node. These color bits are used to ensure the tree remains approximately balanced during insertions and deletions.

Time Complexity

action	avg	worst
Insertion	O(log n)	O(log n)
Deletion	O(log n)	O(log n)
Search	O(log n)	O(log n)

Properties

size : Number

  Number of nodes in this tree.

height : Number

  Height of this tree.

root : Tree.Node

  Root node of this tree.

Methods

insert(key)

  Insert a new node with key key

tree.insert(1);

isEmpty()

  Return whether this tree hasn't any node.

contains(key)

  Return whether this tree has a node with key key.

getNode(key)

  Return the node with key key.

delete(key)

  Delete the node with key key.

bfsIterator()

  Return Iterator of Tree.Node for BFS(Breadth First Search).

dfsIterator()

  Return Iterator of Tree.Node for DFS(Depth First Search) post-order.

dfsIteratorPreOrder()

  Return Iterator of Tree.Node for DFS(Depth First Search) pre-order.

Inner classes

Tree.Node

Properties

key : *

  Key of this node. Key of node can be Number, String and anything that has 'compareTo(key)' method. This compareTo(key) method have to return 0(equal) or positive-number(bigger) or negative number(smaller).

parent : Tree.Node

  Parent of this node. Root node has null as parent.

children : Array of Tree.Node

  Children of this node. Leaf nodes have null as children.

Methods

isRoot()

  Return whether this node is a root of tree.

Example

First, Let's install @structure-js/datastructure npm-package.

npm i @structure-js/datastructure

Next, Let's create binary search tree and insert nodes to it.

let BinarySearchTree = require('@structure-js/datastructure').BinarySearchTree;

let tree = new BinarySearchTree();

tree.insert(2);
tree.insert(3);
tree.insert(1);
tree.insert(4);
tree.insert(5);
tree.insert(8);
tree.insert(9);
tree.insert(10);
tree.insert(11);
tree.insert(20);
tree.insert(15);
tree.insert(17);
tree.insert(16);
tree.insert(12);
tree.insert(13);

console.log("tree.root.key : " + tree.root.key);
console.log("tree.getMax() : " + tree.getMax());
console.log("tree.getMin() : " + tree.getMin());
console.log("tree.size : " + tree.size);

result

tree.root.key : 10
tree.getMax() : 20
tree.getMin() : 1
tree.size : 15

[Image 1]

Next, Let's delete some nodes.

tree.delete(13);
tree.delete(9);
tree.delete(1);
tree.delete(10);

console.log("tree.root.key : " + tree.root.key);
console.log("tree.getMax() : " + tree.getMax());
console.log("tree.getMin() : " + tree.getMin());
console.log("tree.size : " + tree.size);

result

tree.root.key : 11
tree.getMax() : 20
tree.getMin() : 2
tree.size : 11

[Image 2]

Let's insert custom object

let CustomObj = function (key, alias, value) {
    this.key = key;
    this.alias = alias;
    this.value = value;
}
CustomObj.prototype.compareTo = function(object){
    if(this.key === object.key){
        return 0;
    }
    return this.key > object.key ? 1: -1;
}

let tree2 = new BinarySearchTree();

tree2.insert(new CustomObj(2,"My github", "github.com/HeechanYang"));
tree2.insert(new CustomObj(3,"Js lib repo", "github.com/structure-js/datastructure"));
tree2.insert(new CustomObj(1,"Naver", "www.naver.com"));
tree2.insert(new CustomObj(4,"Google", "www.google.com"));
tree2.insert(new CustomObj(5,"Daum", "www.daum.net"));
tree2.insert(new CustomObj(8,"11번가", "www.11st.com"));
tree2.insert(new CustomObj(9,"wikipedia", "www.wikipedia.com"));
tree2.insert(new CustomObj(10,"My blog", "heechanyang.github.io"));
tree2.insert(new CustomObj(11,"firstmall", "www.firstmall.kr"));
tree2.insert(new CustomObj(20,"wix", "ko.wix.com"));
tree2.insert(new CustomObj(15,"sixshop", "www.sixshop.com/"));
tree2.insert(new CustomObj(17,"sabangnet", "www.sabangnet.co.kr/"));
tree2.insert(new CustomObj(16,"compuzone", "www.compuzone.co.kr"));
tree2.insert(new CustomObj(12,"brunch", "brunch.co.kr"));
tree2.insert(new CustomObj(13,"jaewook", "jaewook.net"));

console.log("tree.root.key.value : " + tree.root.key.value);
console.log("tree.root.key : ");
console.log(tree.root.key);
console.log("tree.getMax() : " + tree.getMax());
console.log("tree.getMin() : " + tree.getMin());
console.log("tree.size : " + tree.size);

result

tree.root.key.value : heechanyang.github.io
tree.root.key : 
CustomObj { key: 10, alias: 'My blog', value: 'heechanyang.github.io' }
tree.getMax() : [object Object]
tree.getMin() : [object Object]
tree.size : 15

[Image 3]