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

Commit099d4ba

Browse files
committed
* 'master' ofhttps://github.com/mgechev/javascript-algorithms: Level Order Traversal for red black tree using queue. feat(DataStructures): add segment tree
2 parents26c4f33 +dd8258a commit099d4ba

File tree

4 files changed

+240
-0
lines changed

4 files changed

+240
-0
lines changed

‎src/data-structures/red-black-tree.js

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -266,4 +266,34 @@
266266
}
267267
};
268268

269+
/**
270+
* Get Level Order Traversal for the given Red Black Tree,
271+
* returns 'Tree is empty' string when tree has no Nodes.
272+
* Complexity: O(N).
273+
*
274+
*@public
275+
*@return {String} The keys of the tree in level order traversal.
276+
*
277+
*/
278+
exports.RBTree.prototype.levelOrderTraversal=function(){
279+
varqueue=[];
280+
varlevelOrderString='';
281+
if(this._root){
282+
queue.push(this._root);
283+
}else{
284+
levelOrderString=' Tree is empty';
285+
}
286+
while(queue.length!==0){
287+
vartempNode=queue.shift();
288+
levelOrderString+=' '+tempNode.getKey();
289+
if(tempNode.getLeft()!==null){
290+
queue.push(tempNode.getLeft());
291+
}
292+
if(tempNode.getRight()!==null){
293+
queue.push(tempNode.getRight());
294+
}
295+
}
296+
return'Level Order Traversal -:'+levelOrderString;
297+
};
298+
269299
})(typeofwindow==='undefined' ?module.exports :window);

‎src/data-structures/segment-tree.js

Lines changed: 105 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,105 @@
1+
/**
2+
* Implementation of a segment tree.
3+
*
4+
*@example
5+
* var SegmentTree = require('path-to-algorithms/src/data-structures'+
6+
* '/segment-tree').SegmentTree;
7+
*
8+
* var tree = SegmentTree.indexArray([-1, 2, 4, 0], Infinity, function (a, b) {
9+
* return Math.min(a, b);
10+
* });
11+
*
12+
*@public
13+
*@constructor
14+
*@param {any} placeholder A placeholder value dpendent on the aggregate.
15+
*@param {Function} aggregate Generates the values for the intermediate nodes.
16+
*@module data-structures/segment-tree
17+
*/
18+
(function(exports){
19+
20+
'use strict';
21+
22+
/**
23+
* SegmentTree constructor.
24+
*
25+
*@public
26+
*@constructor
27+
*@param {any} invalidValue Invalid value to be returned depending
28+
* on the aggregate.
29+
*@param {Function} aggregate Function to generate the intermediate
30+
* values in the tree.
31+
*/
32+
functionSegmentTree(invalidValue,aggregate){
33+
this._data=[];
34+
this._original=null;
35+
this._invalidValue=invalidValue;
36+
this._aggregate=aggregate;
37+
}
38+
39+
/**
40+
* Creates a segment tree using an array passed as element.
41+
*
42+
*@static
43+
*@public
44+
*@param {Array} array Array to be indexed.
45+
*@param {Function} aggregate Function used for generation of
46+
* intermediate nodes.
47+
*/
48+
SegmentTree.indexArray=function(array,placeholder,aggregate){
49+
varsegmentize=function(original,data,lo,hi,idx){
50+
if(lo===hi){
51+
data[idx]=original[lo];
52+
}else{
53+
varmid=Math.floor((lo+hi)/2);
54+
varleft=2*idx+1;
55+
varright=2*idx+2;
56+
segmentize(original,data,lo,mid,left);
57+
segmentize(original,data,mid+1,hi,right);
58+
data[idx]=aggregate(data[left],data[right]);
59+
}
60+
};
61+
varresult=[];
62+
if(array&&array.length){
63+
segmentize(array,result,0,array.length-1,0);
64+
}
65+
vartree=newSegmentTree(placeholder,aggregate);
66+
tree._data=result;
67+
tree._original=array;
68+
returntree;
69+
};
70+
71+
/**
72+
* Queries the SegmentTree in given range based on the set aggregate.
73+
*
74+
*@param {Number} start The start index of the interval.
75+
*@param {Number} end The end index of the interval.
76+
*/
77+
SegmentTree.prototype.query=function(start,end){
78+
if(start>end){
79+
thrownewError('The start index should be smaller by the end index');
80+
}
81+
varfindEl=function(originalArrayStart,originalArrayEnd,current){
82+
if(start>originalArrayEnd){
83+
returnthis._invalidValue;
84+
}
85+
if(end<originalArrayStart){
86+
returnthis._invalidValue;
87+
}
88+
if(start===originalArrayStart&&end===originalArrayEnd||
89+
originalArrayStart===originalArrayEnd){
90+
returnthis._data[current];
91+
}
92+
varoriginalArrayMid=
93+
Math.floor((originalArrayStart+originalArrayEnd)/2);
94+
returnthis._aggregate(
95+
findEl(originalArrayStart,originalArrayMid,2*current+1),
96+
findEl(originalArrayMid+1,originalArrayEnd,2*current+2)
97+
);
98+
}.bind(this);
99+
returnfindEl(0,this._original.length-1,0,this._aggregate);
100+
};
101+
102+
exports.SegmentTree=SegmentTree;
103+
104+
}(typeofwindow==='undefined' ?module.exports :window));
105+

‎test/data-structures/red-black-tree.spec.js

Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -97,4 +97,20 @@ describe('RBTree', function () {
9797
});
9898
});
9999

100+
describe('levelOrderTraversal method',function(){
101+
it('should be able to traverse tree in level order',function(){
102+
vartree=newRBTree();
103+
expect(tree.levelOrderTraversal()).toBe('Level Order Traversal -: Tree is empty');
104+
tree.put(10);
105+
tree.put(20);
106+
expect(tree.levelOrderTraversal()).toBe('Level Order Traversal -: 20 10');
107+
tree.put(30);
108+
expect(tree.levelOrderTraversal()).toBe('Level Order Traversal -: 20 10 30');
109+
tree.put(45);
110+
expect(tree.levelOrderTraversal()).toBe('Level Order Traversal -: 20 10 45 30');
111+
tree.put(5);
112+
expect(tree.levelOrderTraversal()).toBe('Level Order Traversal -: 20 10 45 5 30');
113+
});
114+
});
115+
100116
});
Lines changed: 89 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,89 @@
1+
'use strict';
2+
3+
varSegmentTree=require('../../src/data-structures/segment-tree.js')
4+
.SegmentTree;
5+
6+
vardefaultAggregate=function(a,b){
7+
returnMath.min(a,b);
8+
};
9+
10+
describe('Segment Tree',function(){
11+
12+
describe('indexing',function(){
13+
14+
it('should be a constructor function',function(){
15+
expect(typeofSegmentTree).toBe('function');
16+
});
17+
18+
it('should start with null original array',function(){
19+
expect(newSegmentTree()._original).toBe(null);
20+
});
21+
22+
it('should start with empty array as data',function(){
23+
expect(newSegmentTree()._data).not.toBe(null);
24+
expect(newSegmentTree()._data.length).toBe(0);
25+
});
26+
27+
it('should work with empty arrays',function(){
28+
vartree=SegmentTree.indexArray([],Infinity,defaultAggregate);
29+
expect(tree._data).toBeTruthy();
30+
expect(tree._data.length).toBe(0);
31+
});
32+
33+
it('should index arrays with one element',function(){
34+
vartree=SegmentTree.indexArray([1],Infinity,defaultAggregate);
35+
expect(tree._data).toBeTruthy();
36+
expect(tree._data.length).toBe(1);
37+
});
38+
39+
it('should index any array',function(){
40+
vartree=SegmentTree.indexArray([1,2,3],Infinity,defaultAggregate);
41+
expect(tree._data).toEqual([1,1,3,1,2]);
42+
43+
tree=SegmentTree.indexArray([1,2,3,6],Infinity,defaultAggregate);
44+
expect(tree._data).toEqual([1,1,3,1,2,3,6]);
45+
});
46+
47+
});
48+
49+
describe('should find the proper value at given interval',function(){
50+
51+
it('should properly find the minimum when in range',function(){
52+
vartree=SegmentTree.indexArray([1],Infinity,defaultAggregate);
53+
expect(tree.query(0,0)).toBe(1);
54+
55+
tree=SegmentTree.indexArray([1,2],Infinity,defaultAggregate);
56+
expect(tree.query(0,0)).toBe(1);
57+
expect(tree.query(0,1)).toBe(1);
58+
expect(tree.query(1,1)).toBe(2);
59+
60+
tree=SegmentTree.indexArray([1,-1,2],Infinity,defaultAggregate);
61+
expect(tree.query(0,2)).toBe(-1);
62+
expect(tree.query(0,1)).toBe(-1);
63+
expect(tree.query(1,1)).toBe(-1);
64+
expect(tree.query(1,2)).toBe(-1);
65+
expect(tree.query(2,2)).toBe(2);
66+
});
67+
68+
it('should properly find the minimum when outside range',function(){
69+
vartree=SegmentTree.indexArray([1],Infinity,defaultAggregate);
70+
expect(tree.query(0,2)).toBe(1);
71+
72+
tree=SegmentTree.indexArray([1,2,3],Infinity,defaultAggregate);
73+
expect(tree.query(0,20)).toBe(1);
74+
expect(tree.query(2,20)).toBe(3);
75+
expect(Number.isFinite(tree.query(20,25))).toBe(false);
76+
});
77+
78+
it('should throw when the start index is bigger than end',function(){
79+
vartree=SegmentTree.indexArray([1],Infinity,defaultAggregate);
80+
expect(function(){
81+
tree.query(2,1);
82+
}).toThrow();
83+
expect(function(){
84+
tree.query(1,1);
85+
}).not.toThrow();
86+
});
87+
});
88+
});
89+

0 commit comments

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