Red-black-tree-js NPM

A javascript implementation of red-black-tree using ES6

npm link

https://www.npmjs.com/package/red-black-tree-js

npm install

npm i red-black-tree-js

Thanks for using it!

usage

import RbTree from "red-black-tree-js"


const rbTree = new RbTree();
rbTree.insert(1, "foo");
rbTree.insert(2, "bar");
rbTree.insert(3, "bar");
rbTree.insert(4, "bar");
rbTree.insert(5, "bar");
rbTree.insert(6, "bar");
rbTree.remove(6);

const iterator = rbTree.createIterator();

let result = [];
while (iterator.hasNext()) {
  result.push(iterator.next());
}

Reference

https://www.cs.usfca.edu/~galles/visualization/RedBlack.html visualization
https://en.wikipedia.org/wiki/Red%E2%80%93black_tree wiki

OverView

data structure

nodeColor	value
BLACK	1
RED	0

Node	LeafNode
left	left(null)
right	right(null)
parent	parent(null)
key	key(null)
value	value(null)
color	color(black)

API

create RB TREE
let rbTree = new RbTree()
create a red black tree with root = null
find

  const rbTree = new RbTree();
  rbTree.insert(1, "foo");
  rbTree.insert(2, "bar");
  rbTree.insert(3, "bar");
  const value = rbTree.find(2);

  value is "bar"
  Look up value by it's key

iterator() return the next smallest number

  rbTree.insert(30, "abc");
  rbTree.insert(20, "foo");
  rbTree.insert(40, "bar");
  rbTree.insert(10, "bar");
  const iterator = rbTree.createIterator();

  let result = [];
  while (iterator.hasNext()) {
    result.push(iterator.next());
  }

findNode(key)

  const rbTree = new RbTree();
  rbTree.insert(1, "foo");
  rbTree.insert(2, "bar");
  rbTree.insert(3, "bar");
  const node = rbTree.findNode(2);

  return the node object

update(key, value)

  const rbTree = new RbTree();
  rbTree.insert(1, "foo");
  rbTree.insert(2, "bar");

  rbTree.update(2, "updated")

  now the value is "updated"

insert(key, value)
rbTree.insert(1, "abc") insert a key and a value to a node
remove(key)
rbTree.remove(1)
remove a node by its key
print()

   rbTree.insert(30, "abc");
   rbTree.insert(20, "foo");
   rbTree.insert(40, "bar");
   rbTree.insert(10, "bar");
   rbTree.print();

   30 color: 1
   ___20 color: 0 (parent node 30)
   ___40 color: 0 (parent node 30)
   ______null color: 1 (parent node 20)
   ______null color: 1 (parent node 20)
   ______null color: 1 (parent node 40)
   ______null color: 1 (parent node 40)

print out the current tree in a good format

inOrderSucc(node)

  const rbTree = new RbTree();
  rbTree.insert(2, "foo");
  rbTree.insert(1, "bar");
  rbTree.insert(3, "bar");

  let next = rbTree.inOrderSucc(rbTree.root)
  console.log(next)
  {key : 3, value: "bar"}

toSortedArray()

  const rbTree = new RbTree();
  rbTree.insert(1, "foo");
  rbTree.insert(2, "bar");
  rbTree.insert(3, "bar");
  const array = rbTree.toSortedArray();

  array is [Object, Object, Object]
  return a sorted array of objects that contains key and value

toArrayPreOrder()

  const rbTree = new RbTree();
  rbTree.insert(3, "abc");
  rbTree.insert(4, "abc");
  rbTree.insert(1, "foo");
  rbTree.insert(0, "bar");
  rbTree.insert(2, "bar");
  const array = rbTree.toArrayPreOrder();

  array is [Object, Object, Object, Object, Object]
  return an array of objects that contains key and value
  the key order is [3, 1, 0, 2, 4]

toArrayPostOrder()

  const rbTree = new RbTree();
  rbTree.insert(3, "abc");
  rbTree.insert(4, "abc");
  rbTree.insert(1, "foo");
  rbTree.insert(0, "bar");
  rbTree.insert(2, "bar");
  const array = rbTree.toArrayPostOrder();

  array is [Object, Object, Object, Object, Object]
  the key order is [0, 2, 1, 4, 3]
  return an array of objects that contains key and value

minNode()

  const rbTree = new RbTree();
  rbTree.insert(1, "foo");
  rbTree.insert(2, "bar");
  rbTree.insert(3, "bar");
  const node = rbTree.minNode();

  node is Object {key: 1, value: "foo"}
  return the smallest node value in the tree

maxNode()

  const rbTree = new RbTree();
  rbTree.insert(1, "foo");
  rbTree.insert(2, "bar");
  rbTree.insert(3, "bar");
  const node = rbTree.maxNode();

  node is Object {key: 3, value: "bar"}
  return the largest node value in the tree

The tree structure now support inserting string as keys .

For example:

letter 'a' will be treated as 1
letter 'b' will be treated as 2
letter 'b' will be treated as 3
letter 'A' will be treated as 1 as well
letter 'B' will be treated as 2 as well
letter 'C' will be treated as 3 as well
a string like "abc" will be treated as 123
a string like "Abc" will be treated as 123
a string like "dc" will be treated as 41

  rbTree.insert("id", 1001) => rbTree.insert(94, 1001);
  rbTree.insert("a", "foo") => rbTree.insert(1, "foo");  
  rbTree.insert("Am", "bar")=> rbTree.insert(113, "foo");  
  rbTree.insert("boy", "foo") => rbTree.insert(21525, "foo");