BST vs Array
JavaScript performance comparison
Info
BST should be faster in theory on sufficiently large trees, but where's that tipping point in JS given all the engines' array optimizations and cost of object construction.
Using BST implementation from:
Preparation code
<script>
Benchmark.prototype.setup = function() {
function BinarySearchTree() {
/**
* Pointer to root node in the tree.
* @property _root
* @type Object
* @private
*/
this._root = null;
}
BinarySearchTree.prototype = {
//restore constructor
constructor: BinarySearchTree,
/**
* Appends some data to the appropriate point in the tree. If there are no
* nodes in the tree, the data becomes the root. If there are other nodes
* in the tree, then the tree must be traversed to find the correct spot
* for insertion.
* @param {variant} value The data to add to the list.
* @return {Void}
* @method add
*/
add: function (value){
//create a new item object, place data in
var node = {
value: value,
left: null,
right: null
},
//used to traverse the structure
current;
//special case: no items in the tree yet
if (this._root === null){
this._root = node;
} else {
current = this._root;
while(true){
//if the new value is less than this node's value, go left
if (value < current.value){
//if there's no left, then the new node belongs there
if (current.left === null){
current.left = node;
break;
} else {
current = current.left;
}
//if the new value is greater than this node's value, go right
} else if (value > current.value){
//if there's no right, then the new node belongs there
if (current.right === null){
current.right = node;
break;
} else {
current = current.right;
}
//if the new value is equal to the current one, just ignore
} else {
break;
}
}
}
},
/**
* Determines if the given value is present in the tree.
* @param {variant} value The value to find.
* @return {Boolean} True if the value is found, false if not.
* @method contains
*/
contains: function(value){
var found = false,
current = this._root
//make sure there's a node to search
while(!found && current){
//if the value is less than the current node's, go left
if (value < current.value){
current = current.left;
//if the value is greater than the current node's, go right
} else if (value > current.value){
current = current.right;
//values are equal, found it!
} else {
found = true;
}
}
//only proceed if the node was found
return found;
},
/**
* Removes the node with the given value from the tree. This may require
* moving around some nodes so that the binary search tree remains
* properly balanced.
* @param {variant} value The value to remove.
* @return {void}
* @method remove
*/
remove: function(value){
var found = false,
parent = null,
current = this._root,
childCount,
replacement,
replacementParent;
//make sure there's a node to search
while(!found && current){
//if the value is less than the current node's, go left
if (value < current.value){
parent = current;
current = current.left;
//if the value is greater than the current node's, go right
} else if (value > current.value){
parent = current;
current = current.right;
//values are equal, found it!
} else {
found = true;
}
}
//only proceed if the node was found
if (found){
//figure out how many children
childCount = (current.left !== null ? 1 : 0) + (current.right !== null ? 1 : 0);
//special case: the value is at the root
if (current === this._root){
switch(childCount){
//no children, just erase the root
case 0:
this._root = null;
break;
//one child, use one as the root
case 1:
this._root = (current.right === null ? current.left : current.right);
break;
//two children, little work to do
case 2:
//new root will be the old root's left child...maybe
replacement = this._root.left;
//find the right-most leaf node to be the real new root
while (replacement.right !== null){
replacementParent = replacement;
replacement = replacement.right;
}
//it's not the first node on the left
if (replacementParent !== null){
//remove the new root from it's previous position
replacementParent.right = replacement.left;
//give the new root all of the old root's children
replacement.right = this._root.right;
replacement.left = this._root.left;
} else {
//just assign the children
replacement.right = this._root.right;
}
//officially assign new root
this._root = replacement;
//no default
}
//non-root values
} else {
switch (childCount){
//no children, just remove it from the parent
case 0:
//if the current value is less than its parent's, null out the left pointer
if (current.value < parent.value){
parent.left = null;
//if the current value is greater than its parent's, null out the right pointer
} else {
parent.right = null;
}
break;
//one child, just reassign to parent
case 1:
//if the current value is less than its parent's, reset the left pointer
if (current.value < parent.value){
parent.left = (current.left === null ? current.right : current.left);
//if the current value is greater than its parent's, reset the right pointer
} else {
parent.right = (current.left === null ? current.right : current.left);
}
break;
//two children, a bit more complicated
case 2:
//reset pointers for new traversal
replacement = current.left;
replacementParent = current;
//find the right-most node
while(replacement.right !== null){
replacementParent = replacement;
replacement = replacement.right;
}
replacementParent.right = replacement.left;
//assign children to the replacement
replacement.right = current.right;
replacement.left = current.left;
//place the replacement in the right spot
if (current.value < parent.value){
parent.left = replacement;
} else {
parent.right = replacement;
}
//no default
}
}
}
},
/**
* Returns the number of items in the tree. To do this, a traversal
* must be executed.
* @return {int} The number of items in the tree.
* @method size
*/
size: function(){
var length = 0;
this.traverse(function(node){
length++;
});
return length;
},
/**
* Converts the tree into an array.
* @return {Array} An array containing all of the data in the tree.
* @method toArray
*/
toArray: function(){
var result = [];
this.traverse(function(node){
result.push(node.value);
});
return result;
},
/**
* Converts the list into a string representation.
* @return {String} A string representation of the list.
* @method toString
*/
toString: function(){
return this.toArray().toString();
},
/**
* Traverses the tree and runs the given method on each node it comes
* across while doing an in-order traversal.
* @param {Function} process The function to run on each node.
* @return {void}
* @method traverse
*/
traverse: function(process){
//helper function
function inOrder(node){
if (node){
//traverse the left subtree
if (node.left !== null){
inOrder(node.left);
}
//call the process method on this node
process.call(this, node);
//traverse the right subtree
if (node.right !== null){
inOrder(node.right);
}
}
}
//start with the root
inOrder(this._root);
}
};
var data500 = [];
for(var i = 0; i < 500; i++) { data500[i] = i; }
var preppedBST500 = new BinarySearchTree();
var preppedArray500 = [];
for(i=0; i<500; i++) {
preppedBST500.add(data500[i]); preppedArray500.push(data500[i]);
}
};
</script>Test runner
Warning! For accurate results, please disable Firebug before running the tests. (Why?)
Java applet disabled.
| Test | Ops/sec | |
|---|---|---|
500 elems BST add |
|
pending… |
500 elems Array add |
|
pending… |
500 BST search |
|
pending… |
500 array search |
|
pending… |
500 BST Composite |
|
pending… |
500 Array composite |
|
pending… |
Compare results of other browsers
Revisions
You can edit these tests or add even more tests to this page by appending /edit to the URL. Here’s a list of current revisions for this page:
- Revision 1: published
- Revision 2: published by Florian Traverse
0 comments