binary-search-tree - npm Package Compare versions

Comparing version 0.1.4 to 0.2.0

lib/avltree.js

@@ -7,6 +7,20 @@ /**
   , util = require('util')
+  , _ = require('underscore')
   ;
 
+
 /**
  * Constructor
+ * We can't use a direct pointer to the root node (as in the simple binary search tree)
+ * as the root will change during tree rotations
+ * @param {Boolean}  options.unique Whether to enforce a 'unique' constraint on the key or not
+ * @param {Function} options.compareKeys Initialize this BST's compareKeys
+ */
+function AVLTree (options) {
+  this.tree = new _AVLTree(options);
+}
+
+
+/**
+ * Constructor of the internal AVLTree
  * @param {Object} options Optional
@@ -18,3 +32,3 @@ * @param {Boolean}  options.unique Whether to enforce a 'unique' constraint on the key or not
  */
-function AVLTree (options) {
+function _AVLTree (options) {
   options = options || {};
@@ -37,7 +51,408 @@
  */
-util.inherits(AVLTree, BinarySearchTree);
+util.inherits(_AVLTree, BinarySearchTree);
 
+/**
+ * Keep a pointer to the internal tree constructor for testing purposes
+ */
+AVLTree._AVLTree = _AVLTree;
 
 
+/**
+ * Check the recorded height is correct for every node
+ * Throws if one height doesn't match
+ */
+_AVLTree.prototype.checkHeightCorrect = function () {
+  var leftH, rightH;
+
+  if (!this.key) { return; }   // Empty tree
+
+  if (this.left && this.left.height === undefined) { throw "Undefined height for node " + this.left.key; }
+  if (this.right && this.right.height === undefined) { throw "Undefined height for node " + this.right.key; }
+  if (this.height === undefined) { throw "Undefined height for node " + this.key; }
+
+  leftH = this.left ? this.left.height : 0;
+  rightH = this.right ? this.right.height : 0;
+
+  if (this.height !== 1 + Math.max(leftH, rightH)) { throw "Height constraint failed for node " + this.key; }
+  if (this.left) { this.left.checkHeightCorrect(); }
+  if (this.right) { this.right.checkHeightCorrect(); }
+};
+
+
+/**
+ * Return the balance factor
+ */
+_AVLTree.prototype.balanceFactor = function () {
+  var leftH = this.left ? this.left.height : 0
+    , rightH = this.right ? this.right.height : 0
+    ;
+  return leftH - rightH;
+};
+
+
+/**
+ * Check that the balance factors are all between -1 and 1
+ */
+_AVLTree.prototype.checkBalanceFactors = function () {
+  if (Math.abs(this.balanceFactor()) > 1) { throw 'Tree is unbalanced at node ' + this.key; }
+
+  if (this.left) { this.left.checkBalanceFactors(); }
+  if (this.right) { this.right.checkBalanceFactors(); }
+};
+
+
+/**
+ * When checking if the BST conditions are met, also check that the heights are correct
+ * and the tree is balanced
+ */
+_AVLTree.prototype.checkIsAVLT = function () {
+  _AVLTree.super_.prototype.checkIsBST.call(this);
+  this.checkHeightCorrect();
+  this.checkBalanceFactors();
+};
+AVLTree.prototype.checkIsAVLT = function () { this.tree.checkIsAVLT(); };
+
+
+/**
+ * Perform a right rotation of the tree if possible
+ * and return the root of the resulting tree
+ * The resulting tree's nodes' heights are also updated
+ */
+_AVLTree.prototype.rightRotation = function () {
+  var q = this
+    , p = this.left
+    , b
+    , ah, bh, ch;
+
+  if (!p) { return this; }   // No change
+
+  b = p.right;
+
+  // Alter tree structure
+  if (q.parent) {
+    p.parent = q.parent;
+    if (q.parent.left === q) { q.parent.left = p; } else { q.parent.right = p; }
+  } else {
+    p.parent = null;
+  }
+  p.right = q;
+  q.parent = p;
+  q.left = b;
+  if (b) { b.parent = q; }
+
+  // Update heights
+  ah = p.left ? p.left.height : 0;
+  bh = b ? b.height : 0;
+  ch = q.right ? q.right.height : 0;
+  q.height = Math.max(bh, ch) + 1;
+  p.height = Math.max(ah, q.height) + 1;
+
+  return p;
+};
+
+
+/**
+ * Perform a left rotation of the tree if possible
+ * and return the root of the resulting tree
+ * The resulting tree's nodes' heights are also updated
+ */
+_AVLTree.prototype.leftRotation = function () {
+  var p = this
+    , q = this.right
+    , b
+    , ah, bh, ch;
+
+  if (!q) { return this; }   // No change
+
+  b = q.left;
+
+  // Alter tree structure
+  if (p.parent) {
+    q.parent = p.parent;
+    if (p.parent.left === p) { p.parent.left = q; } else { p.parent.right = q; }
+  } else {
+    q.parent = null;
+  }
+  q.left = p;
+  p.parent = q;
+  p.right = b;
+  if (b) { b.parent = p; }
+
+  // Update heights
+  ah = p.left ? p.left.height : 0;
+  bh = b ? b.height : 0;
+  ch = q.right ? q.right.height : 0;
+  p.height = Math.max(ah, bh) + 1;
+  q.height = Math.max(ch, p.height) + 1;
+
+  return q;
+};
+
+
+/**
+ * Modify the tree if its right subtree is too small compared to the left
+ * Return the new root if any
+ */
+_AVLTree.prototype.rightTooSmall = function () {
+  if (this.balanceFactor() <= 1) { return this; }   // Right is not too small, don't change
+
+  if (this.left.balanceFactor() < 0) {
+    this.left.leftRotation();
+  }
+
+  return this.rightRotation();
+};
+
+
+/**
+ * Modify the tree if its left subtree is too small compared to the right
+ * Return the new root if any
+ */
+_AVLTree.prototype.leftTooSmall = function () {
+  if (this.balanceFactor() >= -1) { return this; }   // Left is not too small, don't change
+
+  if (this.right.balanceFactor() > 0) {
+    this.right.rightRotation();
+  }
+
+  return this.leftRotation();
+};
+
+
+/**
+ * Rebalance the tree along the given path. The path is given reversed (as he was calculated
+ * in the insert and delete functions).
+ * Returns the new root of the tree
+ * Of course, the first element of the path must be the root of the tree
+ */
+_AVLTree.prototype.rebalanceAlongPath = function (path) {
+  var newRoot = this
+    , rotated
+    , i;
+
+  if (!this.key) { delete this.height; return this; }   // Empty tree
+
+  // Rebalance the tree and update all heights
+  for (i = path.length - 1; i >= 0; i -= 1) {
+    path[i].height = 1 + Math.max(path[i].left ? path[i].left.height : 0, path[i].right ? path[i].right.height : 0);
+
+    if (path[i].balanceFactor() > 1) {
+      rotated = path[i].rightTooSmall();
+      if (i === 0) { newRoot = rotated; }
+    }
+
+    if (path[i].balanceFactor() < -1) {
+      rotated = path[i].leftTooSmall();
+      if (i === 0) { newRoot = rotated; }
+    }
+  }
+
+  return newRoot;
+};
+
+
+/**
+ * Insert a key, value pair in the tree while maintaining the AVL tree height constraint
+ * Return a pointer to the root node, which may have changed
+ */
+_AVLTree.prototype.insert = function (key, value) {
+  var insertPath = []
+    , currentNode = this
+    ;
+
+  // Empty tree, insert as root
+  if (this.key === null) {
+    this.key = key;
+    this.data.push(value);
+    this.height = 1;
+    return this;
+  }
+
+  // Insert new leaf at the right place
+  while (true) {
+    // Same key: no change in the tree structure
+    if (currentNode.compareKeys(currentNode.key, key) === 0) {
+      if (currentNode.unique) {
+        throw { message: "Can't insert key " + key + ", it violates the unique constraint"
+              , key: key
+              , errorType: 'uniqueViolated'
+              };
+      } else {
+        currentNode.data.push(value);
+      }
+      return this;
+    }
+
+    insertPath.push(currentNode);
+
+    if (currentNode.compareKeys(key, currentNode.key) < 0) {
+      if (!currentNode.left) {
+        insertPath.push(currentNode.createLeftChild({ key: key, value: value }));
+        break;
+      } else {
+        currentNode = currentNode.left;
+      }
+    } else {
+      if (!currentNode.right) {
+        insertPath.push(currentNode.createRightChild({ key: key, value: value }));
+        break;
+      } else {
+        currentNode = currentNode.right;
+      }
+    }
+  }
+
+  return this.rebalanceAlongPath(insertPath);
+};
+
+// Insert in the internal tree, update the pointer to the root if needed
+AVLTree.prototype.insert = function (key, value) {
+  var newTree = this.tree.insert(key, value);
+
+  // If newTree is undefined, that means its structure was not modified
+  if (newTree) { this.tree = newTree; }
+};
+
+
+/**
+ * Delete a key or just a value and return the new root of the tree
+ * @param {Key} key
+ * @param {Value} value Optional. If not set, the whole key is deleted. If set, only this value is deleted
+ */
+_AVLTree.prototype.delete = function (key, value) {
+  var newData = [], replaceWith
+    , self = this
+    , currentNode = this
+    , deletePath = []
+    ;
+
+  if (this.key === null) { return this; }   // Empty tree
+
+  // Either no match is found and the function will return from within the loop
+  // Or a match is found and deletePath will contain the path from the root to the node to delete after the loop
+  while (true) {
+    if (currentNode.compareKeys(key, currentNode.key) === 0) { break; }
+
+    deletePath.push(currentNode);
+
+    if (currentNode.compareKeys(key, currentNode.key) < 0) {
+      if (currentNode.left) {
+        currentNode = currentNode.left;
+      } else {
+        return this;   // Key not found, no modification
+      }
+    } else {
+      // currentNode.compareKeys(key, currentNode.key) is > 0
+      if (currentNode.right) {
+        currentNode = currentNode.right;
+      } else {
+        return this;   // Key not found, no modification
+      }
+    }
+  }
+
+  // Delete only a value (no tree modification)
+  if (currentNode.data.length > 1 && value) {
+    currentNode.data.forEach(function (d) {
+      if (!currentNode.checkValueEquality(d, value)) { newData.push(d); }
+    });
+    currentNode.data = newData;
+    return this;
+  }
+
+  // Delete a whole node
+
+  // Leaf
+  if (!currentNode.left && !currentNode.right) {
+    if (currentNode === this) {   // This leaf is also the root
+      currentNode.key = null;
+      currentNode.data = [];
+      delete currentNode.height;
+      return this;
+    } else {
+      if (currentNode.parent.left === currentNode) {
+        currentNode.parent.left = null;
+      } else {
+        currentNode.parent.right = null;
+      }
+      return this.rebalanceAlongPath(deletePath);
+    }
+  }
+
+
+  // Node with only one child
+  if (!currentNode.left || !currentNode.right) {
+    replaceWith = currentNode.left ? currentNode.left : currentNode.right;
+
+    if (currentNode === this) {   // This node is also the root
+      replaceWith.parent = null;
+      return replaceWith;   // height of replaceWith is necessarily 1 because the tree was balanced before deletion
+    } else {
+      if (currentNode.parent.left === currentNode) {
+        currentNode.parent.left = replaceWith;
+        replaceWith.parent = currentNode.parent;
+      } else {
+        currentNode.parent.right = replaceWith;
+        replaceWith.parent = currentNode.parent;
+      }
+
+      return this.rebalanceAlongPath(deletePath);
+    }
+  }
+
+
+  // Node with two children
+  // Use the in-order predecessor (no need to randomize since we actively rebalance)
+  deletePath.push(currentNode);
+  replaceWith = currentNode.left;
+
+  // Special case: the in-order predecessor is right below the node to delete
+  if (!replaceWith.right) {
+    currentNode.key = replaceWith.key;
+    currentNode.data = replaceWith.data;
+    currentNode.left = replaceWith.left;
+    if (replaceWith.left) { replaceWith.left.parent = currentNode; }
+    return this.rebalanceAlongPath(deletePath);
+  }
+
+  // After this loop, replaceWith is the right-most leaf in the left subtree
+  // and deletePath the path from the root (inclusive) to replaceWith (exclusive)
+  while (true) {
+    if (replaceWith.right) {
+      deletePath.push(replaceWith);
+      replaceWith = replaceWith.right;
+    } else {
+      break;
+    }
+  }
+
+  currentNode.key = replaceWith.key;
+  currentNode.data = replaceWith.data;
+
+  replaceWith.parent.right = replaceWith.left;
+  if (replaceWith.left) { replaceWith.left.parent = replaceWith.parent; }
+
+  return this.rebalanceAlongPath(deletePath);
+};
+
+// Delete a value
+AVLTree.prototype.delete = function (key, value) {
+  var newTree = this.tree.delete(key, value);
+
+  // If newTree is undefined, that means its structure was not modified
+  if (newTree) { this.tree = newTree; }
+};
+
+
+/**
+ * Other functions we want to use on an AVLTree as if it were the internal _AVLTree
+ */
+['getNumberOfKeys', 'search', 'prettyPrint', 'executeOnEveryNode'].forEach(function (fn) {
+  AVLTree.prototype[fn] = function () {
+    return this.tree[fn].apply(this.tree, arguments);
+  };
+});
+
+
 // Interface
 module.exports = AVLTree;

lib/bst.js

@@ -30,41 +30,8 @@ /**
 
-/**
- * Create a BST similar (i.e. same options except for key and value) to the current one
- * @param {Object} options see constructor
- */
-BinarySearchTree.prototype.createSimilar = function (options) {
-  options = options || {};
-  options.unique = this.unique;
-  options.compareKeys = this.compareKeys;
-  options.checkValueEquality = this.checkValueEquality;
+// ================================
+// Methods used to test the tree
+// ================================
 
-  return new BinarySearchTree(options);
-};
 
-
 /**
- * Create the left child of this BST and return it
- */
-BinarySearchTree.prototype.createLeftChild = function (options) {
-  var leftChild = this.createSimilar(options);
-  leftChild.parent = this;
-  this.left = leftChild;
-
-  return leftChild;
-};
-
-
-/**
- * Create the right child of this BST and return it
- */
-BinarySearchTree.prototype.createRightChild = function (options) {
-  var rightChild = this.createSimilar(options);
-  rightChild.parent = this;
-  this.right = rightChild;
-
-  return rightChild;
-};
-
-
-/**
  * Get the descendant with max key
@@ -173,2 +140,3 @@ */
   this.checkInternalPointers();
+  if (this.parent) { throw "The root shouldn't have a parent"; }
 };
@@ -193,3 +161,47 @@
 
+
+// ============================================
+// Methods used to actually work on the tree
+// ============================================
+
 /**
+ * Create a BST similar (i.e. same options except for key and value) to the current one
+ * Use the same constructor (i.e. BinarySearchTree, AVLTree etc)
+ * @param {Object} options see constructor
+ */
+BinarySearchTree.prototype.createSimilar = function (options) {
+  options = options || {};
+  options.unique = this.unique;
+  options.compareKeys = this.compareKeys;
+  options.checkValueEquality = this.checkValueEquality;
+
+  return new this.constructor(options);
+};
+
+
+/**
+ * Create the left child of this BST and return it
+ */
+BinarySearchTree.prototype.createLeftChild = function (options) {
+  var leftChild = this.createSimilar(options);
+  leftChild.parent = this;
+  this.left = leftChild;
+
+  return leftChild;
+};
+
+
+/**
+ * Create the right child of this BST and return it
+ */
+BinarySearchTree.prototype.createRightChild = function (options) {
+  var rightChild = this.createSimilar(options);
+  rightChild.parent = this;
+  this.right = rightChild;
+
+  return rightChild;
+};
+
+
+/**
  * Insert a new element
@@ -273,3 +285,2 @@ */
   }
-  //this.parent.prettyPrint();
 
@@ -276,0 +287,0 @@ if (this.parent.left === this) {

package.json

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

test/bst.test.js

 var should = require('chai').should()
   , assert = require('chai').assert
-  , BinarySearchTree = require('../lib/bst')
+  , BinarySearchTree = require('../index').BinarySearchTree
   , _ = require('underscore')
@@ -467,3 +467,3 @@ , customUtils = require('../lib/customUtils')
 
-    it('Able to delete the rootif it is also a leaf', function () {
+    it('Able to delete the root if it is also a leaf', function () {
       var bst = new BinarySearchTree();
@@ -780,2 +780,85 @@
 
+  // This test performs several inserts and deletes at random, always checking the content
+  // of the tree are as expected and the binary search tree constraint is respected
+  // This test is important because it can catch bugs other tests can't
+  // By their nature, BSTs can be hard to test (many possible cases, bug at one operation whose
+  // effect begins to be felt only after several operations etc.)
+  describe('Randomized test (takes much longer than the rest of the test suite)', function () {
+    var bst = new BinarySearchTree()
+      , data = {};
+
+    // Check a bst against a simple key => [data] object
+    function checkDataIsTheSame (bst, data) {
+      var bstDataElems = [];
+
+      // bstDataElems is a simple array containing every piece of data in the tree
+      bst.executeOnEveryNode(function (node) {
+        var i;
+        for (i = 0; i < node.data.length; i += 1) {
+          bstDataElems.push(node.data[i]);
+        }
+      });
+
+      // Number of key and number of pieces of data match
+      bst.getNumberOfKeys().should.equal(Object.keys(data).length);
+      _.reduce(_.map(data, function (d) { return d.length; }), function (memo, n) { return memo + n; }, 0).should.equal(bstDataElems.length);
+
+      // Compare data
+      Object.keys(data).forEach(function (key) {
+        checkDataEquality(bst.search(key), data[key]);
+      });
+    }
+
+    // Check two pieces of data coming from the bst and data are the same
+    function checkDataEquality (fromBst, fromData) {
+      if (fromBst.length === 0) {
+        if (fromData) { fromData.length.should.equal(0); }
+      }
+
+      assert.deepEqual(fromBst, fromData);
+    }
+
+    // Tests the tree structure (deletions concern the whole tree, deletion of some data in a node is well tested above)
+    it('Inserting and deleting entire nodes', function () {
+      // You can skew to be more insertive or deletive, to test all cases
+      function launchRandomTest (nTests, proba) {
+        var i, key, dataPiece, possibleKeys;
+
+        for (i = 0; i < nTests; i += 1) {
+          if (Math.random() > proba) {   // Deletion
+            possibleKeys = Object.keys(data);
+
+            if (possibleKeys.length > 0) {
+              key = possibleKeys[Math.floor(possibleKeys.length * Math.random()).toString()];
+            } else {
+              key = Math.floor(70 * Math.random()).toString();
+            }
+
+            delete data[key];
+            bst.delete(key);
+          } else {   // Insertion
+            key = Math.floor(70 * Math.random()).toString();
+            dataPiece = Math.random().toString().substring(0, 6);
+            bst.insert(key, dataPiece);
+            if (data[key]) {
+              data[key].push(dataPiece);
+            } else {
+              data[key] = [dataPiece];
+            }
+          }
+
+          // Check the bst constraint are still met and the data is correct
+          bst.checkIsBST();
+          checkDataIsTheSame(bst, data);
+        }
+      }
+
+      launchRandomTest(1000, 0.65);
+      launchRandomTest(2000, 0.35);
+    });
+
+  });   // ==== End of 'Randomized test' ==== //
+
+
+
 });

No alert changes

Improved metrics

Total package byte prevSize

84423

increased by102.92%

Number of package files

10

increased by11.11%

Lines of code

2178

increased by111.46%

No dependency changes