Fixes updateChild and the usage of updateChild

lygstate · lygstate · commit 46f29d48e45f · 2015-09-23T03:45:57.000+08:00
diff --git a/src/data-structures/size-balanced-tree.js b/src/data-structures/size-balanced-tree.js
@@ -33,14 +33,7 @@
 
   'use strict';
 
-  var Nil = {
-    parent: Nil,
-    left: Nil,
-    right: Nil,
-    size: 0,
-  };
   
-  exports.Nil = Nil;
 
   /**
    * Node of the Size-Balanced tree.
@@ -72,21 +65,30 @@
   };
 
   exports.Node = Node;
+  var Nil = new Node(null, null, null, null, 0);
+  Nil.parent = Nil;
+  Nil.left = Nil;
+  Nil.right = Nil;
+  exports.Nil = Nil;
 
   function updateChild(node, newChild) {
     let parent = node.parent;
+    if (parent === Nil) {
+      newChild.parent = parent;
+      return newChild;
+    }
     if (parent.right === node) {
       parent.right = newChild;
-      newChild.parent = parent;
-    } else if (parent.left === node) {
+    } else {
       parent.left = newChild;
-      newChild.parent = parent;
     }
-    if (newChild !== Nil) {
-      return newChild;
+    if (newChild === Nil) {
+      return parent;
     }
-    return parent;
+    newChild.parent = parent;
+    return newChild;
   }
+  exports.updateChild = updateChild;
 
   function LeftRotate(node, childNode) {
     /*
@@ -107,8 +109,8 @@
     node.right = childNode.left;
     node.right.parent = node;
     childNode.left = node;
-    childNode.left.parent = childNode;
-    updateChild(node, childNode)
+    updateChild(node, childNode) //Access node.parent
+    node.parent = childNode;
     node.updateSize();
     return childNode;
   }
@@ -132,8 +134,8 @@
     node.left = childNode.right;
     node.left.parent = node;
     childNode.right = node;
-    childNode.right.parent = childNode;
-    updateChild(node, childNode)
+    updateChild(node, childNode) //Access node.parent
+    node.parent = childNode;
     node.updateSize();
     return childNode;
   }
@@ -156,14 +158,14 @@
     return node;
   }
 
-  function findRightMost = function(node) {
+  function findRightMost(node) {
     while (node.right !== Nil) {
       node = node.right;
     }
     return node;
   }
 
-  function findNodeAtPos = function(node, pos) {
+  function findNodeAtPos(node, pos) {
     while (pos != node.left.size) {
       if (pos < node.left.size) {
         node = node.left;
@@ -185,6 +187,13 @@
     this._root = Nil;
   };
 
+  
+  exports.SBTree.prototype = {
+    get size() {
+      return this._root.size;
+    },
+  }
+ 
   /**
    * Push a value to the end of tree.<br><br>
    * Complexity: O(log N).
@@ -273,8 +282,5 @@
     return removedNode;
   };
 
-  exports.SBTree.prototype.size = function() {
-    return this._root.size;
-  }
 
 })(typeof window === 'undefined' ? module.exports : window);
diff --git a/test/data-structures/size-balanced-tree.spec.js b/test/data-structures/size-balanced-tree.spec.js
@@ -0,0 +1,85 @@
+'use strict';
+
+var mod = require('../../src/data-structures/size-balanced-tree.js');
+var Node = mod.Node;
+var Nil = mod.Nil;
+var SBTree = mod.SBTree;
+var updateChild = mod.updateChild;
+
+describe('Node', function () {
+  it('should be a constructor function', function () {
+    expect(typeof Node).toBe('function');
+  });
+  it('should be a construct properly', function () {
+    var node = new Node(10, Nil, Nil, Nil, 1);
+    expect(node.value).toBe(10);
+    expect(node.left).toBe(Nil);
+    expect(node.right).toBe(Nil);
+    expect(node.parent).toBe(Nil);
+    expect(node.size).toBe(1);
+  });
+  it('should reference children/parent properly', function () {
+    var root = new Node(10, Nil, Nil, Nil, 1);
+    var left = new Node(5, root, Nil, Nil, 1);
+    var right = new Node(15, root, Nil, Nil, 1);
+    root.left = left;
+    root.right = right;
+    expect(root.value).toBe(10);
+    expect(root.left).toBe(left);
+    expect(root.right).toBe(right);
+    expect(root.parent).toBe(Nil);
+    expect(right.parent).toBe(root);
+    expect(left.parent).toBe(root);
+    expect(right.size).toBe(1);
+    expect(left.size).toBe(1);
+    expect(root.size).toBe(1);
+    root.updateSize();
+    expect(root.size).toBe(3);
+  });
+});
+
+describe('SBTree', function () {
+  it('should be a constructor function', function () {
+    expect(typeof SBTree).toBe('function');
+  });
+  it('should start with null root', function () {
+    expect(new SBTree()._root).toBe(Nil);
+  });
+  it('should insert and remove correctly', function () {
+    var sTree = new SBTree();
+    expect(sTree.size).toBe(0);
+    sTree.insert(0, 10);
+    expect(sTree.size).toBe(1);
+    sTree.remove(0);
+    expect(sTree.size).toBe(0);
+    expect(sTree._root).toBe(Nil);
+  });
+
+  function checkNil() {
+    expect(Nil.size).toBe(0);
+    expect(Nil.left).toBe(Nil);
+    expect(Nil.right).toBe(Nil);
+    expect(Nil.parent).toBe(Nil);
+    expect(Nil.value).toBe(null);
+  }
+  it('test updateChild', function() {
+    var e = updateChild(Nil, Nil);
+    checkNil();
+    expect(e).toBe(Nil);
+    var root = new Node(10, Nil, Nil, Nil, 1);
+    var left = new Node(5, root, Nil, Nil, 1);
+    var right = new Node(15, root, Nil, Nil, 1);
+    var leftLeft = new Node(10, left, Nil, Nil, 1);
+    left.left = leftLeft;
+    root.left = left;
+    root.right = right;
+    updateChild(left, leftLeft);
+    expect(leftLeft.parent).toBe(root);
+    expect(root.left).toBe(leftLeft);
+    updateChild(leftLeft, Nil);
+    checkNil();
+    expect(root.left).toBe(Nil);
+    updateChild(Nil, right);
+    expect(right.parent).toBe(Nil);
+  });
+});
