Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // AVLTree ///////////////////////////////////////////////////////////////////
- // This file is originally from the Concentré XML project (version 0.2.1)
- // Licensed under GPL and LGPL
- //
- // Modified by Jeremy Stephens.
- // Pass in the attribute you want to use for comparing
- function AVLTree(n, attr) {
- this.init(n, attr);
- }
- AVLTree.prototype.init = function(n, attr) {
- this.attr = attr;
- this.left = null;
- this.right = null;
- this.node = n;
- this.depth = 1;
- this.elements = [n];
- };
- AVLTree.prototype.balance = function() {
- var ldepth = this.left == null ? 0 : this.left.depth;
- var rdepth = this.right == null ? 0 : this.right.depth;
- if (ldepth > rdepth + 1) {
- // LR or LL rotation
- var lldepth = this.left.left == null ? 0 : this.left.left.depth;
- var lrdepth = this.left.right == null ? 0 : this.left.right.depth;
- if (lldepth < lrdepth) {
- // 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 rorarion
- var rrdepth = this.right.right == null ? 0 : this.right.right.depth;
- var rldepth = this.right.left == null ? 0 : this.right.left.depth;
- if (rldepth > rrdepth) {
- // 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();
- }
- };
- AVLTree.prototype.rotateLL = function() {
- // the left side is too long => rotate from the left (_not_ leftwards)
- var nodeBefore = this.node;
- var elementsBefore = this.elements;
- var rightBefore = this.right;
- this.node = this.left.node;
- this.elements = this.left.elements;
- this.right = this.left;
- this.left = this.left.left;
- this.right.left = this.right.right;
- this.right.right = rightBefore;
- this.right.node = nodeBefore;
- this.right.elements = elementsBefore;
- this.right.updateInNewLocation();
- this.updateInNewLocation();
- };
- AVLTree.prototype.rotateRR = function() {
- // the right side is too long => rotate from the right (_not_ rightwards)
- var nodeBefore = this.node;
- var elementsBefore = this.elements;
- var leftBefore = this.left;
- this.node = this.right.node;
- this.elements = this.right.elements;
- this.left = this.right;
- this.right = this.right.right;
- this.left.right = this.left.left;
- this.left.left = leftBefore;
- this.left.node = nodeBefore;
- this.left.elements = elementsBefore;
- this.left.updateInNewLocation();
- this.updateInNewLocation();
- };
- AVLTree.prototype.updateInNewLocation = function() {
- this.getDepthFromChildren();
- };
- AVLTree.prototype.getDepthFromChildren = function() {
- this.depth = this.node == null ? 0 : 1;
- if (this.left != null) {
- this.depth = this.left.depth + 1;
- }
- if (this.right != null && this.depth <= this.right.depth) {
- this.depth = this.right.depth + 1;
- }
- };
- AVLTree.prototype.compare = function(n1, n2) {
- v1 = n1[this.attr];
- v2 = n2[this.attr];
- if (v1 == v2) {
- return 0;
- }
- if (v1 < v2) {
- return -1;
- }
- return 1;
- };
- AVLTree.prototype.add = function(n) {
- var o = this.compare(n, this.node);
- if (o == 0) {
- this.elements.push(n);
- return false;
- }
- var ret = false;
- if (o == -1) {
- if (this.left == null) {
- this.left = new AVLTree(n, this.attr);
- ret = true;
- } else {
- ret = this.left.add(n);
- if (ret) {
- this.balance();
- }
- }
- } else if (o == 1) {
- if (this.right == null) {
- this.right = new AVLTree(n, this.attr);
- ret = true;
- } else {
- ret = this.right.add(n);
- if (ret) {
- this.balance();
- }
- }
- }
- if (ret) {
- this.getDepthFromChildren();
- }
- return ret;
- };
- // Given the beginning of a value, return the elements if there's a match
- AVLTree.prototype.findBest = function(value) {
- var substr = this.node[this.attr].substr(0, value.length).toLowerCase();
- var value = value.toLowerCase();
- if (value < substr) {
- if (this.left != null) {
- return this.left.findBest(value);
- }
- return [];
- }
- else if (value > substr) {
- if (this.right != null) {
- return this.right.findBest(value);
- }
- return [];
- }
- return this.elements;
- }
Add Comment
Please, Sign In to add comment