Commit160fdef

committed

Using standard maintain, and the delete operation have problems.

1 parent61807b0 commit160fdefCopy full SHA for 160fdef

File tree

2 files changed

+35

-9

lines changed

src/data-structures
- size-balanced-tree.js
test/data-structures
- size-balanced-tree.spec.js

2 files changed

+35

-9

lines changed

`‎src/data-structures/size-balanced-tree.js`

Lines changed: 34 additions & 8 deletions

Original file line number	Diff line number	Diff line change
`@@ -143,20 +143,46 @@`
`143`	`143`	`returnchildNode;`
`144`	`144`	`}`
`145`	`145`
	`146`	`+functionmaintain(node,leftChild){`
	`147`	`+if(node===Nil){`
	`148`	`+returnnode;`
	`149`	`+}`
	`150`	`+varsavedNode=node;`
	`151`	`+if(leftChild){`
	`152`	`+if(node.left.left.size>node.right.size){`
	`153`	`+node=RightRotate(node,node.left);`
	`154`	`+}elseif(node.left.right.size>node.right.size){`
	`155`	`+LeftRotate(node.left,node.left.right);`
	`156`	`+node=RightRotate(node,node.left);`
	`157`	`+}`
	`158`	`+}else{`
	`159`	`+if(node.right.right.size>node.left.size){`
	`160`	`+node=LeftRotate(node,node.right);`
	`161`	`+}elseif(node.right.left.size>node.left.size){`
	`162`	`+RightRotate(node.right,node.right.left);`
	`163`	`+node=LeftRotate(node,node.right);`
	`164`	`+}`
	`165`	`+}`
	`166`	`+node.updateSize();`
	`167`	`+if(node===savedNode){`
	`168`	`+returnnode;`
	`169`	`+}`
	`170`	`+maintain(node.left,false);`
	`171`	`+maintain(node.right,true);`
	`172`	`+node=maintain(node,true);`
	`173`	`+node=maintain(node,false);`
	`174`	`+returnnode;`
	`175`	`+}`
	`176`	`+`
`146`	`177`	`functionmaintainSizeBalancedTree(node){`
`147`	`178`	`while(node.parent!==Nil){`
`148`	`179`	`letchildNode=node;`
`149`	`180`	`node=node.parent;`
`150`		`-if(node.right===childNode){`
`151`		`-if(childNode.right.size>node.left.size){`
`152`		`-node=LeftRotate(node,childNode);`
`153`		`-}`
	`181`	`+if(node.left==childNode){`
	`182`	`+node=maintain(node,true);`
`154`	`183`	`}else{`
`155`		`-if(childNode.left.size>node.right.size){`
`156`		`-node=RightRotate(node,childNode);`
`157`		`-}`
	`184`	`+node=maintain(node,false);`
`158`	`185`	`}`
`159`		`-node.updateSize();`
`160`	`186`	`}`
`161`	`187`	`returnnode;`
`162`	`188`	`}`

`‎test/data-structures/size-balanced-tree.spec.js`

Lines changed: 1 addition & 1 deletion

Original file line number	Diff line number	Diff line change
`@@ -143,7 +143,7 @@ describe('SBTree', function () {`
`143`	`143`	`expect(node.value).toBe(expectedArray[i]);`
`144`	`144`	`}`
`145`	`145`	`console.log(maxHeight);`
`146`		`-for(vari=0;i<50000;++i){`
	`146`	`+for(vari=0;i<90000;++i){`
`147`	`147`	`varremovedPos=getRandomInt(0,sTree.size);`
`148`	`148`	`sTree.remove(removedPos);`
`149`	`149`	`expectedArray.splice(removedPos,1);`

0 commit comments

Comments

(0)

Movatterモバイル変換

Navigation Menu

Search code, repositories, users, issues, pull requests...

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Commit160fdef

File tree

2 files changed

2 files changed

`‎src/data-structures/size-balanced-tree.js`

`‎test/data-structures/size-balanced-tree.spec.js`

0 commit comments