Commit9832fb6

committed

Checking the maxHeight properly.

1 parent62700e1 commit9832fb6Copy full SHA for 9832fb6

File tree

+10

-4

lines changed

+10

-4

lines changed

Lines changed: 2 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -52,6 +52,7 @@`
`52`	`52`	`this.left=left;`
`53`	`53`	`this.right=right;`
`54`	`54`	`this.size=size;`
	`55`	`+this.height=0;`
`55`	`56`	`}`
`56`	`57`
`57`	`58`	`/**`
`@@ -62,6 +63,7 @@`
`62`	`63`	`*/`
`63`	`64`	`Node.prototype.updateSize=function(){`
`64`	`65`	`this.size=this.left.size+this.right.size+1;`
	`66`	`+this.height=Math.max(this.left.height,this.right.height)+1;`
`65`	`67`	`};`
`66`	`68`
`67`	`69`	`exports.Node=Node;`

Lines changed: 8 additions & 4 deletions

Original file line number	Diff line number	Diff line change
`@@ -91,14 +91,18 @@ describe('SBTree', function () {`
`91`	`91`
`92`	`92`	`it('push and get 100000 elements, remove the array by always remove the first/last element',function(){`
`93`	`93`	`varsTree=newSBTree();`
`94`		`-for(vari=0;i<100000;++i){`
	`94`	`+for(vari=0;i<2000000;++i){`
`95`	`95`	`sTree.push(i);`
`96`	`96`	`}`
`97`	`97`	`checkNil();`
`98`		`-for(vari=0;i<100000;++i){`
`99`		`-expect(sTree.get(i).value).toBe(i);`
	`98`	`+letmaxHeight=0;`
	`99`	`+for(vari=0;i<2000000;++i){`
	`100`	`+varnode=sTree.get(i);`
	`101`	`+maxHeight=Math.max(maxHeight,node.height);`
	`102`	`+expect(node.value).toBe(i);`
`100`	`103`	`}`
`101`		`-for(vari=0;i<100000;++i){`
	`104`	`+expect(maxHeight).toBe(21);`
	`105`	`+for(vari=0;i<2000000;++i){`
`102`	`106`	`expect(sTree.get(0).value).toBe(i);`
`103`	`107`	`varnode=sTree.remove(0);// Always remove the first element;`
`104`	`108`	`expect(node.value).toBe(i);`

Comments

(0)