npm package discovery and stats viewer.

Discover Tips

  • General search

    [free text search, go nuts!]

  • Package details

    pkg:[package-name]

  • User packages

    @[username]

Sponsor

Optimize Toolset

I’ve always been into building performant and accessible sites, but lately I’ve been taking it extremely seriously. So much so that I’ve been building a tool to help me optimize and monitor the sites that I build to make sure that I’m making an attempt to offer the best experience to those who visit them. If you’re into performant, accessible and SEO friendly sites, you might like it too! You can check it out at Optimize Toolset.

About

Hi, 👋, I’m Ryan Hefner  and I built this site for me, and you! The goal of this site was to provide an easy way for me to check the stats on my npm packages, both for prioritizing issues and updates, and to give me a little kick in the pants to keep up on stuff.

As I was building it, I realized that I was actually using the tool to build the tool, and figured I might as well put this out there and hopefully others will find it to be a fast and useful way to search and browse npm packages as I have.

If you’re interested in other things I’m working on, follow me on Twitter or check out the open source projects I’ve been publishing on GitHub.

I am also working on a Twitter bot for this site to tweet the most popular, newest, random packages from npm. Please follow that account now and it will start sending out packages soon–ish.

Open Software & Tools

This site wouldn’t be possible without the immense generosity and tireless efforts from the people who make contributions to the world and share their work via open source initiatives. Thank you 🙏

© 2024 – Pkg Stats / Ryan Hefner

bin-trees

v1.0.4

Published

Implementation of binary search trees and red black trees

Downloads

33

Readme

Binary Search Tree(BST) and Red Black Tree(RBT) structures

Build Status Coverage Status

This is an implementation of BST and RBT using the theory explained in Introduction to Algorithms relative to this structures. This first version of the package only support numeric values for tree nodes, in future releases this can be changed and object as values can be used ;)

Example

const { createRBT } = require('bin-trees');

const newRBT = createRBT();
newRBT.insert(2);
newRBT.insert([23, -1, 4]); // the tree now has 2,23,-1,4

newRBT.contain(2); // true
newRBT.find(2); // Node Structure with 2 as key value

newRBT.remove(2).insert(10);
newRBT.contain(10); // true
newRBT.contain(2); // false

newRBT.contain(2, 10); // false,only true if the tree contain all values

newRBT.max(); // 23
newRBT.min(); // -1

API

The module exposes as main functions createBST for binary search trees creation and createRBT for red black trees as well, regardless of the type of tree created they have the same API.

Tree Creation

const { createRBT } = require('bin-trees');

// create empty tree
const emptyTree = createRBT();

// init tree with some values
const treeWithValues = createRBT(3, 2, 14);

// values can be specified using array
const anotherTree = createRBT([3, 2, 5]);

// array and values can be mixed on tree creation
const newTree = createRBT(1, [4, 5], 2, 0);

Insertion

const newTree = createRBT(4, 3, 6, 10);

newTree.insert(5); // new value inserted

newTree.insert(2, 4, 8); // inserting more than one value

newTree.insert([1, 9]); // inserting more than one value using arrays

newTree.insert(11);
newTree.insert(11); // the 11 value is just inserted one time so the tree remain unchanged

newTree.insert(20, [21, 23], 22); // here arrays and value can be missed as well

newTree
  .insert([12, 13])
  .insert(14)
  .insert(15, 16); // insert call can be chained

Deletion

const newTree = createRBT(1, 2, 3, 4, 5, 6, 7, 8, 9, 10);

newTree.remove(3); // 3 value remove from the tree;

newTree.remove(100); // nothing occur the tree remain without any change

newTree.remove(2, 4, 5); // removing various elements in one single call

newTree.remove([7, 8]); // removing various elements using array as argument

newTree
  .remove(9)
  .remove(10)
  .insert(11); // remove call can be chained

Searching

Sometimes when a search is did against the tree we receive as result a node and to get the node value we must call the getValue function to esxtract correctly the value.Search in the tree can be done using the following functions contain,find,the first return a boolean to tell if the tree contain he value and the latter return the node with the value specified or undefined if the tree not contain the value, if any of this functions is called without any argument then and error is throw.Examples:

const newTree = createBST(1, 3, 5, 7, 9, 2, 4, 6, 8, 10);

// asking if the value are in the tree

newTree.contain(3); // true
newTree.contain(100); // false

// using contain with several values only return true if all values are in the tree

newTree.contain(3, 5, 7); // true

newTree.contain(1, 2, 3, 100); // false

// retrieving nodes,check the use of getValue function

newTree.find(3).getValue(); // 3
newTree.find(100); // undefined;

//retrieving various nodes in one single call

newTree.find(1, 2, 3); // [Node(1),Node(2),Node(3)]

newTree.find(1, 35); // [Node(1)] not present values are ignored

newTree.find([4, 5]); // [Node(4),Node(5)]

newTree.find(1, [2, 3], 4, [10], 25); // [Node(1),Node(2),Node(3),Node(4)]

Max and Min values

We can know at any time the node with the max value in the tree or the node that contain the min value,if the node it not the desired result then we can know only the maximum or minimum value

const newRBT = createRBT(1, 2, 3, 4, 5, 6, 7, 8, 9, 10);

newRBT.max(); // Node 10
newRBT.min(); // Node 1

console.log(newRBT.maxValue()); // print 10
console.log(newRBT.minValue()); // print 1

Iteration

Every tree has a function iterator that can be used to build a iterator from the tree, when this new iterator is consumed the tree values are returned in order

const newTree = createRBT(1, 2, 3);
const iterator = newTree.iterator();

console.log(iterator.next()); // {value: 1,done: false};
console.log(iterator.next()); // {value: 2,done: false};
console.log(iterator.next()); // {value: 3,done: false};
console.log(iterator.next()); // {value: undefined,done: true};

// if we call next again when the iterator has finished the same object is returned
console.log(iterator.next()); // {value: undefined,done: true};

The tree also implement the especial Symbol.iterator so it can be used with any of the standard consumer that used this symbol

 const newTree = createRBT(1,2,3);

 // the following for print the tree values in order
 for(let value of newTree){
   console.log(value);
 }

Array like methods

Reduce

We can use reduce over one tree created just like we do with standard arrays:

  const newTree = createRBT(1,2,3,4,5);

  const sum = (acc,val) => acc + val;
  const product = (acc,val) => acc * val;

  const treeTotal = newTree.reduce(sum);
  const treeFactorial = newTree.reduce(product);

  console.log(treeTotal); // 15
  console.log(treeFactorial); // 120

Filter

The filter function is also available, this function is similar to the filter function of the arrays with the difference that a new tree is not created after the filtering process but the existing tree is modified:

  const newTree = createRBT(4, 10, 3, 11, 2, 6, 1, 9);
  newTree.filter(v => v % 2 === 0 && v % 3 === 0); // after this the tree only has the value 6
  newTree.filter(v => v === 1); // now the tree is empty