A binary search tree is a type of binary tree where the data in a node's left subtree is less than the node and the data in a node's right subtree is greater than (or equal to) the node, and the subtrees are also binary search trees. A binary search tree is a data structure upon which algorithms can be run. If a binary tree search was run, using a balanced binary search tree of course, the performance would be at most O(log n) since as you can see the pool of possible results is cut in half with each step (The tree must be balanced, my example does not properly balance when it adds. See: AVL tree or red-black tree).

A nice feature of a binary search tree is that if an inorder traversal (left, root, right) is performed upon it then the resulting list is sorted. I have heard people say that you would not want to use a binary search tree in "high-level programming language x" (such as JavaScript) because the native sorting methods would be faster. It is probably true that the native ".sort()" is faster than an inorder traversal, and it would certainly be more convenient than creating a tree if all I needed to was sort items, but it seems to be a rather myopic viewpoint. A software engineer should use a data structure that is appropriate and efficient for the task at hand.

With that bit of background out of the way, here is a sample implementation (continued after the jump):

/**
 * node constructor
 *
 * @constructor
 * @this {node}
 * @param {string} pval The node value
 */
function node(pval){
this.left = undefined;
this.right = undefined;
this.value = pval;
};

/**
* add a node to this node
*
* @this {node}
* @param {node} pnode The node to add
*/
node.prototype.add = function(pnode){
// we can't prevent undefined nodes
// if the node value is defined
if(this.value){
// less than then go left
if(pnode.value < this.value){
// left is already defined
if(this.left){
this.left.add(pnode);
// left is open
}else{
this.left = pnode;
}
// greater than then go right
}else{
// right is already defined
if(this.right){
this.right.add(pnode);
// right is open
}else{
this.right = pnode;
}
}
// current node is undefined
}else{
this.left = pnode.left;
this.right = pnode.right;
this.value = pnode.value;
}
}

/**
 * binary search tree constructor
 *
 * @constructor
 * @this {bst}
 */
function bst(){
this._root = new node();
};
/**
* add a node to this node
*
* @this {bst}
* @param {any} pval The value to add
*/
bst.prototype.add = function(pval){
this._root.add(new node(pval));
};
/**
* search this tree
*
* @this {bst}
* @param {any} psearch The value to search for
*/
bst.prototype.search = function(psearch){
return this._search_worker(this._root, psearch);
};
/**
* search this tree
*
* @this {bst}
* @param {node} pnode The node to search from
* @param {any} psearch The value to search for
* @return {node} The matching node
* @see {node}
*/
bst.prototype._search_worker = 
function(pnode, psearch){
if(!pnode){
return undefined;
}else if(psearch < pnode.value){
return this._search_worker(
pnode.left, psearch);
}else if(psearch > pnode.value){
return this._search_worker(
pnode.right, psearch);
}else if(psearch == pnode.value){
return pnode;
}else{
return undefined;
}
};
//
// just to test with
//
tbst = new bst();
tbst.add('k');
tbst.add('f');
tbst.add('o');
tbst.add('n');
tbst.add('z');
tbst.add('d');
tbst.add('b');
tbst.add('a');
tbst.add('g');
tbst.add('l');

Tags: Blogger JavaScript Data Structures Code Algorithms

Published: 2010-04-02