|
75 | 75 |
|
76 | 76 | functionupdateChild(node,newChild){ |
77 | 77 | letparent=node.parent; |
78 | | -if(parent===Nil){ |
79 | | -newChild.parent=parent; |
80 | | -returnnewChild; |
81 | | -} |
82 | | -if(parent.right===node){ |
83 | | -parent.right=newChild; |
84 | | -}else{ |
85 | | -parent.left=newChild; |
86 | | -} |
87 | | -if(newChild===Nil){ |
| 78 | +if(parent!==Nil){ |
| 79 | +if(parent.right===node){ |
| 80 | +parent.right=newChild; |
| 81 | +}else{ |
| 82 | +parent.left=newChild; |
| 83 | +} |
88 | 84 | parent.updateSize(); |
89 | | -returnparent; |
90 | 85 | } |
91 | | -newChild.parent=parent; |
92 | | -returnnewChild; |
| 86 | +if(newChild!==Nil){ |
| 87 | +newChild.parent=parent; |
| 88 | +} |
93 | 89 | } |
94 | 90 | exports.updateChild=updateChild; |
95 | 91 |
|
|
194 | 190 | returnnode; |
195 | 191 | } |
196 | 192 |
|
| 193 | +functionfindLeftMost(node){ |
| 194 | +while(node.left!==Nil){ |
| 195 | +node=node.left; |
| 196 | +} |
| 197 | +returnnode; |
| 198 | +} |
| 199 | + |
197 | 200 | functionfindNodeAtPos(node,pos){ |
198 | 201 | while(pos!=node.left.size){ |
199 | 202 | if(pos<node.left.size){ |
|
270 | 273 | returnNil;// There is no element to remove |
271 | 274 | } |
272 | 275 | letnode=findNodeAtPos(this._root,pos); |
273 | | -letremovedNode=node; |
274 | 276 | letmaintainNode; |
275 | | -if(node.right===Nil){ |
276 | | -maintainNode=updateChild(node,node.left) |
277 | | -}elseif(node.left===Nil){ |
278 | | -maintainNode=updateChild(node,node.right) |
279 | | -}else{ |
280 | | -/* |
281 | | - Before remove: |
282 | | - P(node's parent, be notices, N either be left child or right child of P) |
283 | | - | |
284 | | - N(node) |
285 | | - / \ |
286 | | - L R |
| 277 | + |
| 278 | +/* |
| 279 | + Before remove: |
| 280 | + P(node's parent, be notices, N either be left child or right child of P) |
| 281 | + | |
| 282 | + N(node) |
| 283 | + / \ |
| 284 | + L R |
| 285 | + \ |
| 286 | + \ |
| 287 | + LRM(Left-Rightmost) |
| 288 | + \ |
| 289 | + Nil |
| 290 | + After remove node N: |
| 291 | + P(node's parent) |
| 292 | + / |
| 293 | + L |
287 | 294 | \ |
288 | 295 | \ |
289 | 296 | LRM(Left-Rightmost) |
290 | 297 | \ |
291 | | - Nil |
292 | | - After remove node N: |
293 | | - P(node's parent) |
294 | | - / |
295 | | - L |
296 | | - \ |
297 | | - \ |
298 | | - LRM(Left-Rightmost) |
299 | | - \ |
300 | | - R |
| 298 | + R |
301 | 299 |
|
302 | | - N(node) is wild node that was removed |
303 | | -
|
304 | | - */ |
| 300 | + N(node) is wild node that was removed |
| 301 | +
|
| 302 | + */ |
| 303 | +if(node.left!==Nil){ |
305 | 304 | letLRM=findRightMost(node.left); |
306 | 305 | updateChild(node,node.left) |
307 | 306 | LRM.right=node.right |
308 | | -LRM.right.parent=LRM; |
309 | | -maintainNode=LRM.right; |
| 307 | +if(LRM.right===Nil){ |
| 308 | +maintainNode=LRM; |
| 309 | +}else{ |
| 310 | +LRM.right.parent=LRM; |
| 311 | +maintainNode=LRM.right; |
| 312 | +} |
| 313 | +}elseif(node.right!==Nil){ |
| 314 | +letRLM=findLeftMost(node.right); |
| 315 | +updateChild(node,node.right) |
| 316 | +RLM.left=node.left |
| 317 | +if(RLM.left===Nil){ |
| 318 | +maintainNode=RLM; |
| 319 | +}else{ |
| 320 | +RLM.left.parent=RLM; |
| 321 | +maintainNode=RLM.left; |
| 322 | +} |
| 323 | +}else{ |
| 324 | +updateChild(node,Nil) |
| 325 | +maintainNode=node.parent; |
310 | 326 | } |
311 | 327 | this._root=maintainSizeBalancedTree(maintainNode); |
312 | | -returnremovedNode; |
| 328 | +returnnode; |
313 | 329 | }; |
314 | 330 |
|
315 | 331 |
|
|