Class: BTree

BTree

Generalization of BinarySearchTree data structured with each node allowed to have more than 2 children. [Ref - Introduction to Algorithms By Cormen et al.]

new BTree(degree)

Example

var BTree = require("dsjslib").BTree
var btree=new BTree(3)

Known Limitations: Currently only supports Numeric or String keys (uses < > for natural ordering). Its more of an academic implementation at this point because all nodes are always in memory. A more robust/practical implementation which loads data from disk as required will be added soon.

Parameters:
Name Type Description
degree Number

A BTree of degree N,can have a maximum of 2*N -1 keys and minimum of N-1 keys per Node. Root is allowed to have less than minimum no. of keys
Source:

Methods

checkInvariants(node)

Check various BTree invariants -- For sanity testing 1. Except root all nodes have degree -1 <keys<2*degree-1 2. Child keys are less than corresponding parent key (and greater than predecessor parent key)

Parameters:
Name Type Argument Description
node Object <optional>

Node to start at. Starts at root if not provided
Source:

delete(key, node)

Deletes a key and re-joins nodes and/or reduces the height of tree as required

Parameters:
Name Type Argument Description
key String | Number

key to delete
node Object <optional>

Node to start at. Starts at root if not provided
Source:

get(key, node) → {*}

Get value for key

Parameters:
Name Type Argument Description
key String | Number
node Object <optional>

Optional, Node to start search at. When not provided search starts at root
Source:
Returns:

value associated with key, null if key was not found

Type
*

put(key, value, node) → {BTree}

Inserts a key and splits nodes as required

Parameters:
Name Type Argument Description
key String | Number
value *
node Object <optional>

Node to start at. Starts at root if not provided
Source:
Returns:

this

Type
BTree