Fixes updateChild with updateSize when the newChild is Nil and the parent is not Nil.

lygstate · lygstate · commit b201487a00b7 · 2015-09-23T04:28:04.000+08:00
diff --git a/src/data-structures/size-balanced-tree.js b/src/data-structures/size-balanced-tree.js
@@ -83,6 +83,7 @@
       parent.left = newChild;
     }
     if (newChild === Nil) {
+      parent.updateSize();
       return parent;
     }
     newChild.parent = parent;
@@ -277,7 +278,7 @@
       updateChild(node, node.left)
       LRM.right = node.right
       LRM.right.parent = LRM;
-      maintainNode = node.right;
+      maintainNode = LRM.right;
     }
     this._root = maintainSizeBalancedTree(maintainNode);
     return removedNode;
diff --git a/test/data-structures/size-balanced-tree.spec.js b/test/data-structures/size-balanced-tree.spec.js
@@ -71,20 +71,25 @@ describe('SBTree', function () {
     var right = new Node(15, root, Nil, Nil, 1);
     var leftLeft = new Node(10, left, Nil, Nil, 1);
     left.left = leftLeft;
+    left.updateSize();
     root.left = left;
     root.right = right;
+    root.updateSize();
+    expect(root.size).toBe(4);
+
     updateChild(left, leftLeft);
     expect(leftLeft.parent).toBe(root);
     expect(root.left).toBe(leftLeft);
     updateChild(leftLeft, Nil);
     checkNil();
     expect(root.left).toBe(Nil);
+    expect(root.size).toBe(2);
     updateChild(Nil, right);
     expect(right.parent).toBe(Nil);
     checkNil();
   });
 
-  it('push and get 100000 elements', function () {
+  it('push and get 100000 elements, remove the array by always remove the first/last element', function () {
     var sTree = new SBTree();
     for (var i = 0; i < 100000; ++i) {
       sTree.push(i);
@@ -93,5 +98,22 @@ describe('SBTree', function () {
     for (var i = 0; i < 100000; ++i) {
       expect(sTree.get(i).value).toBe(i);
     }
+    for (var i = 0; i < 100000; ++i) {
+      expect(sTree.get(0).value).toBe(i);
+      var node = sTree.remove(0); // Always remove the first element;
+      expect(node.value).toBe(i);
+    }
+    checkNil();
+    expect(sTree._root).toBe(Nil);
+    var count = 10000;
+    for (var i = 0; i < count; ++i) {
+      sTree.push(i);
+    }
+    for (var i = 0; i < count; ++i) {
+      var node = sTree.remove(count - i - 1); // Always remove the last element;
+      expect(node.value).toBe(count - i - 1);
+      expect(sTree.size).toBe(count - i - 1);
+    }
+    checkNil();
   });
 });

Original file line number	Diff line number	Diff line change
`@@ -83,6 +83,7 @@`
`83`	`83`	`parent.left = newChild;`
`84`	`84`	`}`
`85`	`85`	`if (newChild === Nil) {`
	`86`	`+ parent.updateSize();`
`86`	`87`	`return parent;`
`87`	`88`	`}`
`88`	`89`	`newChild.parent = parent;`
`@@ -277,7 +278,7 @@`
`277`	`278`	`updateChild(node, node.left)`
`278`	`279`	`LRM.right = node.right`
`279`	`280`	`LRM.right.parent = LRM;`
`280`		`- maintainNode = node.right;`
	`281`	`+ maintainNode = LRM.right;`
`281`	`282`	`}`
`282`	`283`	`this._root = maintainSizeBalancedTree(maintainNode);`
`283`	`284`	`return removedNode;`