|
| 1 | +/** |
| 2 | + * Size balanced tree is a data structure which is |
| 3 | + * a type of self-balancing binary search tree that use |
| 4 | + * the tree size attribute for re-balancing the tree. |
| 5 | + * |
| 6 | + *@example |
| 7 | + * |
| 8 | + * var SBTree = require('../src/data-structures/size-balanced-tree').SBTree; |
| 9 | + * var sbTree = new SBTree(); |
| 10 | + * |
| 11 | + * var treeNode = sbTree.push({ |
| 12 | + * name: 'John', |
| 13 | + * surname: 'Smith' |
| 14 | + * }); |
| 15 | + * sbTree.insert(0, { |
| 16 | + * name: 'Pavlo', |
| 17 | + * surname: 'Popov' |
| 18 | + * }); |
| 19 | + * sbTree.insert(1, { |
| 20 | + * name: 'Garry', |
| 21 | + * surname: 'Fisher' |
| 22 | + * }); |
| 23 | + * sbTree.insert(0, { |
| 24 | + * name: 'Derek', |
| 25 | + * surname: 'Anderson' |
| 26 | + * }); |
| 27 | + * |
| 28 | + * console.log(sbTree.get(0)); // { name: 'Derek', surname: 'Anderson' } |
| 29 | + * |
| 30 | + *@module data-structures/size-balanced-tree |
| 31 | + */ |
| 32 | +(function(exports){ |
| 33 | + |
| 34 | +'use strict'; |
| 35 | + |
| 36 | +varNil={ |
| 37 | +parent:Nil, |
| 38 | +left:Nil, |
| 39 | +right:Nil, |
| 40 | +size:0, |
| 41 | +}; |
| 42 | + |
| 43 | +exports.Nil=Nil; |
| 44 | + |
| 45 | +/** |
| 46 | + * Node of the Size-Balanced tree. |
| 47 | + * |
| 48 | + *@private |
| 49 | + *@constructor |
| 50 | + *@param {Object} value Value assigned to the node. |
| 51 | + *@param {Node} parent Parent node. |
| 52 | + *@param {Node} left Left node. |
| 53 | + *@param {Node} right Right node. |
| 54 | + *@param {Number} size Node's, means the Node count of this subtree. |
| 55 | + */ |
| 56 | +functionNode(value,parent,left,right,size){ |
| 57 | +this.value=value; |
| 58 | +this.parent=parent; |
| 59 | +this.left=left; |
| 60 | +this.right=right; |
| 61 | +this.size=size; |
| 62 | +} |
| 63 | + |
| 64 | +/** |
| 65 | + * Update node's size. |
| 66 | + * |
| 67 | + *@private |
| 68 | + *@method |
| 69 | + */ |
| 70 | +Node.prototype.updateSize=function(){ |
| 71 | +this.size=this.left.size+this.right.size+1; |
| 72 | +}; |
| 73 | + |
| 74 | +exports.Node=Node; |
| 75 | + |
| 76 | +functionupdateChild(node,newChild){ |
| 77 | +letparent=node.parent; |
| 78 | +if(parent!==Nil){ |
| 79 | +if(parent.right===node){ |
| 80 | +parent.right=newChild; |
| 81 | +newChild.parent=parent; |
| 82 | +}else{ |
| 83 | +parent.left=newChild; |
| 84 | +newChild.parent=parent; |
| 85 | +} |
| 86 | +returnparent; |
| 87 | +} |
| 88 | +returnnewChild; |
| 89 | +} |
| 90 | + |
| 91 | +functionLeftRotate(node,childNode){ |
| 92 | +/* |
| 93 | + Before rotate: |
| 94 | + node |
| 95 | + / \ |
| 96 | + NL childNode |
| 97 | + / \ |
| 98 | + CL CR |
| 99 | + After rotate: |
| 100 | +
|
| 101 | + childNode |
| 102 | + / \ |
| 103 | + node CR |
| 104 | + / \ |
| 105 | + NL CL |
| 106 | + */ |
| 107 | +node.right=childNode.left; |
| 108 | +node.right.parent=node; |
| 109 | +childNode.left=node; |
| 110 | +childNode.left.parent=childNode; |
| 111 | +updateChild(node,childNode) |
| 112 | +node.updateSize(); |
| 113 | +returnchildNode; |
| 114 | +} |
| 115 | + |
| 116 | +functionRightRotate(node,childNode){ |
| 117 | +/* |
| 118 | + Before rotate: |
| 119 | + node |
| 120 | + / \ |
| 121 | + childNode NR |
| 122 | + / \ |
| 123 | + CL CR |
| 124 | + After rotate: |
| 125 | +
|
| 126 | + childNode |
| 127 | + / \ |
| 128 | + CL node |
| 129 | + / \ |
| 130 | + CR NR |
| 131 | + */ |
| 132 | +node.left=childNode.right; |
| 133 | +node.left.parent=node; |
| 134 | +childNode.right=node; |
| 135 | +childNode.right.parent=childNode; |
| 136 | +updateChild(node,childNode) |
| 137 | +node.updateSize(); |
| 138 | +returnchildNode; |
| 139 | +} |
| 140 | + |
| 141 | +functionmaintainSizeBalancedTree(node){ |
| 142 | +while(node.parent!==Nil){ |
| 143 | +letchildNode=node; |
| 144 | +node=node.parent; |
| 145 | +if(node.right===childNode){ |
| 146 | +if(childNode.right.size>node.left.size){ |
| 147 | +node=LeftRotate(node,childNode); |
| 148 | +} |
| 149 | +}else{ |
| 150 | +if(childNode.left.size>node.right.size){ |
| 151 | +node=RightRotate(node,childNode); |
| 152 | +} |
| 153 | +} |
| 154 | +node.updateSize(); |
| 155 | +} |
| 156 | +returnnode; |
| 157 | +} |
| 158 | + |
| 159 | +functionfindRightMost=function(node){ |
| 160 | +while(node.right!==Nil){ |
| 161 | +node=node.right; |
| 162 | +} |
| 163 | +returnnode; |
| 164 | +} |
| 165 | + |
| 166 | +functionfindNodeAtPos=function(node,pos){ |
| 167 | +while(pos!=node.left.size){ |
| 168 | +if(pos<node.left.size){ |
| 169 | +node=node.left; |
| 170 | +}else{ |
| 171 | +pos-=node.left.size; |
| 172 | +node=node.right; |
| 173 | +} |
| 174 | +} |
| 175 | +returnnode; |
| 176 | +} |
| 177 | + |
| 178 | +/** |
| 179 | + * Red-Black Tree. |
| 180 | + * |
| 181 | + *@public |
| 182 | + *@constructor |
| 183 | + */ |
| 184 | +exports.SBTree=function(){ |
| 185 | +this._root=Nil; |
| 186 | +}; |
| 187 | + |
| 188 | +/** |
| 189 | + * Push a value to the end of tree.<br><br> |
| 190 | + * Complexity: O(log N). |
| 191 | + * |
| 192 | + *@public |
| 193 | + *@method |
| 194 | + *@param {Object} value Value. |
| 195 | + */ |
| 196 | +exports.SBTree.prototype.push=function(value){ |
| 197 | +letnode=findRightMost(this._root); |
| 198 | +letnewNode=newNode(value,node,Nil,Nil,1); |
| 199 | +if(node!==Nil)node.right=newNode; |
| 200 | +this._root=maintainSizeBalancedTree(newNode); |
| 201 | +returnnewNode; |
| 202 | +}; |
| 203 | + |
| 204 | +exports.SBTree.prototype.get=function(pos){ |
| 205 | +if(pos>=this._root.size){ |
| 206 | +returnNil; |
| 207 | +} |
| 208 | +returnfindNodeAtPos(this._root,pos); |
| 209 | +}, |
| 210 | + |
| 211 | +exports.SBTree.prototype.insert=function(pos,value){ |
| 212 | +if(pos>=this._root.size){ |
| 213 | +returnthis.push(value) |
| 214 | +} |
| 215 | +letnode=findNodeAtPos(this._root,pos); |
| 216 | +letnewNode |
| 217 | +if(node.left===Nil){ |
| 218 | +newNode=newNode(value,node,Nil,Nil,1); |
| 219 | +node.left=newNode; |
| 220 | +}else{ |
| 221 | +node=findRightMost(node); |
| 222 | +newNode=newNode(value,node,Nil,Nil,1); |
| 223 | +node.right=newNode; |
| 224 | +} |
| 225 | +this._root=maintainSizeBalancedTree(newNode); |
| 226 | +returnnewNode; |
| 227 | +}; |
| 228 | + |
| 229 | +exports.SBTree.prototype.remove=function(pos){ |
| 230 | +if(pos>=this._root.size){ |
| 231 | +returnNil;// There is no element to remove |
| 232 | +} |
| 233 | +letnode=findNodeAtPos(this._root,pos); |
| 234 | +letremovedNode=node; |
| 235 | +letmaintainNode; |
| 236 | +if(node.right===Nil){ |
| 237 | +maintainNode=updateChild(node,node.left) |
| 238 | +}elseif(node.left===Nil){ |
| 239 | +maintainNode=updateChild(node,node.right) |
| 240 | +}else{ |
| 241 | +/* |
| 242 | + Before remove: |
| 243 | + P(node's parent, be notices, N either be left child or right child of P) |
| 244 | + | |
| 245 | + N(node) |
| 246 | + / \ |
| 247 | + L R |
| 248 | + \ |
| 249 | + \ |
| 250 | + LRM(Left-Rightmost) |
| 251 | + \ |
| 252 | + Nil |
| 253 | + After remove node N: |
| 254 | + P(node's parent) |
| 255 | + / |
| 256 | + L |
| 257 | + \ |
| 258 | + \ |
| 259 | + LRM(Left-Rightmost) |
| 260 | + \ |
| 261 | + R |
| 262 | +
|
| 263 | + N(node) is wild node that was removed |
| 264 | +
|
| 265 | + */ |
| 266 | +letLRM=findRightMost(node.left); |
| 267 | +updateChild(node,node.left) |
| 268 | +LRM.right=node.right |
| 269 | +LRM.right.parent=LRM; |
| 270 | +maintainNode=LRM; |
| 271 | +} |
| 272 | +if(maintainNode!==Nil){ |
| 273 | +maintainNode.updateSize(); |
| 274 | +} |
| 275 | + |
| 276 | +this._root=maintainSizeBalancedTree(maintainNode); |
| 277 | +returnremovedNode; |
| 278 | +}; |
| 279 | + |
| 280 | +exports.SBTree.prototype.size=function(){ |
| 281 | +returnthis._root.size; |
| 282 | +} |
| 283 | + |
| 284 | +})(typeofwindow==='undefined' ?module.exports :window); |