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

@justlep/binary-search-tree

v1.0.2

Published

Different binary search tree implementations, including a self-balancing one (AVL)

Downloads

9

Readme

Binary search trees for Node.js

Build Status

This is a cleaned up and modernized fork of node-binary-search-tree, provided as ES module. Written primarily to store indexes for NeDB (a javascript dependency-less database).

  • Node.js 14.17.6+
  • no dependencies

Two implementations of binary search tree: basic and AVL (a kind of self-balancing binary search tree).

Installation

npm install @justlep/binary-search-tree --save

Usage

The API mainly provides 3 functions: insert, search and delete. If you do not create a unique-type binary search tree, you can store multiple pieces of data for the same key. Doing so with a unique-type BST will result in an error being thrown. Data is always returned as an array, and you can delete all data relating to a given key, or just one piece of data.

Values inserted can be anything except undefined.

import {BinarySearchTree, AVLTree} from '@justlep/binary-search-tree';

// Creating a binary search tree
const bst = new BinarySearchTree();

// Inserting some data
bst.insert(15, 'some data for key 15');
bst.insert(12, 'something else');
bst.insert(18, 'hello');

// You can insert multiple pieces of data for the same key
// if your tree doesn't enforce a unique constraint
bst.insert(18, 'world');

// Retrieving data (always returned as an array of all data stored for this key)
bst.search(15);   // Equal to ['some data for key 15']
bst.search(18);   // Equal to ['hello', 'world']
bst.search(1);    // Equal to []

// Search between bounds with a MongoDB-like query
// Data is returned in key order
// Note the difference between $lt (less than) and $gte (less than OR EQUAL)
bst.betweenBounds({ $lt: 18, $gte: 12});   // Equal to ['something else', 'some data for key 15']

// Deleting all the data relating to a key
bst.delete(15);   // bst.search(15) will now give []
bst.delete(18, 'world');   // bst.search(18) will now give ['hello']

There are three optional parameters you can pass the BST constructor, allowing you to enforce a key-uniqueness constraint, use a custom function to compare keys and use a custom function to check whether values are equal. These parameters are all passed in an object.

Uniqueness

const bst = new BinarySearchTree({unique: true});
bst.insert(10, 'hello');
bst.insert(10, 'world');   // Will throw an error

Custom key comparison

/**
 * Custom key comparison function for age keys.
 * @param {Object} a
 * @param {Object} b
 * @return {number} - 0 / 1 / -1
 */
function compareKeys(a, b) {
  return (a.age > b.age) ? 1 : (a.age < b.age) ? -1 : 0;
}

// Now we can use objects with an 'age' property as keys
const bst = new BinarySearchTree({ compareKeys });
bst.insert({ age: 23 }, 'Mark');
bst.insert({ age: 47 }, 'Franck');

If no custom key comparison function is provided to the constructor, the default one can compare numbers, dates and strings which are the most common usecases

Custom value checking

// Custom value equality checking function used when we try to just delete one piece of data
// Returns true if a and b are considered the same, false otherwise
// The default function is able to compare numbers and strings
function checkValueEquality (a, b) {
  return a.length === b.length;
}
const bst = new BinarySearchTree({ checkValueEquality });
bst.insert(10, 'hello');
bst.insert(10, 'world');
bst.insert(10, 'howdoyoudo');

bst.delete(10, 'abcde');
bst.search(10);   // Returns ['howdoyoudo']

License

MIT