Preparation code

 
<script>
  Benchmark.prototype.setup = function() {
    function TNode(value, leftChild, rightChild) {
      this.value = value;
      this.leftChild = leftChild ? leftChild : null;
      this.rightChild = rightChild ? rightChild : null;
      this.parent = null;
    
      if (leftChild) {
        leftChild.parent = this;
      }
    
      if (rightChild) {
        rightChild.parent = this;
      }
    }
    
    TNode.prototype.minimum = function() {
      var curr = this;
    
      while (curr.leftChild !== null) {
        curr = curr.leftChild.minimum();
      }
    
      return curr;
    }
    
    TNode.prototype.maximum = function() {
      var curr = this;
    
      while (curr.rightChild !== null) {
        curr = curr.rightChild.maximum();
      }
    
      return curr;
    }
    
    TNode.prototype.isLeftChild = function() {
      return (this.parent !== null && this === this.parent.leftChild);
    };
    
    TNode.prototype.isRightChild = function() {
      return (this.parent !== null && this === this.parent.rightChild);
    };
    
    TNode.prototype.successor = function() {
      if (this.rightChild !== null) {
        return this.rightChild.minimum();
      }
    
      var curr = this;
    
      while (curr.isRightChild()) {
        curr = curr.parent;
      }
    
      return curr.parent;
    };
    
    TNode.prototype.predecessor = function() {
      if (this.leftChild !== null) {
        return this.leftChild.maximum();
      }
    
      var curr = this;
    
      while (curr.isLeftChild()) {
        curr = curr.parent;
      }
    
      return curr.parent;
    };
    
    function BST() {
      this.root = null;
    }
    
    BST.prototype.insert = function(value) {
      var curr = this.root,
          parent = null;
      toAdd = new TNode(value);
    
      while (curr !== null) {
        parent = curr;
        if (value < curr.value) {
          curr = curr.leftChild;
        } else {
          curr = curr.rightChild;
        }
      }
    
      toAdd.parent = parent;
    
      if (parent === null) {
        this.root = toAdd;
      } else if (toAdd.value < parent.value) {
        parent.leftChild = toAdd;
      } else {
        parent.rightChild = toAdd;
      }
    
      return toAdd;
    }
    
    BST.prototype.remove = function(value) {
      var deleted, replacement, toRemove = this.search(value);
    
      if (toRemove === null) {
        return null;
      }
    
      // deal with child node possibilities
      // when the node to remove has two children, do not delete it, instead remove
      // its successor and swap values around.
      deleted = (toRemove.leftChild !== null && toRemove.rightChild !== null) ? toRemove.successor() : toRemove;
      replacement = (deleted.leftChild !== null) ? deleted.leftChild : deleted.rightChild;
    
      if (replacement !== null) {
        replacement.parent = deleted.parent;
      }
    
      // deal with parent node possibilities
      if (deleted === this.root) {
        this.root = replacement;
      } else if (deleted.isLeftChild()) {
        deleted.parent.leftChild = replacement;
      } else {
        deleted.parent.rightChild = replacement;
      }
    
      // clean up the returned node by setting its value
      // to match the search query
      if (deleted !== toRemove) {
        toRemove.value = deleted.value;
        deleted.value = value;
      }
    
      return deleted;
    }
    
    BST.prototype.search = function(value) {
      var curr = this.root;
    
      while (curr !== null) {
        if (value === curr.value) {
          break;
        }
    
        if (value < curr.value) {
          curr = curr.leftChild;
        } else {
          curr = curr.rightChild;
        }
      }
    
      return curr;
    }
    
    function linearSearch(needle, haystack) {
      for (var i = 0; i < haystack.length; i++) {
        if (haystack[i] === needle) {
          return i;
        }
      }
      return false;
    }
    var insertValueList = [];
    for (var i = 0; i < 500; i++) {
      insertValueList.push(Math.random() * 100);
    }
    
    var valuesForSearchTest = [];
    for (var i = 0; i < insertValueList.length; i++) {
      valuesForSearchTest.push(insertValueList[i]);
    }
    
    var bstForSearchTest = new BST();
    for (var i = 0; i < insertValueList.length; i++) {
      bstForSearchTest.insert(insertValueList[i]);
    }
  };
</script>

Test runner

Warning! For accurate results, please disable Firebug before running the tests. (Why?)

Java applet disabled.

var values = [];
for (var i = 0; i < insertValueList.length; i++) {
  values.push(insertValueList[i]);
}

var bst = new BST();
for (var i = 0; i < insertValueList.length; i++) {
  bst.insert(insertValueList[i]);
}

for (var i = 0; i < insertValueList.length; i++) {
  linearSearch(insertValueList[i], valuesForSearchTest);
}

for (var i = 0; i < insertValueList.length; i++) {
  bstForSearchTest.search(insertValueList[i]);
}

You can edit these tests or add even more tests to this page by appending /edit to the URL.

Compare results of other browsers

0 comments