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

Commit46f29d4

Browse files
committed
Fixes updateChild and the usage of updateChild
1 parentfe9fd72 commit46f29d4

File tree

2 files changed

+113
-22
lines changed

2 files changed

+113
-22
lines changed

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

Lines changed: 28 additions & 22 deletions
Original file line numberDiff line numberDiff line change
@@ -33,14 +33,7 @@
3333

3434
'use strict';
3535

36-
varNil={
37-
parent:Nil,
38-
left:Nil,
39-
right:Nil,
40-
size:0,
41-
};
4236

43-
exports.Nil=Nil;
4437

4538
/**
4639
* Node of the Size-Balanced tree.
@@ -72,21 +65,30 @@
7265
};
7366

7467
exports.Node=Node;
68+
varNil=newNode(null,null,null,null,0);
69+
Nil.parent=Nil;
70+
Nil.left=Nil;
71+
Nil.right=Nil;
72+
exports.Nil=Nil;
7573

7674
functionupdateChild(node,newChild){
7775
letparent=node.parent;
76+
if(parent===Nil){
77+
newChild.parent=parent;
78+
returnnewChild;
79+
}
7880
if(parent.right===node){
7981
parent.right=newChild;
80-
newChild.parent=parent;
81-
}elseif(parent.left===node){
82+
}else{
8283
parent.left=newChild;
83-
newChild.parent=parent;
8484
}
85-
if(newChild!==Nil){
86-
returnnewChild;
85+
if(newChild===Nil){
86+
returnparent;
8787
}
88-
returnparent;
88+
newChild.parent=parent;
89+
returnnewChild;
8990
}
91+
exports.updateChild=updateChild;
9092

9193
functionLeftRotate(node,childNode){
9294
/*
@@ -107,8 +109,8 @@
107109
node.right=childNode.left;
108110
node.right.parent=node;
109111
childNode.left=node;
110-
childNode.left.parent=childNode;
111-
updateChild(node,childNode)
112+
updateChild(node,childNode)//Access node.parent
113+
node.parent=childNode;
112114
node.updateSize();
113115
returnchildNode;
114116
}
@@ -132,8 +134,8 @@
132134
node.left=childNode.right;
133135
node.left.parent=node;
134136
childNode.right=node;
135-
childNode.right.parent=childNode;
136-
updateChild(node,childNode)
137+
updateChild(node,childNode)//Access node.parent
138+
node.parent=childNode;
137139
node.updateSize();
138140
returnchildNode;
139141
}
@@ -156,14 +158,14 @@
156158
returnnode;
157159
}
158160

159-
functionfindRightMost=function(node){
161+
functionfindRightMost(node){
160162
while(node.right!==Nil){
161163
node=node.right;
162164
}
163165
returnnode;
164166
}
165167

166-
functionfindNodeAtPos=function(node,pos){
168+
functionfindNodeAtPos(node,pos){
167169
while(pos!=node.left.size){
168170
if(pos<node.left.size){
169171
node=node.left;
@@ -185,6 +187,13 @@
185187
this._root=Nil;
186188
};
187189

190+
191+
exports.SBTree.prototype={
192+
getsize(){
193+
returnthis._root.size;
194+
},
195+
}
196+
188197
/**
189198
* Push a value to the end of tree.<br><br>
190199
* Complexity: O(log N).
@@ -273,8 +282,5 @@
273282
returnremovedNode;
274283
};
275284

276-
exports.SBTree.prototype.size=function(){
277-
returnthis._root.size;
278-
}
279285

280286
})(typeofwindow==='undefined' ?module.exports :window);
Lines changed: 85 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,85 @@
1+
'use strict';
2+
3+
varmod=require('../../src/data-structures/size-balanced-tree.js');
4+
varNode=mod.Node;
5+
varNil=mod.Nil;
6+
varSBTree=mod.SBTree;
7+
varupdateChild=mod.updateChild;
8+
9+
describe('Node',function(){
10+
it('should be a constructor function',function(){
11+
expect(typeofNode).toBe('function');
12+
});
13+
it('should be a construct properly',function(){
14+
varnode=newNode(10,Nil,Nil,Nil,1);
15+
expect(node.value).toBe(10);
16+
expect(node.left).toBe(Nil);
17+
expect(node.right).toBe(Nil);
18+
expect(node.parent).toBe(Nil);
19+
expect(node.size).toBe(1);
20+
});
21+
it('should reference children/parent properly',function(){
22+
varroot=newNode(10,Nil,Nil,Nil,1);
23+
varleft=newNode(5,root,Nil,Nil,1);
24+
varright=newNode(15,root,Nil,Nil,1);
25+
root.left=left;
26+
root.right=right;
27+
expect(root.value).toBe(10);
28+
expect(root.left).toBe(left);
29+
expect(root.right).toBe(right);
30+
expect(root.parent).toBe(Nil);
31+
expect(right.parent).toBe(root);
32+
expect(left.parent).toBe(root);
33+
expect(right.size).toBe(1);
34+
expect(left.size).toBe(1);
35+
expect(root.size).toBe(1);
36+
root.updateSize();
37+
expect(root.size).toBe(3);
38+
});
39+
});
40+
41+
describe('SBTree',function(){
42+
it('should be a constructor function',function(){
43+
expect(typeofSBTree).toBe('function');
44+
});
45+
it('should start with null root',function(){
46+
expect(newSBTree()._root).toBe(Nil);
47+
});
48+
it('should insert and remove correctly',function(){
49+
varsTree=newSBTree();
50+
expect(sTree.size).toBe(0);
51+
sTree.insert(0,10);
52+
expect(sTree.size).toBe(1);
53+
sTree.remove(0);
54+
expect(sTree.size).toBe(0);
55+
expect(sTree._root).toBe(Nil);
56+
});
57+
58+
functioncheckNil(){
59+
expect(Nil.size).toBe(0);
60+
expect(Nil.left).toBe(Nil);
61+
expect(Nil.right).toBe(Nil);
62+
expect(Nil.parent).toBe(Nil);
63+
expect(Nil.value).toBe(null);
64+
}
65+
it('test updateChild',function(){
66+
vare=updateChild(Nil,Nil);
67+
checkNil();
68+
expect(e).toBe(Nil);
69+
varroot=newNode(10,Nil,Nil,Nil,1);
70+
varleft=newNode(5,root,Nil,Nil,1);
71+
varright=newNode(15,root,Nil,Nil,1);
72+
varleftLeft=newNode(10,left,Nil,Nil,1);
73+
left.left=leftLeft;
74+
root.left=left;
75+
root.right=right;
76+
updateChild(left,leftLeft);
77+
expect(leftLeft.parent).toBe(root);
78+
expect(root.left).toBe(leftLeft);
79+
updateChild(leftLeft,Nil);
80+
checkNil();
81+
expect(root.left).toBe(Nil);
82+
updateChild(Nil,right);
83+
expect(right.parent).toBe(Nil);
84+
});
85+
});

0 commit comments

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