Skip to content

Commit fed9e0e

Browse files
mgechevmgechev
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 parents 521904f + 3d9d535 commit fed9e0e

File tree

2 files changed

+542
-0
lines changed

2 files changed

+542
-0
lines changed

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

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+
function CreateSBTreeClass (Node, Nil, updateChild) {
36+
function LeftRotate(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+
return childNode;
60+
}
61+
62+
function RightRotate(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+
return childNode;
86+
}
87+
88+
function maintain(node, leftChild) {
89+
if (node === Nil) {
90+
return node;
91+
}
92+
var savedNode = node;
93+
if (leftChild) {
94+
if (node.left.left.size > node.right.size) {
95+
node = RightRotate(node, node.left);
96+
} else if (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+
} else if (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+
return node;
110+
}
111+
maintain(node.left, false);
112+
maintain(node.right, true);
113+
node = maintain(node, true);
114+
node = maintain(node, false);
115+
return node;
116+
}
117+
118+
function maintainSizeBalancedTree(node) {
119+
while (node.parent !== Nil) {
120+
var childNode = 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+
return node;
129+
}
130+
131+
function findNodeAtPos(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+
return node;
142+
}
143+
144+
/**
145+
* Size Balanced Tree.
146+
*
147+
* @public
148+
* @constructor
149+
*/
150+
var SBTree = function () {};
151+
152+
SBTree.prototype = {
153+
_root: Nil,
154+
get size() {
155+
return this._root.size;
156+
},
157+
158+
get root() {
159+
return this._root;
160+
},
161+
162+
binarySearch: function (cmp, value) {
163+
var left = -1;
164+
var right = this.size;
165+
while (left + 1 < right) {
166+
var middle = (left + right) >> 1; // jshint ignore:line
167+
var result = cmp(this.get(middle).value, value);
168+
if (result <= 0) {
169+
left = middle;
170+
} else {
171+
right = middle;
172+
}
173+
}
174+
return left + 1;
175+
},
176+
};
177+
178+
SBTree.prototype.get = function (pos) {
179+
if (pos >= this.size) {
180+
return Nil;
181+
}
182+
return findNodeAtPos(this._root, pos);
183+
};
184+
185+
SBTree.prototype.getIndex = function (node) {
186+
var index = node.left.size;
187+
while (node !== this._root) {
188+
var parent = node.parent;
189+
if (parent.right === node) {
190+
index += parent.left.size + 1;
191+
}
192+
node = parent;
193+
}
194+
return index;
195+
};
196+
197+
SBTree.prototype.shiftDown = function (node) {
198+
var direction = 0;
199+
while (true) {
200+
if (node.left !== Nil && node.right !== Nil) {
201+
switch (direction) {
202+
case 0:
203+
RightRotate(node, node.left);
204+
break;
205+
case 1:
206+
LeftRotate(node, node.right);
207+
break;
208+
}
209+
direction = 1 - direction;
210+
} else if (node.left !== Nil) {
211+
RightRotate(node, node.left);
212+
} else if (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+
var parent = 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+
var parent = 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+
var node = Nil;
238+
var newNode = new Node(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+
return newNode;
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+
var maintainNode = node.parent;
272+
if (maintainNode.left === node) {
273+
maintainNode.left = Nil;
274+
} else if (maintainNode.right === node) {
275+
maintainNode.right = Nil;
276+
}
277+
this.removeLeafNode(node);
278+
this._root = maintainSizeBalancedTree(maintainNode);
279+
return node;
280+
};
281+
282+
SBTree.prototype.remove = function (pos) {
283+
if (pos >= this._root.size) {
284+
return Nil; // There is no element to remove
285+
}
286+
var node = findNodeAtPos(this._root, pos);
287+
return this.removeNode(node);
288+
};
289+
290+
return SBTree;
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+
var NodeConstructor = 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+
var createNil = function (Node, value) {
315+
var Nil = new Node(value, null, null, null, 0);
316+
Nil.parent = Nil;
317+
Nil.left = Nil;
318+
Nil.right = Nil;
319+
return Nil;
320+
};
321+
322+
/**
323+
* Update node's size.
324+
*
325+
* @private
326+
* @method
327+
*/
328+
var updateSize = 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+
var updateChild = function (node, childNode) {
335+
var parent = 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+
} else if (parent.left === node) {
345+
parent.left = childNode;
346+
parent.updateSize();
347+
} // otherwise parent is Nil
348+
};
349+
350+
var Node = function () {
351+
NodeConstructor.apply(this, arguments);
352+
};
353+
354+
Node.prototype.updateSize = updateSize;
355+
356+
var Nil = 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+
})(typeof module === 'undefined' ? window : module.exports);

0 commit comments

Comments
 (0)