Last active
August 29, 2015 13:57
-
-
Save Eh2406/9893763 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// AVLTree /////////////////////////////////////////////////////////////////// | |
// This file is originally from the Concentré XML project (version 0.2.1) | |
// Licensed under GPL and LGPL | |
// | |
// Modified by Jeremy Stephens. | |
// and by Jacob Finkelman. | |
// Pass in the attribute you want to use for comparing | |
function AVLTree(n, attr) { | |
return new AVLTree.prototype.init(n, attr); | |
} | |
AVLTree.prototype.init = function(n, attr) { | |
this.attr = attr; | |
this.left = null; | |
this.right = null; | |
this.parent = null; | |
this.node = n; | |
this.depth = 0; | |
//chain object | |
return this; | |
}; | |
AVLTree.prototype.init.prototype = AVLTree.prototype; | |
AVLTree.prototype.balance = function() { | |
var ldepth = this.left ? this.left.depth : -1, | |
rdepth = this.right ? this.right.depth : -1, | |
depthBefore = this.depth; | |
if (ldepth > rdepth + 1) { | |
// LR or LL rotation | |
if ((this.left.left ? this.left.left.depth : -1) < (this.left.right ? this.left.right.depth : -1)) { | |
// LR rotation consists of a RR rotation of the left child | |
this.left.rotateRR(); | |
// plus a LL rotation of this node, which happens anyway | |
} | |
this.rotateLL(); | |
} else if (ldepth + 1 < rdepth) { | |
// RR or RL rotation | |
if ((this.right.left ? this.right.left.depth : -1) > (this.right.right ? this.right.right.depth : -1)) { | |
// RR rotation consists of a LL rotation of the right child | |
this.right.rotateLL(); | |
// plus a RR rotation of this node, which happens anyway | |
} | |
this.rotateRR(); | |
} | |
this.updateDepth(); | |
if (this.depth !== depthBefore && this.parent) { | |
this.parent.balance(); | |
} | |
}; | |
AVLTree.prototype.rotateLL = function() { | |
// the left side is too long => rotate from the left (_not_ leftwards) | |
// y x | |
// / \ / \ | |
// x C ==> A y | |
// / \ / \ | |
// A B B C | |
var nodeBefore = this.node, | |
rightBefore = this.right; | |
this.node = this.left.node; | |
this.right = this.left; | |
this.left = this.left.left; | |
if (this.left) {this.left.parent = this} | |
this.right.left = this.right.right; | |
this.right.right = rightBefore; | |
if (this.right.right) {this.right.right.parent = this.right} | |
this.right.node = nodeBefore; | |
this.right.updateDepth(); | |
this.updateDepth(); | |
}; | |
AVLTree.prototype.rotateRR = function() { | |
// the right side is too long => rotate from the right (_not_ rightwards) | |
// x y | |
// / \ / \ | |
// A y ==> x C | |
// / \ / \ | |
// B C A B | |
var nodeBefore = this.node, | |
leftBefore = this.left; | |
this.node = this.right.node; | |
this.left = this.right; | |
this.right = this.right.right; | |
if (this.right) {this.right.parent = this} | |
this.left.right = this.left.left; | |
this.left.left = leftBefore; | |
if (this.left.left) {this.left.left.parent = this.left} | |
this.left.node = nodeBefore; | |
this.left.updateDepth(); | |
this.updateDepth(); | |
}; | |
AVLTree.prototype.updateDepth = function() { | |
this.depth = 1 + Math.max( | |
this.left ? this.left.depth : -1, | |
this.right ? this.right.depth : -1 | |
); | |
}; | |
AVLTree.prototype.find = function(n) { | |
var o = this.attr(n, this.node); | |
if (o == 0) { | |
return this; | |
} else if (o < 0) { | |
return this.left ? this.left.find(n) : this.predecessor(); | |
} else { // o > 0 | |
return this.right ? this.right.find(n) : this; | |
} | |
}; | |
AVLTree.prototype.add = function(n) { | |
var o = this.attr(n, this.node); | |
if (o == 0) { | |
this.node = n; | |
return this; | |
} else if (o < 0) { | |
if (this.left) { | |
return this.left.add(n); | |
} else { | |
this.left = AVLTree(n, this.attr); | |
this.left.parent = this; | |
this.balance(); | |
return this.left; | |
} | |
} else { // o > 0 | |
if (this.right) { | |
return this.right.add(n); | |
} else { | |
this.right = AVLTree(n, this.attr); | |
this.right.parent = this; | |
this.balance(); | |
return this.right; | |
} | |
} | |
}; | |
AVLTree.prototype.del = function() { | |
var child; | |
if (!(this.left && this.right)) { | |
child = this.left || this.right; | |
if (this.parent.left === this) { | |
this.parent.left = child; | |
if (child) { | |
child.parent = this.parent; | |
} | |
this.parent.balance(); | |
} else { //this.parent.right === this | |
this.parent.right = child; | |
if (child) { | |
child.parent = this.parent; | |
} | |
this.parent.balance(); | |
} | |
} else { | |
child = this.left.depth > this.right.depth ? this.predecessor() : this.successor(); | |
this.node = child.node; | |
child.del(); | |
} | |
} | |
// get the left most sub-node | |
AVLTree.prototype.first = function() { | |
var next = this; | |
while (next.left) { | |
next = next.left; | |
} | |
return next; | |
} | |
// get the right most sub-node | |
AVLTree.prototype.last = function() { | |
var next = this; | |
while (next.right) { | |
next = next.right; | |
} | |
return next; | |
} | |
// get the next node after x in sorted order | |
AVLTree.prototype.successor = function() { | |
var next = this; | |
if (this.right) { | |
return this.right.first(); | |
} | |
while (next.parent && next.parent.right === next) { | |
next = next.parent; | |
} | |
return next.parent; | |
}; | |
// get the previous node before x in sorted order | |
AVLTree.prototype.predecessor = function() { | |
var next = this; | |
if (this.left) { | |
return this.left.last(); | |
} | |
while (next.parent && next.parent.left === next) { | |
next = next.parent; | |
} | |
return next.parent; | |
}; | |
// Convert tree to an array in sorted order | |
AVLTree.prototype.toArray = function(arr) { | |
if (this.left) { | |
arr = this.left.toArray(arr); | |
} else { | |
arr = arr || []; | |
} | |
arr.push(this.node); | |
if (this.right) { | |
arr = this.right.toArray(arr); | |
} | |
return arr; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
do u have an example of this implementation? i don't know how add a new node :(