Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

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

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitbddeca7

Browse files
committed
Now the updateChild could be able override by external code.
and along with insertLeafNode & removeLeafNode
1 parentefeda27 commitbddeca7

File tree

2 files changed

+112
-137
lines changed

2 files changed

+112
-137
lines changed

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

Lines changed: 111 additions & 130 deletions
Original file line numberDiff line numberDiff line change
@@ -32,22 +32,7 @@
3232
*@module data-structures/size-balanced-tree
3333
*/
3434

35-
functionCreateSBTreeClass(Node,Nil){
36-
functionupdateChild(node,newChild){
37-
varparent=node.parent;
38-
if(parent!==Nil){
39-
if(parent.right===node){
40-
parent.right=newChild;
41-
}else{
42-
parent.left=newChild;
43-
}
44-
parent.updateSize();
45-
}
46-
if(newChild!==Nil){
47-
newChild.parent=parent;
48-
}
49-
}
50-
35+
functionCreateSBTreeClass(Node,Nil,updateChild){
5136
functionLeftRotate(node,childNode){
5237
/*
5338
Before rotate:
@@ -69,9 +54,8 @@ function CreateSBTreeClass (Node, Nil) {
6954
node.right.parent=node;
7055
}
7156
childNode.left=node;
72-
updateChild(node,childNode);//Access node.parent
73-
node.parent=childNode;
74-
node.updateSize();
57+
// setting childNode's parent to node's parent
58+
updateChild(node,childNode);
7559
returnchildNode;
7660
}
7761

@@ -96,9 +80,8 @@ function CreateSBTreeClass (Node, Nil) {
9680
node.left.parent=node;
9781
}
9882
childNode.right=node;
99-
updateChild(node,childNode);//Access node.parent
100-
node.parent=childNode;
101-
node.updateSize();
83+
// setting childNode's parent to node's parent
84+
updateChild(node,childNode);
10285
returnchildNode;
10386
}
10487

@@ -122,7 +105,6 @@ function CreateSBTreeClass (Node, Nil) {
122105
node=LeftRotate(node,node.right);
123106
}
124107
}
125-
node.updateSize();
126108
if(node===savedNode){
127109
returnnode;
128110
}
@@ -146,20 +128,6 @@ function CreateSBTreeClass (Node, Nil) {
146128
returnnode;
147129
}
148130

149-
functionfindRightMost(node){
150-
while(node.right!==Nil){
151-
node=node.right;
152-
}
153-
returnnode;
154-
}
155-
156-
functionfindLeftMost(node){
157-
while(node.left!==Nil){
158-
node=node.left;
159-
}
160-
returnnode;
161-
}
162-
163131
functionfindNodeAtPos(node,pos){
164132
while(pos!==node.left.size){
165133
if(pos<node.left.size){
@@ -183,7 +151,6 @@ function CreateSBTreeClass (Node, Nil) {
183151

184152
SBTree.prototype={
185153
_root:Nil,
186-
updateChild:updateChild,
187154
getsize(){
188155
returnthis._root.size;
189156
},
@@ -208,26 +175,8 @@ function CreateSBTreeClass (Node, Nil) {
208175
},
209176
};
210177

211-
/**
212-
* Push a value to the end of tree.
213-
* Complexity: O(log N).
214-
*
215-
*@public
216-
*@method
217-
*@param {Object} value Value.
218-
*/
219-
SBTree.prototype.push=function(value){
220-
varnode=findRightMost(this._root);
221-
varnewNode=newNode(value,node,Nil,Nil,1);
222-
if(node!==Nil){
223-
node.right=newNode;
224-
}
225-
this._root=maintainSizeBalancedTree(newNode);
226-
returnnewNode;
227-
};
228-
229178
SBTree.prototype.get=function(pos){
230-
if(pos>=this._root.size){
179+
if(pos>=this.size){
231180
returnNil;
232181
}
233182
returnfindNodeAtPos(this._root,pos);
@@ -245,83 +194,97 @@ function CreateSBTreeClass (Node, Nil) {
245194
returnindex;
246195
};
247196

248-
SBTree.prototype.insert=function(pos,value){
249-
if(pos>=this._root.size){
250-
returnthis.push(value);
197+
SBTree.prototype.shiftDown=function(node){
198+
vardirection=0;
199+
while(true){
200+
if(node.left!==Nil&&node.right!==Nil){
201+
switch(direction){
202+
case0:
203+
RightRotate(node,node.left);
204+
break;
205+
case1:
206+
LeftRotate(node,node.right);
207+
break;
208+
}
209+
direction=1-direction;
210+
}elseif(node.left!==Nil){
211+
RightRotate(node,node.left);
212+
}elseif(node.right!==Nil){
213+
LeftRotate(node,node.right);
214+
}else{
215+
break;// The node could be able to removed
216+
}
251217
}
252-
varnode=findNodeAtPos(this._root,pos);
253-
varnewNode;
254-
if(node.left===Nil){
255-
newNode=newNode(value,node,Nil,Nil,1);
256-
node.left=newNode;
218+
};
219+
220+
SBTree.prototype.insertLeafNode=function(node){
221+
varparent=node.parent;
222+
while(parent!==Nil){
223+
parent.size=parent.size+1;
224+
parent=parent.parent;
225+
}
226+
};
227+
228+
SBTree.prototype.removeLeafNode=function(node){
229+
varparent=node.parent;
230+
while(parent!==Nil){
231+
parent.size=parent.size-1;
232+
parent=parent.parent;
233+
}
234+
};
235+
236+
SBTree.prototype.insert=function(pos,value){
237+
varnode=Nil;
238+
varnewNode=newNode(value,Nil,Nil,Nil,1);
239+
if(pos===this.size){
240+
if(pos>0){
241+
node=findNodeAtPos(this._root,pos-1);
242+
node.right=newNode;
243+
}
257244
}else{
258-
node=findRightMost(node.left);
259-
newNode=newNode(value,node,Nil,Nil,1);
260-
node.right=newNode;
245+
node=findNodeAtPos(this._root,pos);
246+
if(node.left!==Nil){
247+
this.shiftDown(node);
248+
}
249+
node.left=newNode;
261250
}
251+
newNode.parent=node;
252+
this.insertLeafNode(newNode);
262253
this._root=maintainSizeBalancedTree(newNode);
263254
returnnewNode;
264255
};
265256

257+
/**
258+
* Push a value to the end of tree.
259+
* Complexity: O(log N).
260+
*
261+
*@public
262+
*@method
263+
*@param {Object} value Value.
264+
*/
265+
SBTree.prototype.push=function(value){
266+
this.insert(this.size,value);
267+
};
268+
269+
SBTree.prototype.removeNode=function(node){
270+
this.shiftDown(node);
271+
varmaintainNode=node.parent;
272+
if(maintainNode.left===node){
273+
maintainNode.left=Nil;
274+
}elseif(maintainNode.right===node){
275+
maintainNode.right=Nil;
276+
}
277+
this.removeLeafNode(node);
278+
this._root=maintainSizeBalancedTree(maintainNode);
279+
returnnode;
280+
};
281+
266282
SBTree.prototype.remove=function(pos){
267283
if(pos>=this._root.size){
268284
returnNil;// There is no element to remove
269285
}
270286
varnode=findNodeAtPos(this._root,pos);
271-
varmaintainNode;
272-
273-
/*
274-
Before remove:
275-
P (node's parent, be notices,
276-
| N either be left child or right child of P)
277-
|
278-
N(node)
279-
/ \
280-
L R
281-
\
282-
\
283-
LRM(Left-Rightmost)
284-
\
285-
Nil
286-
After remove node N:
287-
P(node's parent)
288-
/
289-
L
290-
\
291-
\
292-
LRM(Left-Rightmost)
293-
\
294-
R
295-
296-
N(node) is wild node that was removed
297-
298-
*/
299-
if(node.left!==Nil){
300-
varLRM=findRightMost(node.left);
301-
updateChild(node,node.left);
302-
LRM.right=node.right;
303-
if(LRM.right===Nil){
304-
maintainNode=LRM;
305-
}else{
306-
LRM.right.parent=LRM;
307-
maintainNode=LRM.right;
308-
}
309-
}elseif(node.right!==Nil){
310-
varRLM=findLeftMost(node.right);
311-
updateChild(node,node.right);
312-
RLM.left=node.left;
313-
if(RLM.left===Nil){
314-
maintainNode=RLM;
315-
}else{
316-
RLM.left.parent=RLM;
317-
maintainNode=RLM.left;
318-
}
319-
}else{
320-
updateChild(node,Nil);
321-
maintainNode=node.parent;
322-
}
323-
this._root=maintainSizeBalancedTree(maintainNode);
324-
returnnode;
287+
returnthis.removeNode(node);
325288
};
326289

327290
returnSBTree;
@@ -349,6 +312,14 @@ function CreateSBTreeClass (Node, Nil) {
349312
this.height=0;
350313
};
351314

315+
varcreateNil=function(Node,value){
316+
varNil=newNode(value,null,null,null,0);
317+
Nil.parent=Nil;
318+
Nil.left=Nil;
319+
Nil.right=Nil;
320+
returnNil;
321+
};
322+
352323
/**
353324
* Update node's size.
354325
*
@@ -360,12 +331,22 @@ function CreateSBTreeClass (Node, Nil) {
360331
this.height=Math.max(this.left.height,this.right.height)+1;
361332
};
362333

363-
varcreateNil=function(Node,value){
364-
varNil=newNode(value,null,null,null,0);
365-
Nil.parent=Nil;
366-
Nil.left=Nil;
367-
Nil.right=Nil;
368-
returnNil;
334+
// node, childNode must not be Nil,
335+
// if the childNode turn out to be the root, the parent should be Nil
336+
varupdateChild=function(node,childNode){
337+
varparent=node.parent;
338+
node.parent=childNode;
339+
childNode.parent=parent;
340+
341+
node.updateSize();
342+
childNode.updateSize();
343+
if(parent.right===node){
344+
parent.right=childNode;
345+
parent.updateSize();
346+
}elseif(parent.left===node){
347+
parent.left=childNode;
348+
parent.updateSize();
349+
}// otherwise parent is Nil
369350
};
370351

371352
varNode=function(){
@@ -379,11 +360,11 @@ function CreateSBTreeClass (Node, Nil) {
379360
exports.NodeConstructor=NodeConstructor;
380361
exports.createNil=createNil;
381362
exports.updateSize=updateSize;
363+
exports.updateChild=updateChild;
382364
exports.CreateSBTreeClass=CreateSBTreeClass;
383365

384366
exports.Node=Node;
385367
exports.Nil=Nil;
386-
exports.SBTree=CreateSBTreeClass(Node,Nil);
387-
exports.updateChild=exports.SBTree.prototype.updateChild;
368+
exports.SBTree=CreateSBTreeClass(Node,Nil,updateChild);
388369

389370
})(typeofmodule==='undefined' ?window :module.exports);

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

Lines changed: 1 addition & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -64,7 +64,6 @@ describe('SBTree', function () {
6464
}
6565

6666
it('test updateChild',function(){
67-
updateChild(Nil,Nil);
6867
checkNil();
6968
varroot=newNode(10,Nil,Nil,Nil,1);
7069
varleft=newNode(5,root,Nil,Nil,1);
@@ -80,12 +79,7 @@ describe('SBTree', function () {
8079
updateChild(left,leftLeft);
8180
expect(leftLeft.parent).toBe(root);
8281
expect(root.left).toBe(leftLeft);
83-
updateChild(leftLeft,Nil);
84-
checkNil();
85-
expect(root.left).toBe(Nil);
86-
expect(root.size).toBe(2);
87-
updateChild(Nil,right);
88-
expect(right.parent).toBe(Nil);
82+
expect(root.left.size).toBe(1);
8983
checkNil();
9084
});
9185
// Returns a random integer between min (included) and max (excluded)

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp