Security News
Fluent Assertions Faces Backlash After Abandoning Open Source Licensing
Fluent Assertions is facing backlash after dropping the Apache license for a commercial model, leaving users blindsided and questioning contributor rights.
@seald-io/binary-search-tree
Advanced tools
Different binary search tree implementations, including a self-balancing one (AVL)
@seald-io/binary-search-tree is an npm package that provides a simple and efficient implementation of a binary search tree (BST) data structure. It allows for the storage, retrieval, and manipulation of data in a sorted manner, making it useful for various applications such as searching, sorting, and maintaining a dynamic set of ordered elements.
Insertion
This feature allows you to insert key-value pairs into the binary search tree. The keys are used to maintain the order of the elements, and the values are the data associated with those keys.
const { BinarySearchTree } = require('@seald-io/binary-search-tree');
const bst = new BinarySearchTree();
bst.insert(10, 'value1');
bst.insert(5, 'value2');
bst.insert(15, 'value3');
console.log(bst.search(10)); // Outputs: 'value1'
Search
This feature allows you to search for a value associated with a given key in the binary search tree. If the key exists, the corresponding value is returned.
const { BinarySearchTree } = require('@seald-io/binary-search-tree');
const bst = new BinarySearchTree();
bst.insert(10, 'value1');
bst.insert(5, 'value2');
bst.insert(15, 'value3');
console.log(bst.search(5)); // Outputs: 'value2'
Deletion
This feature allows you to delete a key-value pair from the binary search tree. After deletion, the key will no longer exist in the tree.
const { BinarySearchTree } = require('@seald-io/binary-search-tree');
const bst = new BinarySearchTree();
bst.insert(10, 'value1');
bst.insert(5, 'value2');
bst.insert(15, 'value3');
bst.delete(10);
console.log(bst.search(10)); // Outputs: null
Traversal
This feature allows you to traverse the binary search tree in order. The inOrderTraversal method visits all nodes in ascending order of their keys, applying a callback function to each key-value pair.
const { BinarySearchTree } = require('@seald-io/binary-search-tree');
const bst = new BinarySearchTree();
bst.insert(10, 'value1');
bst.insert(5, 'value2');
bst.insert(15, 'value3');
bst.inOrderTraversal((key, value) => {
console.log(key, value);
});
// Outputs:
// 5 'value2'
// 10 'value1'
// 15 'value3'
The 'binary-search-tree' package provides a similar implementation of a binary search tree. It supports basic operations like insertion, search, and deletion. However, it may not have as many features or optimizations as @seald-io/binary-search-tree.
The 'avl' package implements an AVL tree, which is a self-balancing binary search tree. It ensures that the tree remains balanced after insertions and deletions, providing better performance for search operations compared to a standard binary search tree.
The 'bintrees' package provides implementations for both AVL trees and Red-Black trees. These are self-balancing binary search trees that offer better performance guarantees for dynamic sets of ordered elements. This package is more versatile compared to @seald-io/binary-search-tree.
This module is a fork of node-binary-search-tree written by Louis Chatriot for storing indexes in nedb.
Since the original maintainer doesn't support these packages anymore, we forked them (here is nedb) and maintain them for the needs of Seald.
Two implementations of binary search tree: basic and AVL (a kind of self-balancing binmary search tree).
Package name is @seald-io/binary-search-tree
.
npm install @seald-io/binary-search-tree
If you want to run the tests, you'll have to clone the repository:
git clone https://github.com/seald/node-binary-search-tree
npm install
npm test
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
.
const BinarySearchTree = require('binary-search-tree').BinarySearchTree
const AVLTree = require('binary-search-tree').AVLTree // Same API as BinarySearchTree
// 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.
const bst = new BinarySearchTree({ unique: true });
bst.insert(10, 'hello');
bst.insert(10, 'world'); // Will throw an error
// Custom key comparison function
// It needs to return a negative number if a is less than b,
// a positive number if a is greater than b
// and 0 if they are equal
// If none is provided, the default one can compare numbers, dates and strings
// which are the most common usecases
const compareKeys = (a, b) => {
if (a.age < b.age) return -1
if (a.age > b.age) return 1
return 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')
// 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
const checkValueEquality = (a, b) => a.length === b.length
var 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']
The package is released under the MIT License as the original package.
See LICENSE.md.
FAQs
Different binary search tree implementations, including a self-balancing one (AVL)
We found that @seald-io/binary-search-tree demonstrated a not healthy version release cadence and project activity because the last version was released a year ago. It has 3 open source maintainers collaborating on the project.
Did you know?
Socket for GitHub automatically highlights issues in each pull request and monitors the health of all your open source dependencies. Discover the contents of your packages and block harmful activity before you install or update your dependencies.
Security News
Fluent Assertions is facing backlash after dropping the Apache license for a commercial model, leaving users blindsided and questioning contributor rights.
Research
Security News
Socket researchers uncover the risks of a malicious Python package targeting Discord developers.
Security News
The UK is proposing a bold ban on ransomware payments by public entities to disrupt cybercrime, protect critical services, and lead global cybersecurity efforts.