README

DragonBST - a dependency-less AVL binary search tree

Installation and tests

Package name is @recrosoftware/dragon-bst.

npm install @recrosoftware/dragon-bst

You can test with:

git clone https://github.com/Recrosoftware/node-dragon-bst.git dragon-bst
cd dragon-bst
npm install
npm test

Usage

Import module

// ES6
import {AVLTree} from '@recrosoftware/dragon-bst';

// or ES5
var AVLTree = require('@recrosoftware/dragon-bst').AVLTree;

Creating a tree

The AVLTree constructor accepts three optional parameters that allow you to:

Enforce key-data uniqueness constrain
Enforce data uniqueness constrain for data associated to a key
Use a custom key comparison function
Use a custom data equality checking function

Uniqueness

// Creating an AVL binary search tree with enforced uniqueness
var tree = new AVLTree({ unique: true });

tree.insert(10, 'hello');
tree.insert(10, 'world'); // Will throw a TreeError

Data uniqueness

Defaults to true

// Creating an AVL binary search tree with enforced data uniqueness (default)
var tree = new AVLTree();

tree.insert(10, 'hi');
tree.insert(10, 'hello');
tree.insert(10, 'hi');

tree.search(10);   // Equal to ['hi', 'hello']

// Creating an AVL binary search tree without enforced data uniqueness
tree = new AVLTree({ uniqueValues: false });

tree.insert(10, 'hi');
tree.insert(10, 'hello');
tree.insert(10, 'hi');

tree.search(10);   // Equal to ['hi', 'hello', 'hi]

Custom key comparison

The custom key comparison function is a function that accepts two keys as arguments and returns:

-1 if the first key is lesser than the second
0 if the keys are equals
1 if the second key is greater than the first

Note: the default key comparison function is capable to compare numbers, strings and dates but not numbers with strings, or strings with dates, etc.

function 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
var tree = new AVLTree({ compareKeys: compareKeys });

tree.insert({ age: 23 }, 'Mark');
tree.insert({ age: 47 }, 'Franck');

Custom value checking

The custom value checking function is a function that accepts two pieces of fata as arguments and returns true or false whether they are equals or not.

Note: the default value checking function can compare strings, numbers and booleans

function checkValueEquality (a, b) {
  return a.length === b.length;
}

var tree = new AVLTree({ checkValueEquality: checkValueEquality });
tree.insert(10, 'hello');      // Now key 10 contains ['hello']
tree.insert(10, 'world');      // Now key 10 contains ['world']
tree.insert(10, 'howdoyoudo'); // Now key 10 contains ['world', 'howdoyoudo']

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

Insert Elements

// Creating an AVL binary search tree
var tree = new AVLTree();

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

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

Search elements

Let's imagine that we have the following tree:

var tree = new AVLTree();

tree.insert(0, 'A');
tree.insert(0, 'a');

tree.insert(1, 'B');
tree.insert(2, 'C');
tree.insert(3, 'D');
tree.insert(4, 'E');
tree.insert(5, 'F');
tree.insert(6, 'G');
tree.insert(7, 'H');
tree.insert(8, 'I');
tree.insert(9, 'J');

We can search for a single element in the tree by using:

// Search data for a specific key
tree.search(0);      // Equal to ['A', 'a']
tree.search(6);      // Equal to ['G']
tree.search(11);     // Equal to []

We can search for a key or data that follows or precedes a certain key:

Note: the keys' order is based on the compareKeys function provided in the options while creating the tree.

// Search data right after a specific key
tree.searchAfter(3); // Equal to ['E']
tree.searchAfter(9); // Equal to []

// Search data right before a specific key
tree.searchBefore(3); // Equal to ['C']
tree.searchBefore(0); // Equal to []

// Search the key right after a specified one
tree.searchKeyAfter(3); // Equal to 4
tree.searchKeyAfter(9); // Returns undefined

// Search the key right before a specified one
tree.searchKeyBefore(3); // Equal to 2
tree.searchKeyBefore(0); // Returns undefined

We can search for keys within bounds or data associated with those keys: