Commitfe9fd72

committed

Getting the maintainNode to be the leaf-most node, so that the updateSize would always be right and

the rotate always working.

1 parentd2f065a commitfe9fd72Copy full SHA for fe9fd72

File tree

+11

-15

lines changed

+11

-15

lines changed

Lines changed: 11 additions & 15 deletions

Original file line number	Diff line number	Diff line change
`@@ -75,17 +75,17 @@`
`75`	`75`
`76`	`76`	`functionupdateChild(node,newChild){`
`77`	`77`	`letparent=node.parent;`
`78`		`-if(parent!==Nil){`
`79`		`-if(parent.right===node){`
`80`		`-parent.right=newChild;`
`81`		`-newChild.parent=parent;`
`82`		`-}else{`
`83`		`-parent.left=newChild;`
`84`		`-newChild.parent=parent;`
`85`		`-}`
`86`		`-returnparent;`
	`78`	`+if(parent.right===node){`
	`79`	`+parent.right=newChild;`
	`80`	`+newChild.parent=parent;`
	`81`	`+}elseif(parent.left===node){`
	`82`	`+parent.left=newChild;`
	`83`	`+newChild.parent=parent;`
	`84`	`+}`
	`85`	`+if(newChild!==Nil){`
	`86`	`+returnnewChild;`
`87`	`87`	`}`
`88`		`-returnnewChild;`
	`88`	`+returnparent;`
`89`	`89`	`}`
`90`	`90`
`91`	`91`	`functionLeftRotate(node,childNode){`
`@@ -267,12 +267,8 @@`
`267`	`267`	`updateChild(node,node.left)`
`268`	`268`	`LRM.right=node.right`
`269`	`269`	`LRM.right.parent=LRM;`
`270`		`-maintainNode=LRM;`
	`270`	`+maintainNode=node.right;`
`271`	`271`	`}`
`272`		`-if(maintainNode!==Nil){`
`273`		`-maintainNode.updateSize();`
`274`		`-}`
`275`		`-`
`276`	`272`	`this._root=maintainSizeBalancedTree(maintainNode);`
`277`	`273`	`returnremovedNode;`
`278`	`274`	`};`

Comments

(0)