binary-search-tree - npm Package Compare versions

Comparing version 0.0.1 to 0.0.2

lib/bst.js

@@ -5,4 +5,6 @@ /**
 
-// Default compare function will work for numbers, strings and dates
-function defaultCompareFunction (a, b) {
+/*
+ * Default compareKeys function will work for numbers, strings and dates
+ */
+function defaultCompareKeysFunction (a, b) {
   if (a < b) { return -1; }
@@ -17,2 +19,10 @@ if (a > b) { return 1; }
 /**
+ * Check whether two values are equal (used in non-unique deletion)
+ */
+function defaultCheckValueEquality (a, b) {
+  return a === b;
+}
+
+
+/**
  * Constructor
@@ -35,3 +45,4 @@ * @param {Object} options Optional
 
-  this.compareKeys = options.compareKeys || defaultCompareFunction;
+  this.compareKeys = options.compareKeys || defaultCompareKeysFunction;
+  this.checkValueEquality = options.checkValueEquality || defaultCheckValueEquality;
 }
@@ -62,3 +73,3 @@
   return leftChild;
-}
+};
 
@@ -75,14 +86,13 @@
   return rightChild;
-}
+};
 
 
 /**
- * Get the maximum key
- * This is equal to a traversal from the root to the right-most leaf
+ * Get the descendant with max key
  */
-BinarySearchTree.prototype.getMaxKey = function () {
+BinarySearchTree.prototype.getMaxKeyDescendant = function () {
   if (this.right) {
-    return this.right.getMaxKey()
+    return this.right.getMaxKeyDescendant();
   } else {
-    return this.key;
+    return this;
   }
@@ -93,10 +103,17 @@ };
 /**
- * Get the minimum key
- * This is equal to a traversal from the root to the left-most leaf
+ * Get the maximum key
  */
-BinarySearchTree.prototype.getMinKey = function () {
+BinarySearchTree.prototype.getMaxKey = function () {
+  return this.getMaxKeyDescendant().key;
+};
+
+
+/**
+ * Get the descendant with min key
+ */
+BinarySearchTree.prototype.getMinKeyDescendant = function () {
   if (this.left) {
-    return this.left.getMinKey()
+    return this.left.getMinKeyDescendant()
   } else {
-    return this.key;
+    return this;
   }
@@ -107,17 +124,47 @@ };
 /**
- * Check that all BST properties are actually verified
+ * Get the minimum key
+ */
+BinarySearchTree.prototype.getMinKey = function () {
+  return this.getMinKeyDescendant().key;
+};
+
+
+/**
+ * Check that all nodes (incl. leaves) fullfil condition given by fn
+ * test is a function passed every (key, data) and which throws if the condition is not met
+ */
+BinarySearchTree.prototype.checkAllNodesFullfillCondition = function (test) {
+  if (!this.key) { return; }
+
+  test(this.key, this.data);
+  if (this.left) { this.left.checkAllNodesFullfillCondition(test); }
+  if (this.right) { this.right.checkAllNodesFullfillCondition(test); }
+};
+
+
+/**
+ * Check that the core BST properties on node ordering are verified
  * Throw if they aren't
- * A priori only useful for testing
  */
-BinarySearchTree.prototype.checkIsBST = function () {
+BinarySearchTree.prototype.checkNodeOrdering = function () {
+  var self = this;
+
   if (!this.key) { return; }
 
   if (this.left) {
-    if (this.compareKeys(this.left.getMaxKey(), this.key) >= 0) { throw "Tree with root " + this.key + "  is not a BST"; }
-    this.left.checkIsBST();
+    this.left.checkAllNodesFullfillCondition(function (k) {
+      if (self.compareKeys(k, self.key) >= 0) {
+        throw 'Tree with root ' + self.key + ' is not a binary search tree';
+      }
+    });
+    this.left.checkNodeOrdering();
   }
 
   if (this.right) {
-    if (this.compareKeys(this.right.getMaxKey(), this.key) <= 0) { throw "Tree with root " + this.key + "  is not a BST"; }
-    this.right.checkIsBST();
+    this.right.checkAllNodesFullfillCondition(function (k) {
+      if (self.compareKeys(k, self.key) <= 0) {
+        throw 'Tree with root ' + self.key + ' is not a binary search tree';
+      }
+    });
+    this.right.checkNodeOrdering();
   }
@@ -128,2 +175,27 @@ };
 /**
+ * Check that all pointers are coherent in this tree
+ */
+BinarySearchTree.prototype.checkInternalPointers = function () {
+  if (this.left) {
+    if (this.left.parent !== this) { throw 'Parent pointer broken for key ' + this.key; }
+    this.left.checkInternalPointers();
+  }
+
+  if (this.right) {
+    if (this.right.parent !== this) { throw 'Parent pointer broken for key ' + this.key; }
+    this.right.checkInternalPointers();
+  }
+};
+
+
+/**
+ * Check that a tree is a BST as defined here (node ordering and pointer references)
+ */
+BinarySearchTree.prototype.checkIsBST = function () {
+  this.checkNodeOrdering();
+  this.checkInternalPointers();
+};
+
+
+/**
  * Insert a new element
@@ -191,3 +263,125 @@ */
 
+/**
+ * Delete the current node if it is a leaf
+ * Return true if it was deleted
+ */
+BinarySearchTree.prototype.deleteIfLeaf = function () {
+  if (this.left || this.right) { return false; }
+
+  // The leaf is itself a root
+  if (!this.parent) {
+    this.key = null;
+    this.data = [];
+    return true;
+  }
+
+  if (this.parent.left === this) {
+    this.parent.left = null;
+  } else {
+    this.parent.right = null;
+  }
+
+  return true;
+};
+
+
+/**
+ * Delete the current node if it has only one child
+ * Return true if it was deleted
+ */
+BinarySearchTree.prototype.deleteIfOnlyOneChild = function () {
+  var child;
+
+  if (this.left && !this.right) { child = this.left; }
+  if (!this.left && this.right) { child = this.right; }
+  if (!child) { return false; }
+
+  // Root
+  if (!this.parent) {
+    this.key = child.key;
+    this.data = child.data;
+
+    this.left = null;
+    if (child.left) {
+      this.left = child.left;
+      child.left.parent = this;
+    }
+
+    this.right = null;
+    if (child.right) {
+      this.right = child.right;
+      child.right.parent = this;
+    }
+
+    return true;
+  }
+
+  if (this.parent.left === this) {
+    this.parent.left = child;
+    child.parent = this.parent;
+  } else {
+    this.parent.right = child;
+    child.parent = this.parent;
+  }
+
+  return true;
+};
+
+
+/**
+ * Delete a key or just a value
+ * @param {Key} key
+ * @param {Value} value Optional. If not set, the whole key is deleted. If set, only this value is deleted
+ */
+BinarySearchTree.prototype.delete = function (key, value) {
+  var newData = [], replaceWith;
+
+  if (this.key === null) { return; }
+
+  if (this.compareKeys(key, this.key) < 0) {
+    if (this.left) { this.left.delete(key, value); }
+    return;
+  }
+
+  if (this.compareKeys(key, this.key) > 0) {
+    if (this.right) { this.right.delete(key, value); }
+    return;
+  }
+
+  if (!this.compareKeys(key, this.key) === 0) { return; }
+
+  // Delete only a value
+  if (this.data.length > 1 && value) {
+    this.data.forEach(function (d) {
+      if (!this.checkValueEquality(d, value)) { newData.push(d); }
+      this.data = newData;
+    });
+    return;
+  }
+
+  // Delete the whole node
+  if (this.deleteIfLeaf()) { return; }
+  if (this.deleteIfOnlyOneChild()) { return; }
+
+  // We are in the case where the node to delete has two children
+  if (Math.random() >= 0.5) {   // Randomize replacement to avoid unbalancing the tree too much
+    // Use the in-order predecessor
+    replaceWith = this.left.getMaxKeyDescendant();
+    this.key = replaceWith.key;
+    this.data = replaceWith.data;
+    replaceWith.parent.right = replaceWith.left;
+    if (replaceWith.left) { replaceWith.left.parent = replaceWith.parent; }
+  } else {
+    // Use the in-order successor
+    replaceWith = this.right.getMinKeyDescendant();
+    this.key = replaceWith.key;
+    this.data = replaceWith.data;
+    replaceWith.parent.left = replaceWith.right;
+    if (replaceWith.right) { replaceWith.right.parent = replaceWith.parent; }
+  }
+};
+
+
+
 // Interface
 module.exports = BinarySearchTree;

package.json

 {
   "name": "binary-search-tree",
-  "version": "0.0.1",
+  "version": "0.0.2",
   "author": {
@@ -5,0 +5,0 @@ "name": "Louis Chatriot",

test/bst.test.js

@@ -19,2 +19,158 @@ var should = require('chai').should()
 
+  describe('Sanity checks', function () {
+
+    it('Can get maxkey and minkey descendants', function () {
+      var t = new BinarySearchTree({ key: 10 })
+        , l = new BinarySearchTree({ key: 5 })
+        , r = new BinarySearchTree({ key: 15 })
+        , ll = new BinarySearchTree({ key: 3 })
+        , lr = new BinarySearchTree({ key: 8 })
+        , rl = new BinarySearchTree({ key: 11 })
+        , rr = new BinarySearchTree({ key: 42 })
+        ;
+
+      t.left = l; t.right = r;
+      l.left = ll; l.right = lr;
+      r.left = rl; r.right = rr;
+
+      // Getting min and max key descendants
+      t.getMinKeyDescendant().key.should.equal(3);
+      t.getMaxKeyDescendant().key.should.equal(42);
+
+      t.left.getMinKeyDescendant().key.should.equal(3);
+      t.left.getMaxKeyDescendant().key.should.equal(8);
+
+      t.right.getMinKeyDescendant().key.should.equal(11);
+      t.right.getMaxKeyDescendant().key.should.equal(42);
+
+      t.right.left.getMinKeyDescendant().key.should.equal(11);
+      t.right.left.getMaxKeyDescendant().key.should.equal(11);
+
+      // Getting min and max keys
+      t.getMinKey().should.equal(3);
+      t.getMaxKey().should.equal(42);
+
+      t.left.getMinKey().should.equal(3);
+      t.left.getMaxKey().should.equal(8);
+
+      t.right.getMinKey().should.equal(11);
+      t.right.getMaxKey().should.equal(42);
+
+      t.right.left.getMinKey().should.equal(11);
+      t.right.left.getMaxKey().should.equal(11);
+    });
+
+    it('Can check a condition again every node in a tree', function () {
+      var t = new BinarySearchTree({ key: 10 })
+        , l = new BinarySearchTree({ key: 6 })
+        , r = new BinarySearchTree({ key: 16 })
+        , ll = new BinarySearchTree({ key: 4 })
+        , lr = new BinarySearchTree({ key: 8 })
+        , rl = new BinarySearchTree({ key: 12 })
+        , rr = new BinarySearchTree({ key: 42 })
+        ;
+
+      t.left = l; t.right = r;
+      l.left = ll; l.right = lr;
+      r.left = rl; r.right = rr;
+
+      function test (k, v) { if (k % 2 !== 0) { throw 'Key is not even'; } }
+
+      t.checkAllNodesFullfillCondition(test);
+
+      [l, r, ll, lr, rl, rr].forEach(function (node) {
+        node.key += 1;
+        (function () { t.checkAllNodesFullfillCondition(test); }).should.throw();
+        node.key -= 1;
+      });
+
+      t.checkAllNodesFullfillCondition(test);
+    });
+
+    it('Can check that a tree verifies node ordering', function () {
+      var t = new BinarySearchTree({ key: 10 })
+        , l = new BinarySearchTree({ key: 5 })
+        , r = new BinarySearchTree({ key: 15 })
+        , ll = new BinarySearchTree({ key: 3 })
+        , lr = new BinarySearchTree({ key: 8 })
+        , rl = new BinarySearchTree({ key: 11 })
+        , rr = new BinarySearchTree({ key: 42 })
+        ;
+
+      t.left = l; t.right = r;
+      l.left = ll; l.right = lr;
+      r.left = rl; r.right = rr;
+
+      t.checkNodeOrdering();
+
+      // Let's be paranoid and check all cases...
+      l.key = 12;
+      (function () { t.checkNodeOrdering(); }).should.throw();
+      l.key = 5;
+
+      r.key = 9;
+      (function () { t.checkNodeOrdering(); }).should.throw();
+      r.key = 15;
+
+      ll.key = 6;
+      (function () { t.checkNodeOrdering(); }).should.throw();
+      ll.key = 11;
+      (function () { t.checkNodeOrdering(); }).should.throw();
+      ll.key = 3;
+
+      lr.key = 4;
+      (function () { t.checkNodeOrdering(); }).should.throw();
+      lr.key = 11;
+      (function () { t.checkNodeOrdering(); }).should.throw();
+      lr.key = 8;
+
+      rl.key = 16;
+      (function () { t.checkNodeOrdering(); }).should.throw();
+      rl.key = 9;
+      (function () { t.checkNodeOrdering(); }).should.throw();
+      rl.key = 11;
+
+      rr.key = 12;
+      (function () { t.checkNodeOrdering(); }).should.throw();
+      rr.key = 7;
+      (function () { t.checkNodeOrdering(); }).should.throw();
+      rr.key = 10.5;
+      (function () { t.checkNodeOrdering(); }).should.throw();
+      rr.key = 42;
+
+      t.checkNodeOrdering();
+    });
+
+    it('Checking if a tree\'s internal pointers (i.e. parents) are correct', function () {
+      var t = new BinarySearchTree({ key: 10 })
+        , l = new BinarySearchTree({ key: 5 })
+        , r = new BinarySearchTree({ key: 15 })
+        , ll = new BinarySearchTree({ key: 3 })
+        , lr = new BinarySearchTree({ key: 8 })
+        , rl = new BinarySearchTree({ key: 11 })
+        , rr = new BinarySearchTree({ key: 42 })
+        ;
+
+      t.left = l; t.right = r;
+      l.left = ll; l.right = lr;
+      r.left = rl; r.right = rr;
+
+      (function () { t.checkInternalPointers(); }).should.throw();
+      l.parent = t;
+      (function () { t.checkInternalPointers(); }).should.throw();
+      r.parent = t;
+      (function () { t.checkInternalPointers(); }).should.throw();
+      ll.parent = l;
+      (function () { t.checkInternalPointers(); }).should.throw();
+      lr.parent = l;
+      (function () { t.checkInternalPointers(); }).should.throw();
+      rl.parent = r;
+      (function () { t.checkInternalPointers(); }).should.throw();
+      rr.parent = r;
+
+      t.checkInternalPointers();
+    });
+
+  });
+
   describe('Insertion', function () {
@@ -223,5 +379,217 @@
 
-
   });   /// ==== End of 'Search' ==== //
 
+
+  describe('Deletion', function () {
+
+    it('Deletion does nothing on an empty tree', function () {
+      var bst = new BinarySearchTree()
+        , bstu = new BinarySearchTree({ unique: true });
+
+      bst.delete(5);
+      bstu.delete(5);
+
+      assert.isNull(bst.key);
+      assert.isNull(bstu.key);
+
+      bst.data.length.should.equal(0);
+      bstu.data.length.should.equal(0);
+    });
+
+    it('Deleting a non-existent key doesnt have any effect', function () {
+      var bst = new BinarySearchTree();
+
+      [10, 5, 3, 8, 15, 12, 37].forEach(function (k) {
+        bst.insert(k, 'some ' + k);
+      });
+
+      function checkBst () {
+        [10, 5, 3, 8, 15, 12, 37].forEach(function (k) {
+          _.isEqual(bst.search(k), ['some ' + k]).should.equal(true);
+        });
+      }
+
+      checkBst();
+
+      bst.delete(2);
+      checkBst(); bst.checkIsBST();
+      bst.delete(4);
+      checkBst(); bst.checkIsBST();
+      bst.delete(9);
+      checkBst(); bst.checkIsBST();
+      bst.delete(6);
+      checkBst(); bst.checkIsBST();
+      bst.delete(11);
+      checkBst(); bst.checkIsBST();
+      bst.delete(14);
+      checkBst(); bst.checkIsBST();
+      bst.delete(20);
+      checkBst(); bst.checkIsBST();
+      bst.delete(200);
+      checkBst(); bst.checkIsBST();
+    });
+
+    it('Able to delete the rootif it is also a leaf', function () {
+      var bst = new BinarySearchTree();
+
+      bst.insert(10, 'hello');
+      bst.key.should.equal(10);
+      _.isEqual(bst.data, ['hello']).should.equal(true);
+
+      bst.delete(10);
+      assert.isNull(bst.key);
+      bst.data.length.should.equal(0);
+    });
+
+    it('Able to delete leaf nodes that are non-root', function () {
+      var bst;
+
+      function recreateBst () {
+        bst = new BinarySearchTree();
+
+        // With this insertion order the tree is well balanced
+        // So we know the leaves are 3, 8, 12, 37
+        [10, 5, 3, 8, 15, 12, 37].forEach(function (k) {
+          bst.insert(k, 'some ' + k);
+        });
+      }
+
+      function checkOnlyOneWasRemoved (theRemoved) {
+        [10, 5, 3, 8, 15, 12, 37].forEach(function (k) {
+          if (k === theRemoved) {
+            bst.search(k).length.should.equal(0);
+          } else {
+            _.isEqual(bst.search(k), ['some ' + k]).should.equal(true);
+          }
+        });
+      }
+
+      recreateBst();
+      bst.delete(3);
+      bst.checkIsBST();
+      checkOnlyOneWasRemoved(3);
+      assert.isNull(bst.left.left);
+
+      recreateBst();
+      bst.delete(8);
+      bst.checkIsBST();
+      checkOnlyOneWasRemoved(8);
+      assert.isNull(bst.left.right);
+
+      recreateBst();
+      bst.delete(12);
+      bst.checkIsBST();
+      checkOnlyOneWasRemoved(12);
+      assert.isNull(bst.right.left);
+
+      recreateBst();
+      bst.delete(37);
+      bst.checkIsBST();
+      checkOnlyOneWasRemoved(37);
+      assert.isNull(bst.right.right);
+    });
+
+    it('Able to delete the root if it has only one child', function () {
+      var bst;
+
+      // Root has only one child, on the left
+      bst = new BinarySearchTree();
+      [10, 5, 3, 6].forEach(function (k) {
+        bst.insert(k, 'some ' + k);
+      });
+      bst.delete(10);
+      bst.checkIsBST();
+      [5, 3, 6].forEach(function (k) {
+        _.isEqual(bst.search(k), ['some ' + k]).should.equal(true);
+      });
+      bst.search(10).length.should.equal(0);
+
+      // Root has only one child, on the right
+      bst = new BinarySearchTree();
+      [10, 15, 13, 16].forEach(function (k) {
+        bst.insert(k, 'some ' + k);
+      });
+      bst.delete(10);
+      bst.checkIsBST();
+      [15, 13, 16].forEach(function (k) {
+        _.isEqual(bst.search(k), ['some ' + k]).should.equal(true);
+      });
+      bst.search(10).length.should.equal(0);
+    });
+
+    it('Able to delete non root nodes that have only one child', function () {
+      var bst;
+
+      function recreateBst () {
+        bst = new BinarySearchTree();
+
+        [10, 5, 15, 3, 1, 4, 20, 17, 25].forEach(function (k) {
+          bst.insert(k, 'some ' + k);
+        });
+      }
+
+      function checkOnlyOneWasRemoved (theRemoved) {
+        [10, 5, 15, 3, 1, 4, 20, 17, 25].forEach(function (k) {
+          if (k === theRemoved) {
+            bst.search(k).length.should.equal(0);
+          } else {
+            _.isEqual(bst.search(k), ['some ' + k]).should.equal(true);
+          }
+        });
+      }
+
+      recreateBst();
+      bst.delete(5);
+      bst.checkIsBST();
+      checkOnlyOneWasRemoved(5);
+
+      recreateBst();
+      bst.delete(15);
+      bst.checkIsBST();
+      checkOnlyOneWasRemoved(15);
+    });
+
+    it('Can delete the root if it has 2 children', function () {
+      var bst;
+
+      bst = new BinarySearchTree();
+      [10, 5, 3, 8, 15, 12, 37].forEach(function (k) {
+        bst.insert(k, 'some ' + k);
+      });
+      bst.delete(10);
+      bst.checkIsBST();
+      [5, 3, 8, 15, 12, 37].forEach(function (k) {
+        _.isEqual(bst.search(k), ['some ' + k]).should.equal(true);
+      });
+      bst.search(10).length.should.equal(0);
+    });
+
+    it('Can delete a non-root node that has two children', function () {
+      var bst;
+
+      bst = new BinarySearchTree();
+      [10, 5, 3, 1, 4, 8, 6, 9, 15, 12, 11, 13, 20, 19, 42].forEach(function (k) {
+        bst.insert(k, 'some ' + k);
+      });
+      bst.delete(5);
+      bst.checkIsBST();
+      [10, 3, 1, 4, 8, 6, 9, 15, 12, 11, 13, 20, 19, 42].forEach(function (k) {
+        _.isEqual(bst.search(k), ['some ' + k]).should.equal(true);
+      });
+      bst.search(5).length.should.equal(0);
+
+      bst = new BinarySearchTree();
+      [10, 5, 3, 1, 4, 8, 6, 9, 15, 12, 11, 13, 20, 19, 42].forEach(function (k) {
+        bst.insert(k, 'some ' + k);
+      });
+      bst.delete(15);
+      bst.checkIsBST();
+      [10, 5, 3, 1, 4, 8, 6, 9, 12, 11, 13, 20, 19, 42].forEach(function (k) {
+        _.isEqual(bst.search(k), ['some ' + k]).should.equal(true);
+      });
+      bst.search(15).length.should.equal(0);
+    });
+
+  });   // ==== End of 'Deletion' ==== //
+
 });

No alert changes

Improved metrics

Total package byte prevSize

27985

increased by128.24%

Lines of code

784

increased by138.3%

No dependency changes