#bstree A binary search tree implementation for node and browser.
npm install bstree
var BSTree = require('bstree');
var tree = new BSTree();
tree.add(2)
tree.add(3)
tree.add(1)
tree.top() // 3
tree.bottom() // 1
tree.removeTop() //3
tree.top() // 2
tree.remove(1) // 1
tree.removeBottom() // 2
#required: sudo npm install -g grunt-cli
grunt test
- comparator:
A
function
that takes two arguments that correspond to tree node values. The return of this function is a boolean. If the value returned is true, the first argument is less than the second argument. If the value returned is false, the two arguments are equal or the second argument is greater than the first argument. Defaults to:function(a, b) { return a < b }
###Example:
var BSTree = require('bstree')
var tree = new BSTree(function(a, b) {
return b > a
})
// or
var otherTree = new BSTree()
Constant
Adds the given element from the tree.
var tree = new BSTree();
tree.add(5)
In the average case: logarithmic in #length
In the worst case: linear in #length
Returns the minimum value in the tree.
var tree = new BSTree()
;[7,3,10,5,1,6,9,8,2].forEach(tree.add, tree)
console.log(tree.bottom()) // 1
Constant in #length
property that indicates the number of elements in tree.
var tree = new BSTree()
console.log(tree.length) // 0
tree.add('item')
console.log(tree.length) // 1
Returns the maximum value in the tree.
var tree = new BSTree()
;[7,3,10,5,1,6,9,8,2].forEach(tree.add, tree);
console.log(tree.top()) // 10
Constant in #length
Removes the given element from the tree if it exists. Returns element
if a removal occurred. Returns undefined
if not.
var tree = new BSTree()
;[7,3,10,5,1,6,9,8,2].forEach(tree.add, tree);
console.log(tree.remove(8)) // 8
var sorted_array = []
tree.forEach(function (element) {
sorted_array.push(element)
})
console.log(sorted_array) // [1, 2, 3, 4, 5, 6, 7, 9, 10]
In the average case: logarithmic in #length
In the worst case: linear in #length
Removes and returns the bottom element of tree relative to comparator.
If it does not exist (tree is empty), returns undefined
###Example:
var tree = BSTree()
;[7,3,10,5,1,6,9,8,2].forEach(tree.add, tree);
console.log(tree.removeBottom()) // 1
var sorted_array = []
tree.forEach(function (element) {
sorted_array.push(element)
})
console.log(sorted_array) // [2, 3, 4, 5, 6, 7, 8, 9, 10]
In the average case: logarithmic in #length
In the worst case: linear in #length
Removes and returns the top element of tree relative to comparator.
If it does not exist (tree is empty), returns undefined
###Example:
var tree = BSTree()
;[7,3,10,5,1,6,9,8,2].forEach(tree.add, tree);
console.log(tree.removeTop()) // 10
var sorted_array = []
tree.forEach(function (element) {
sorted_array.push(element)
})
console.log(sorted_array) // [1, 2, 3, 4, 5, 6, 7, 8, 9]
In the average case: logarithmic in #length
In the worst case: linear in #length