bstree

A binary search tree implementation for node and browser.

---

Install

npm install bstree

Example:

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
 

Test

#required: sudo npm install -g grunt-cli
grunt test

---

#constructor(comparator)

---

Parameters:

• 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()

Algorithm complexity:

Constant

#add(element)

---

Adds the given element from the tree.

Example

var tree = new BSTree();
tree.add(5)

Algorithm complexity:

In the average case: logarithmic in #length

In the worst case: linear in #length

#bottom()

---

Returns the minimum value in the tree.

Example:

var tree = new BSTree()
;[7,3,10,5,1,6,9,8,2].forEach(tree.add, tree)
 
console.log(tree.bottom()) // 1

Algorithm complexity:

Constant in #length

#length

---

property that indicates the number of elements in tree.

Example:

var tree = new BSTree()
console.log(tree.length) // 0
 
tree.add('item')
console.log(tree.length) // 1

#top()

---

Returns the maximum value in the tree.

Example:

var tree = new BSTree()
;[7,3,10,5,1,6,9,8,2].forEach(tree.add, tree);
 
console.log(tree.top()) // 10

Algorithm complexity:

Constant in #length

#remove(element)

---

Removes the given element from the tree if it exists. Returns element if a removal occurred. Returns undefined if not.

Example

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]

Algorithm complexity:

In the average case: logarithmic in #length

In the worst case: linear in #length

#removeBottom()

---

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]

Algorithm complexity:

In the average case: logarithmic in #length

In the worst case: linear in #length

#removeTop()

---

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]

Algorithm complexity:

In the average case: logarithmic in #length

In the worst case: linear in #length