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

Commitd3673b0

Browse files
committed
Pass the whole gulp build.
1 parent2854031 commitd3673b0

File tree

2 files changed

+41
-38
lines changed

2 files changed

+41
-38
lines changed

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

Lines changed: 34 additions & 32 deletions
Original file line numberDiff line numberDiff line change
@@ -30,11 +30,8 @@
3030
*@module data-structures/size-balanced-tree
3131
*/
3232
(function(exports){
33-
3433
'use strict';
3534

36-
37-
3835
/**
3936
* Node of the Size-Balanced tree.
4037
*
@@ -101,14 +98,16 @@
10198
10299
childNode
103100
/ \
104-
node CR
101+
node CR
105102
/ \
106103
NL CL
107104
*/
108105
node.right=childNode.left;
109-
if(node.right!==Nil)node.right.parent=node;
106+
if(node.right!==Nil){
107+
node.right.parent=node;
108+
}
110109
childNode.left=node;
111-
updateChild(node,childNode)//Access node.parent
110+
updateChild(node,childNode);//Access node.parent
112111
node.parent=childNode;
113112
node.updateSize();
114113
returnchildNode;
@@ -126,14 +125,16 @@
126125
127126
childNode
128127
/ \
129-
CL node
128+
CL node
130129
/ \
131130
CR NR
132131
*/
133132
node.left=childNode.right;
134-
if(node.left!==Nil)node.left.parent=node;
133+
if(node.left!==Nil){
134+
node.left.parent=node;
135+
}
135136
childNode.right=node;
136-
updateChild(node,childNode)//Access node.parent
137+
updateChild(node,childNode);//Access node.parent
137138
node.parent=childNode;
138139
node.updateSize();
139140
returnchildNode;
@@ -174,7 +175,7 @@
174175
while(node.parent!==Nil){
175176
varchildNode=node;
176177
node=node.parent;
177-
if(node.left==childNode){
178+
if(node.left===childNode){
178179
node=maintain(node,true);
179180
}else{
180181
node=maintain(node,false);
@@ -198,12 +199,12 @@
198199
}
199200

200201
functionfindNodeAtPos(node,pos){
201-
while(pos!=node.left.size){
202+
while(pos!==node.left.size){
202203
if(pos<node.left.size){
203204
node=node.left;
204205
}else{
205206
pos-=node.left.size;
206-
--pos;//The node element should be decrement by 1
207+
pos-=1;//The node element should be decrement by 1
207208
node=node.right;
208209
}
209210
}
@@ -220,13 +221,12 @@
220221
this._root=Nil;
221222
};
222223

223-
224224
exports.SBTree.prototype={
225225
getsize(){
226226
returnthis._root.size;
227227
},
228-
}
229-
228+
};
229+
230230
/**
231231
* Push a value to the end of tree.<br><br>
232232
* Complexity: O(log N).
@@ -238,21 +238,23 @@
238238
exports.SBTree.prototype.push=function(value){
239239
varnode=findRightMost(this._root);
240240
varnewNode=newNode(value,node,Nil,Nil,1);
241-
if(node!==Nil)node.right=newNode;
241+
if(node!==Nil){
242+
node.right=newNode;
243+
}
242244
this._root=maintainSizeBalancedTree(newNode);
243245
returnnewNode;
244246
};
245247

246-
exports.SBTree.prototype.get=function(pos){
248+
exports.SBTree.prototype.get=function(pos){
247249
if(pos>=this._root.size){
248250
returnNil;
249251
}
250252
returnfindNodeAtPos(this._root,pos);
251253
};
252254

253-
exports.SBTree.prototype.getIndex=function(node){
255+
exports.SBTree.prototype.getIndex=function(node){
254256
varindex=node.left.size;
255-
while(node!=this._root){
257+
while(node!==this._root){
256258
varparent=node.parent;
257259
if(parent.right===node){
258260
index+=parent.left.size+1;
@@ -262,12 +264,12 @@
262264
returnindex;
263265
};
264266

265-
exports.SBTree.prototype.insert=function(pos,value){
267+
exports.SBTree.prototype.insert=function(pos,value){
266268
if(pos>=this._root.size){
267-
returnthis.push(value)
269+
returnthis.push(value);
268270
}
269271
varnode=findNodeAtPos(this._root,pos);
270-
varnewNode
272+
varnewNode;
271273
if(node.left===Nil){
272274
newNode=newNode(value,node,Nil,Nil,1);
273275
node.left=newNode;
@@ -280,7 +282,7 @@
280282
returnnewNode;
281283
};
282284

283-
exports.SBTree.prototype.remove=function(pos){
285+
exports.SBTree.prototype.remove=function(pos){
284286
if(pos>=this._root.size){
285287
returnNil;// There is no element to remove
286288
}
@@ -289,7 +291,8 @@
289291

290292
/*
291293
Before remove:
292-
P(node's parent, be notices, N either be left child or right child of P)
294+
P (node's parent, be notices,
295+
| N either be left child or right child of P)
293296
|
294297
N(node)
295298
/ \
@@ -302,20 +305,20 @@
302305
After remove node N:
303306
P(node's parent)
304307
/
305-
L
308+
L
306309
\
307310
\
308311
LRM(Left-Rightmost)
309312
\
310313
R
311314
312315
N(node) is wild node that was removed
313-
316+
314317
*/
315318
if(node.left!==Nil){
316319
varLRM=findRightMost(node.left);
317-
updateChild(node,node.left)
318-
LRM.right=node.right
320+
updateChild(node,node.left);
321+
LRM.right=node.right;
319322
if(LRM.right===Nil){
320323
maintainNode=LRM;
321324
}else{
@@ -324,21 +327,20 @@
324327
}
325328
}elseif(node.right!==Nil){
326329
varRLM=findLeftMost(node.right);
327-
updateChild(node,node.right)
328-
RLM.left=node.left
330+
updateChild(node,node.right);
331+
RLM.left=node.left;
329332
if(RLM.left===Nil){
330333
maintainNode=RLM;
331334
}else{
332335
RLM.left.parent=RLM;
333336
maintainNode=RLM.left;
334337
}
335338
}else{
336-
updateChild(node,Nil)
339+
updateChild(node,Nil);
337340
maintainNode=node.parent;
338341
}
339342
this._root=maintainSizeBalancedTree(maintainNode);
340343
returnnode;
341344
};
342345

343-
344346
})(typeofmodule==='undefined' ?window :module.exports);

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

Lines changed: 7 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -62,7 +62,8 @@ describe('SBTree', function () {
6262
expect(Nil.parent).toBe(Nil);
6363
expect(Nil.value).toBe(null);
6464
}
65-
it('test updateChild',function(){
65+
66+
it('test updateChild',function(){
6667
updateChild(Nil,Nil);
6768
checkNil();
6869
varroot=newNode(10,Nil,Nil,Nil,1);
@@ -149,15 +150,15 @@ describe('SBTree', function () {
149150
checkNil();
150151
});
151152

152-
it('test getIndex',function(){
153+
it('test getIndex',function(){
153154
varsTree=newSBTree();
154-
for(leti=0;i<10000;++i){
155-
letkey=i.toString();
155+
for(vari=0;i<10000;++i){
156+
varkey=i.toString();
156157
sTree.push(key);
157158
}
158159

159-
for(leti=0;i<100;++i){
160-
letitem=sTree.get(i);
160+
for(vari=0;i<100;++i){
161+
varitem=sTree.get(i);
161162
expect(item.value).toBe(i.toString());
162163
expect(sTree.getIndex(item)).toBe(i);
163164
}

0 commit comments

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