Editing bst_check

This edit will create a new revision.

Your details (optional)

Name

Email (won’t be displayed; might be used for Gravatar)

URL

Test case details

Title *

Published (uncheck if you want to fiddle around before making the page public)

Description (in case you feel further explanation is needed)(Markdown syntax is allowed)

Are you a spammer? (just answer the question)

Preparation code

Preparation code HTML (this will be inserted in the <body> of a valid HTML5 document in standards mode) (useful when testing DOM operations or including libraries)

Include JavaScript libraries as follows: <script src="//cdn.ext/library.js"></script>

Define setup for all tests (variables, functions, arrays or other objects that will be used in the tests) (runs before each clocked test loop, outside of the timed code region) (e.g. define local test variables, reset global variables, clear canvas, etc.) (see FAQ)

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;
}

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]);
}

Define teardown for all tests (runs after each clocked test loop, outside of the timed code region) (see FAQ)

Code snippets to compare

Test 1

Title

Async (check if this is an asynchronous test)

Code

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

Test 2

Title

Async (check if this is an asynchronous test)

Code

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

Test 3

Title

Async (check if this is an asynchronous test)

Code

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

Test 4

Title

Async (check if this is an asynchronous test)

Code

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