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

Commitfed9e0e

Browse files
committed
Merge remote-tracking branch 'sbt/master'
* sbt/master: (21 commits) Do not check height. Now the updateChild could be able override by external code. and along with insertLeafNode & removeLeafNode Add binarySearch function. Use node 0.12 Pass the whole gulp build. Replace let with var Test index. Switch module & window. No need the maxHeight Consistence the delete operation. Do not check return of updateChild Using standard maintain, and the delete operation have problems. Testing random remove properly. Testing random insert properly. Checking the maxHeight properly. Testing insert properly. Fixes updateChild with updateSize when the newChild is Nil and the parent is not Nil. Fixes of the Nil pointer problem, testing push 10000 elements at the end and get the 10000 elements and check it. Fixes updateChild and the usage of updateChild Getting the maintainNode to be the leaf-most node, so that the updateSize would always be right and the rotate always working. ...
2 parents521904f +3d9d535 commitfed9e0e

File tree

2 files changed

+542
-0
lines changed

2 files changed

+542
-0
lines changed
Lines changed: 368 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,368 @@
1+
'use strict';
2+
3+
/**
4+
* Size balanced tree is a data structure which is
5+
* a type of self-balancing binary search tree that use
6+
* the tree size attribute for re-balancing the tree.
7+
*
8+
*@example
9+
*
10+
* var SBTree = require('../src/data-structures/size-balanced-tree').SBTree;
11+
* var sbTree = new SBTree();
12+
*
13+
* var treeNode = sbTree.push({
14+
* name: 'John',
15+
* surname: 'Smith'
16+
* });
17+
* sbTree.insert(0, {
18+
* name: 'Pavlo',
19+
* surname: 'Popov'
20+
* });
21+
* sbTree.insert(1, {
22+
* name: 'Garry',
23+
* surname: 'Fisher'
24+
* });
25+
* sbTree.insert(0, {
26+
* name: 'Derek',
27+
* surname: 'Anderson'
28+
* });
29+
*
30+
* console.log(sbTree.get(0)); // { name: 'Derek', surname: 'Anderson' }
31+
*
32+
*@module data-structures/size-balanced-tree
33+
*/
34+
35+
functionCreateSBTreeClass(Node,Nil,updateChild){
36+
functionLeftRotate(node,childNode){
37+
/*
38+
Before rotate:
39+
node
40+
/ \
41+
NL childNode
42+
/ \
43+
CL CR
44+
After rotate:
45+
46+
childNode
47+
/ \
48+
node CR
49+
/ \
50+
NL CL
51+
*/
52+
node.right=childNode.left;
53+
if(node.right!==Nil){
54+
node.right.parent=node;
55+
}
56+
childNode.left=node;
57+
// setting childNode's parent to node's parent
58+
updateChild(node,childNode);
59+
returnchildNode;
60+
}
61+
62+
functionRightRotate(node,childNode){
63+
/*
64+
Before rotate:
65+
node
66+
/ \
67+
childNode NR
68+
/ \
69+
CL CR
70+
After rotate:
71+
72+
childNode
73+
/ \
74+
CL node
75+
/ \
76+
CR NR
77+
*/
78+
node.left=childNode.right;
79+
if(node.left!==Nil){
80+
node.left.parent=node;
81+
}
82+
childNode.right=node;
83+
// setting childNode's parent to node's parent
84+
updateChild(node,childNode);
85+
returnchildNode;
86+
}
87+
88+
functionmaintain(node,leftChild){
89+
if(node===Nil){
90+
returnnode;
91+
}
92+
varsavedNode=node;
93+
if(leftChild){
94+
if(node.left.left.size>node.right.size){
95+
node=RightRotate(node,node.left);
96+
}elseif(node.left.right.size>node.right.size){
97+
LeftRotate(node.left,node.left.right);
98+
node=RightRotate(node,node.left);
99+
}
100+
}else{
101+
if(node.right.right.size>node.left.size){
102+
node=LeftRotate(node,node.right);
103+
}elseif(node.right.left.size>node.left.size){
104+
RightRotate(node.right,node.right.left);
105+
node=LeftRotate(node,node.right);
106+
}
107+
}
108+
if(node===savedNode){
109+
returnnode;
110+
}
111+
maintain(node.left,false);
112+
maintain(node.right,true);
113+
node=maintain(node,true);
114+
node=maintain(node,false);
115+
returnnode;
116+
}
117+
118+
functionmaintainSizeBalancedTree(node){
119+
while(node.parent!==Nil){
120+
varchildNode=node;
121+
node=node.parent;
122+
if(node.left===childNode){
123+
node=maintain(node,true);
124+
}else{
125+
node=maintain(node,false);
126+
}
127+
}
128+
returnnode;
129+
}
130+
131+
functionfindNodeAtPos(node,pos){
132+
while(pos!==node.left.size){
133+
if(pos<node.left.size){
134+
node=node.left;
135+
}else{
136+
pos-=node.left.size;
137+
pos-=1;//The node element should be decrement by 1
138+
node=node.right;
139+
}
140+
}
141+
returnnode;
142+
}
143+
144+
/**
145+
* Size Balanced Tree.
146+
*
147+
*@public
148+
*@constructor
149+
*/
150+
varSBTree=function(){};
151+
152+
SBTree.prototype={
153+
_root:Nil,
154+
getsize(){
155+
returnthis._root.size;
156+
},
157+
158+
getroot(){
159+
returnthis._root;
160+
},
161+
162+
binarySearch:function(cmp,value){
163+
varleft=-1;
164+
varright=this.size;
165+
while(left+1<right){
166+
varmiddle=(left+right)>>1;// jshint ignore:line
167+
varresult=cmp(this.get(middle).value,value);
168+
if(result<=0){
169+
left=middle;
170+
}else{
171+
right=middle;
172+
}
173+
}
174+
returnleft+1;
175+
},
176+
};
177+
178+
SBTree.prototype.get=function(pos){
179+
if(pos>=this.size){
180+
returnNil;
181+
}
182+
returnfindNodeAtPos(this._root,pos);
183+
};
184+
185+
SBTree.prototype.getIndex=function(node){
186+
varindex=node.left.size;
187+
while(node!==this._root){
188+
varparent=node.parent;
189+
if(parent.right===node){
190+
index+=parent.left.size+1;
191+
}
192+
node=parent;
193+
}
194+
returnindex;
195+
};
196+
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+
}
217+
}
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+
}
244+
}else{
245+
node=findNodeAtPos(this._root,pos);
246+
if(node.left!==Nil){
247+
this.shiftDown(node);
248+
}
249+
node.left=newNode;
250+
}
251+
newNode.parent=node;
252+
this.insertLeafNode(newNode);
253+
this._root=maintainSizeBalancedTree(newNode);
254+
returnnewNode;
255+
};
256+
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+
282+
SBTree.prototype.remove=function(pos){
283+
if(pos>=this._root.size){
284+
returnNil;// There is no element to remove
285+
}
286+
varnode=findNodeAtPos(this._root,pos);
287+
returnthis.removeNode(node);
288+
};
289+
290+
returnSBTree;
291+
}
292+
293+
(function(exports){
294+
295+
/**
296+
* Node constructor of the Size-Balanced tree.
297+
*
298+
*@private
299+
*@constructor
300+
*@param {Object} value Value assigned to the node.
301+
*@param {Node} parent Parent node.
302+
*@param {Node} left Left node.
303+
*@param {Node} right Right node.
304+
*@param {Number} size Node's, means the Node count of this .
305+
*/
306+
varNodeConstructor=function(value,parent,left,right,size){
307+
this.value=value;
308+
this.parent=parent;
309+
this.left=left;
310+
this.right=right;
311+
this.size=size;
312+
};
313+
314+
varcreateNil=function(Node,value){
315+
varNil=newNode(value,null,null,null,0);
316+
Nil.parent=Nil;
317+
Nil.left=Nil;
318+
Nil.right=Nil;
319+
returnNil;
320+
};
321+
322+
/**
323+
* Update node's size.
324+
*
325+
*@private
326+
*@method
327+
*/
328+
varupdateSize=function(){
329+
this.size=this.left.size+this.right.size+1;
330+
};
331+
332+
// node, childNode must not be Nil,
333+
// if the childNode turn out to be the root, the parent should be Nil
334+
varupdateChild=function(node,childNode){
335+
varparent=node.parent;
336+
node.parent=childNode;
337+
childNode.parent=parent;
338+
339+
node.updateSize();
340+
childNode.updateSize();
341+
if(parent.right===node){
342+
parent.right=childNode;
343+
parent.updateSize();
344+
}elseif(parent.left===node){
345+
parent.left=childNode;
346+
parent.updateSize();
347+
}// otherwise parent is Nil
348+
};
349+
350+
varNode=function(){
351+
NodeConstructor.apply(this,arguments);
352+
};
353+
354+
Node.prototype.updateSize=updateSize;
355+
356+
varNil=createNil(Node,null);
357+
358+
exports.NodeConstructor=NodeConstructor;
359+
exports.createNil=createNil;
360+
exports.updateSize=updateSize;
361+
exports.updateChild=updateChild;
362+
exports.CreateSBTreeClass=CreateSBTreeClass;
363+
364+
exports.Node=Node;
365+
exports.Nil=Nil;
366+
exports.SBTree=CreateSBTreeClass(Node,Nil,updateChild);
367+
368+
})(typeofmodule==='undefined' ?window :module.exports);

0 commit comments

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