Skip to content

Instantly share code, notes, and snippets.

@Eh2406

Eh2406/avltree.js

Last active August 29, 2015 13:57
Download ZIP

Revisions

  1. Eh2406 revised this gist Apr 7, 2014. 1 changed file with 52 additions and 31 deletions.
    83 changes: 52 additions & 31 deletions avltree.js
    View file
    Original file line number Diff line number Diff line change
    @@ -24,8 +24,9 @@ AVLTree.prototype.init = function(n, attr) {
    AVLTree.prototype.init.prototype = AVLTree.prototype;

    AVLTree.prototype.balance = function() {
    var ldepth = this.left ? this.left.depth : -1;
    var rdepth = this.right ? this.right.depth : -1;
    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
    @@ -44,6 +45,11 @@ AVLTree.prototype.balance = function() {
    }
    this.rotateRR();
    }
    this.updateDepth();
    if (this.depth !== depthBefore && this.parent) {
    this.parent.balance();
    }

    };

    AVLTree.prototype.rotateLL = function() {
    @@ -58,8 +64,10 @@ AVLTree.prototype.rotateLL = function() {
    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();
    @@ -77,8 +85,10 @@ AVLTree.prototype.rotateRR = function() {
    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();
    @@ -89,57 +99,68 @@ AVLTree.prototype.updateDepth = function() {
    this.left ? this.left.depth : -1,
    this.right ? this.right.depth : -1
    );
    if(this.left) {
    this.left.parent = this;
    }
    if(this.right) {
    this.right.parent = this;
    }
    };

    AVLTree.prototype.find = function(n) {
    var o = this.attr(n, this.node);
    if (o == 0) {
    return this;
    } else if (o < 0) {
    if (this.left) {
    return this.left.find(n);
    } else {
    return this.predecessor();
    }
    return this.left ? this.left.find(n) : this.predecessor();
    } else { // o > 0
    if (this.right) {
    return this.right.find(n);
    } else {
    return this;
    }
    return this.right ? this.right.find(n) : this;
    }
    };

    AVLTree.prototype.add = function(n) {
    var o = this.attr(n, this.node), ret = false;
    var o = this.attr(n, this.node);
    if (o == 0) {
    return false;
    this.node = n;
    return this;
    } else if (o < 0) {
    if (this.left) {
    ret = this.left.add(n);
    return this.left.add(n);
    } else {
    ret = this.left = AVLTree(n, this.attr);
    this.left = AVLTree(n, this.attr);
    this.left.parent = this;
    this.balance();
    return this.left;
    }
    } else { // o > 0
    if (this.right) {
    ret = this.right.add(n);
    return this.right.add(n);
    } else {
    ret = this.right = AVLTree(n, this.attr);
    this.right = AVLTree(n, this.attr);
    this.right.parent = this;
    this.balance();
    return this.right;
    }
    }
    };

    if (ret) {
    this.balance();
    this.updateDepth();
    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();
    }
    return ret;
    };
    }

    // get the left most sub-node
    AVLTree.prototype.first = function() {
    @@ -185,13 +206,13 @@ AVLTree.prototype.predecessor = function() {

    // Convert tree to an array in sorted order
    AVLTree.prototype.toArray = function(arr) {
    if (this.left != null) {
    if (this.left) {
    arr = this.left.toArray(arr);
    } else {
    arr = arr || [];
    }
    arr.push(this.node);
    if (this.right != null) {
    if (this.right) {
    arr = this.right.toArray(arr);
    }
    return arr;
  2. Eh2406 revised this gist Apr 3, 2014. 1 changed file with 38 additions and 19 deletions.
    57 changes: 38 additions & 19 deletions avltree.js
    View file
    Original file line number Diff line number Diff line change
    @@ -3,13 +3,13 @@
    // Licensed under GPL and LGPL
    //
    // Modified by Jeremy Stephens.
    // and by Jacob Finkelman
    // 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;
    @@ -20,13 +20,13 @@ AVLTree.prototype.init = function(n, attr) {
    //chain object
    return this;
    };

    AVLTree.prototype.init.prototype = AVLTree.prototype;

    AVLTree.prototype.balance = function() {
    var ldepth = this.left ? this.left.depth : -1;
    var rdepth = this.right ? this.right.depth : -1;

    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)) {
    @@ -45,7 +45,7 @@ AVLTree.prototype.balance = function() {
    this.rotateRR();
    }
    };

    AVLTree.prototype.rotateLL = function() {
    // the left side is too long => rotate from the left (_not_ leftwards)
    // y x
    @@ -64,14 +64,14 @@ AVLTree.prototype.rotateLL = function() {
    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
    // B C A B
    var nodeBefore = this.node,
    leftBefore = this.left;
    this.node = this.right.node;
    @@ -83,21 +83,40 @@ AVLTree.prototype.rotateRR = function() {
    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
    );
    );
    if(this.left) {
    this.left.parent = this;
    }
    if(this.right) {
    this.right.parent = this;
    }
    };

    AVLTree.prototype.add = function(n) {

    AVLTree.prototype.find = function(n) {
    var o = this.attr(n, this.node);
    if (o == 0) {
    return this;
    } else if (o < 0) {
    if (this.left) {
    return this.left.find(n);
    } else {
    return this.predecessor();
    }
    } else { // o > 0
    if (this.right) {
    return this.right.find(n);
    } else {
    return this;
    }
    }
    };

    AVLTree.prototype.add = function(n) {
    var o = this.attr(n, this.node), ret = false;
    if (o == 0) {
    return false;
    @@ -123,7 +142,7 @@ AVLTree.prototype.add = function(n) {
    };

    // get the left most sub-node
    AVLTree.prototype.first = function() {
    AVLTree.prototype.first = function() {
    var next = this;
    while (next.left) {
    next = next.left;
    @@ -132,16 +151,16 @@ AVLTree.prototype.first = function() {
    }

    // get the right most sub-node
    AVLTree.prototype.last = function() {
    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() {
    AVLTree.prototype.successor = function() {
    var next = this;
    if (this.right) {
    return this.right.first();
    @@ -153,7 +172,7 @@ AVLTree.prototype.successor = function() {
    };

    // get the previous node before x in sorted order
    AVLTree.prototype.predecessor = function() {
    AVLTree.prototype.predecessor = function() {
    var next = this;
    if (this.left) {
    return this.left.last();
    @@ -165,7 +184,7 @@ AVLTree.prototype.predecessor = function() {
    };

    // Convert tree to an array in sorted order
    AVLTree.prototype.toArray = function(arr) {
    AVLTree.prototype.toArray = function(arr) {
    if (this.left != null) {
    arr = this.left.toArray(arr);
    } else {
  3. Eh2406 revised this gist Apr 3, 2014. 1 changed file with 10 additions and 10 deletions.
    20 changes: 10 additions & 10 deletions avltree.js
    View file
    Original file line number Diff line number Diff line change
    @@ -48,11 +48,11 @@ AVLTree.prototype.balance = function() {

    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
    // y x
    // / \ / \
    // x C ==> A y
    // / \ / \
    // A B B C
    var nodeBefore = this.node,
    rightBefore = this.right;
    this.node = this.left.node;
    @@ -67,11 +67,11 @@ AVLTree.prototype.rotateLL = function() {

    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
    // x y
    // / \ / \
    // A y ==> x C
    // / \ / \
    // B C A B
    var nodeBefore = this.node,
    leftBefore = this.left;
    this.node = this.right.node;
  4. Eh2406 revised this gist Apr 3, 2014. 1 changed file with 32 additions and 23 deletions.
    55 changes: 32 additions & 23 deletions avltree.js
    View file
    Original file line number Diff line number Diff line change
    @@ -122,37 +122,46 @@ AVLTree.prototype.add = function(n) {
    return ret;
    };

    // get the next node affter x in sorted order
    AVLTree.prototype.successor = function(x) {
    // 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) {
    next = this.right;
    while (next.left) {
    next = next.left;
    }
    return next;
    } else {
    while (next.parent && next.parent.right === next) {
    next = next.parent;
    }
    return next.parent;
    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(x) { var next = this;
    AVLTree.prototype.predecessor = function() {
    var next = this;
    if (this.left) {
    next = this.left;
    while (next.right) {
    next = next.right;
    }
    return next;
    } else {
    while (next.parent && next.parent.left === next) {
    next = next.parent;
    }
    return next.parent;
    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
  5. Eh2406 revised this gist Apr 3, 2014. 1 changed file with 35 additions and 2 deletions.
    37 changes: 35 additions & 2 deletions avltree.js
    View file
    Original file line number Diff line number Diff line change
    @@ -114,14 +114,47 @@ AVLTree.prototype.add = function(n) {
    ret = this.right = AVLTree(n, this.attr);
    }
    }

    if (ret) {
    this.balance();
    this.updateDepth();
    }
    return ret;
    };


    // get the next node affter x in sorted order
    AVLTree.prototype.successor = function(x) {
    var next = this;
    if (this.right) {
    next = this.right;
    while (next.left) {
    next = next.left;
    }
    return next;
    } else {
    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(x) { var next = this;
    if (this.left) {
    next = this.left;
    while (next.right) {
    next = next.right;
    }
    return next;
    } else {
    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 != null) {
  6. Eh2406 revised this gist Apr 2, 2014. 1 changed file with 25 additions and 25 deletions.
    50 changes: 25 additions & 25 deletions avltree.js
    View file
    Original file line number Diff line number Diff line change
    @@ -4,28 +4,29 @@
    //
    // 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;
    var rdepth = this.right ? this.right.depth : -1;

    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)) {
    @@ -44,7 +45,7 @@ AVLTree.prototype.balance = function() {
    this.rotateRR();
    }
    };

    AVLTree.prototype.rotateLL = function() {
    // the left side is too long => rotate from the left (_not_ leftwards)
    // y x
    @@ -63,7 +64,7 @@ AVLTree.prototype.rotateLL = function() {
    this.right.updateDepth();
    this.updateDepth();
    };

    AVLTree.prototype.rotateRR = function() {
    // the right side is too long => rotate from the right (_not_ rightwards)
    // x y
    @@ -82,46 +83,45 @@ AVLTree.prototype.rotateRR = function() {
    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
    );
    if(this.left) {
    this.left.parent = this;
    }
    if(this.right) {
    this.right.parent = this;
    }
    };

    AVLTree.prototype.add = function(n) {
    var o = this.attr(n, this.node), ret = false;
    if (o == 0) {
    return false;
    } else if (o < 0) {
    if (this.left == null) {
    this.left = AVLTree(n, this.attr);
    ret = true;
    } else {
    if (this.left) {
    ret = this.left.add(n);
    if (ret) {
    this.balance();
    }
    } else {
    ret = this.left = AVLTree(n, this.attr);
    }
    } else { // o > 0
    if (this.right == null) {
    this.right = AVLTree(n, this.attr);
    ret = true;
    } else {
    if (this.right) {
    ret = this.right.add(n);
    if (ret) {
    this.balance();
    }
    } else {
    ret = this.right = AVLTree(n, this.attr);
    }
    }

    if (ret) {
    this.balance();
    this.updateDepth();
    }
    return ret;
    };

    // Convert tree to an array in sorted order
    AVLTree.prototype.toArray = function(arr) {
    if (this.left != null) {
  7. Eh2406 revised this gist Apr 2, 2014. 1 changed file with 12 additions and 12 deletions.
    24 changes: 12 additions & 12 deletions avltree.js
    View file
    Original file line number Diff line number Diff line change
    @@ -28,15 +28,15 @@ AVLTree.prototype.balance = function() {

    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) {
    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) {
    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
    @@ -47,11 +47,11 @@ AVLTree.prototype.balance = function() {

    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
    // y x
    // / \ / \
    // x C ==> A y
    // / \ / \
    // A B B C
    var nodeBefore = this.node,
    rightBefore = this.right;
    this.node = this.left.node;
    @@ -66,11 +66,11 @@ AVLTree.prototype.rotateLL = function() {

    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
    // x y
    // / \ / \
    // A y ==> x C
    // / \ / \
    // B C A B
    var nodeBefore = this.node,
    leftBefore = this.left;
    this.node = this.right.node;
  8. Eh2406 revised this gist Apr 2, 2014. 1 changed file with 10 additions and 0 deletions.
    10 changes: 10 additions & 0 deletions avltree.js
    View file
    Original file line number Diff line number Diff line change
    @@ -47,6 +47,11 @@ AVLTree.prototype.balance = function() {

    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;
    @@ -61,6 +66,11 @@ AVLTree.prototype.rotateLL = function() {

    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;
  9. Eh2406 revised this gist Apr 2, 2014. 1 changed file with 4 additions and 10 deletions.
    14 changes: 4 additions & 10 deletions avltree.js
    View file
    Original file line number Diff line number Diff line change
    @@ -23,26 +23,20 @@ AVLTree.prototype.init = function(n, attr) {
    AVLTree.prototype.init.prototype = AVLTree.prototype;

    AVLTree.prototype.balance = function() {
    var ldepth = this.left == null ? -1 : this.left.depth;
    var rdepth = this.right == null ? -1 : this.right.depth;
    var ldepth = this.left ? this.left.depth : -1;
    var rdepth = this.right ? this.right.depth : -1;

    if (ldepth > rdepth + 1) {
    // LR or LL rotation
    var lldepth = this.left.left == null ? -1 : this.left.left.depth;
    var lrdepth = this.left.right == null ? -1 : this.left.right.depth;

    if (lldepth < lrdepth) {
    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
    var rrdepth = this.right.right == null ? -1 : this.right.right.depth;
    var rldepth = this.right.left == null ? -1 : this.right.left.depth;

    if (rldepth > rrdepth) {
    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
  10. Eh2406 revised this gist Apr 2, 2014. 1 changed file with 7 additions and 6 deletions.
    13 changes: 7 additions & 6 deletions avltree.js
    View file
    Original file line number Diff line number Diff line change
    @@ -3,6 +3,7 @@
    // 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) {
    @@ -22,13 +23,13 @@ AVLTree.prototype.init = function(n, attr) {
    AVLTree.prototype.init.prototype = AVLTree.prototype;

    AVLTree.prototype.balance = function() {
    var ldepth = this.left == null ? 0 : this.left.depth;
    var rdepth = this.right == null ? 0 : this.right.depth;
    var ldepth = this.left == null ? -1 : this.left.depth;
    var rdepth = this.right == null ? -1 : 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;
    var lldepth = this.left.left == null ? -1 : this.left.left.depth;
    var lrdepth = this.left.right == null ? -1 : this.left.right.depth;

    if (lldepth < lrdepth) {
    // LR rotation consists of a RR rotation of the left child
    @@ -38,8 +39,8 @@ AVLTree.prototype.balance = function() {
    this.rotateLL();
    } else if (ldepth + 1 < rdepth) {
    // RR or RL rotation
    var rrdepth = this.right.right == null ? 0 : this.right.right.depth;
    var rldepth = this.right.left == null ? 0 : this.right.left.depth;
    var rrdepth = this.right.right == null ? -1 : this.right.right.depth;
    var rldepth = this.right.left == null ? -1 : this.right.left.depth;

    if (rldepth > rrdepth) {
    // RR rotation consists of a LL rotation of the right child
  11. Eh2406 revised this gist Apr 2, 2014. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion avltree.js
    View file
    Original file line number Diff line number Diff line change
    @@ -14,7 +14,7 @@ AVLTree.prototype.init = function(n, attr) {
    this.left = null;
    this.right = null;
    this.node = n;
    this.depth = 1;
    this.depth = 0;
    //chain object
    return this;
    };
  12. Eh2406 revised this gist Apr 2, 2014. 1 changed file with 4 additions and 1 deletion.
    5 changes: 4 additions & 1 deletion avltree.js
    View file
    Original file line number Diff line number Diff line change
    @@ -79,7 +79,10 @@ AVLTree.prototype.rotateRR = function() {
    };

    AVLTree.prototype.updateDepth = function() {
    this.depth = 1 + Math.max(this.left && this.left.depth, this.right && this.right.depth);
    this.depth = 1 + Math.max(
    this.left ? this.left.depth : -1,
    this.right ? this.right.depth : -1
    );
    };

    AVLTree.prototype.add = function(n) {
  13. Eh2406 revised this gist Apr 2, 2014. 1 changed file with 7 additions and 13 deletions.
    20 changes: 7 additions & 13 deletions avltree.js
    View file
    Original file line number Diff line number Diff line change
    @@ -60,8 +60,8 @@ AVLTree.prototype.rotateLL = function() {
    this.right.left = this.right.right;
    this.right.right = rightBefore;
    this.right.node = nodeBefore;
    this.right.getDepthFromChildren();
    this.getDepthFromChildren();
    this.right.updateDepth();
    this.updateDepth();
    };

    AVLTree.prototype.rotateRR = function() {
    @@ -74,18 +74,12 @@ AVLTree.prototype.rotateRR = function() {
    this.left.right = this.left.left;
    this.left.left = leftBefore;
    this.left.node = nodeBefore;
    this.left.getDepthFromChildren();
    this.getDepthFromChildren();
    this.left.updateDepth();
    this.updateDepth();
    };

    AVLTree.prototype.getDepthFromChildren = function() {
    this.depth = 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.updateDepth = function() {
    this.depth = 1 + Math.max(this.left && this.left.depth, this.right && this.right.depth);
    };

    AVLTree.prototype.add = function(n) {
    @@ -115,7 +109,7 @@ AVLTree.prototype.add = function(n) {
    }

    if (ret) {
    this.getDepthFromChildren();
    this.updateDepth();
    }
    return ret;
    };
  14. Eh2406 revised this gist Apr 2, 2014. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion avltree.js
    View file
    Original file line number Diff line number Diff line change
    @@ -127,7 +127,7 @@ AVLTree.prototype.toArray = function(arr) {
    } else {
    arr = arr || [];
    }
    arr.push.apply(arr, this.node);
    arr.push(this.node);
    if (this.right != null) {
    arr = this.right.toArray(arr);
    }
  15. Eh2406 revised this gist Mar 31, 2014. 1 changed file with 5 additions and 5 deletions.
    10 changes: 5 additions & 5 deletions avltree.js
    View file
    Original file line number Diff line number Diff line change
    @@ -52,8 +52,8 @@ AVLTree.prototype.balance = function() {

    AVLTree.prototype.rotateLL = function() {
    // the left side is too long => rotate from the left (_not_ leftwards)
    var nodeBefore = this.node;
    var rightBefore = this.right;
    var nodeBefore = this.node,
    rightBefore = this.right;
    this.node = this.left.node;
    this.right = this.left;
    this.left = this.left.left;
    @@ -66,8 +66,8 @@ AVLTree.prototype.rotateLL = function() {

    AVLTree.prototype.rotateRR = function() {
    // the right side is too long => rotate from the right (_not_ rightwards)
    var nodeBefore = this.node;
    var leftBefore = this.left;
    var nodeBefore = this.node,
    leftBefore = this.left;
    this.node = this.right.node;
    this.left = this.right;
    this.right = this.right.right;
    @@ -79,7 +79,7 @@ AVLTree.prototype.rotateRR = function() {
    };

    AVLTree.prototype.getDepthFromChildren = function() {
    this.depth = this.node == null ? 0 : 1;
    this.depth = 1;
    if (this.left != null) {
    this.depth = this.left.depth + 1;
    }
  16. Eh2406 revised this gist Mar 31, 2014. 1 changed file with 3 additions and 7 deletions.
    10 changes: 3 additions & 7 deletions avltree.js
    View file
    Original file line number Diff line number Diff line change
    @@ -60,8 +60,8 @@ AVLTree.prototype.rotateLL = function() {
    this.right.left = this.right.right;
    this.right.right = rightBefore;
    this.right.node = nodeBefore;
    this.right.updateInNewLocation();
    this.updateInNewLocation();
    this.right.getDepthFromChildren();
    this.getDepthFromChildren();
    };

    AVLTree.prototype.rotateRR = function() {
    @@ -74,11 +74,7 @@ AVLTree.prototype.rotateRR = function() {
    this.left.right = this.left.left;
    this.left.left = leftBefore;
    this.left.node = nodeBefore;
    this.left.updateInNewLocation();
    this.updateInNewLocation();
    };

    AVLTree.prototype.updateInNewLocation = function() {
    this.left.getDepthFromChildren();
    this.getDepthFromChildren();
    };

  17. Eh2406 revised this gist Mar 31, 2014. 1 changed file with 3 additions and 11 deletions.
    14 changes: 3 additions & 11 deletions avltree.js
    View file
    Original file line number Diff line number Diff line change
    @@ -15,7 +15,6 @@ AVLTree.prototype.init = function(n, attr) {
    this.right = null;
    this.node = n;
    this.depth = 1;
    this.elements = [n];
    //chain object
    return this;
    };
    @@ -54,33 +53,27 @@ AVLTree.prototype.balance = function() {
    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();
    };
    @@ -102,11 +95,10 @@ AVLTree.prototype.getDepthFromChildren = function() {
    AVLTree.prototype.add = function(n) {
    var o = this.attr(n, this.node), ret = false;
    if (o == 0) {
    this.elements.push(n);
    return false;
    } else if (o < 0) {
    if (this.left == null) {
    this.left = new AVLTree(n, this.attr);
    this.left = AVLTree(n, this.attr);
    ret = true;
    } else {
    ret = this.left.add(n);
    @@ -116,7 +108,7 @@ AVLTree.prototype.add = function(n) {
    }
    } else { // o > 0
    if (this.right == null) {
    this.right = new AVLTree(n, this.attr);
    this.right = AVLTree(n, this.attr);
    ret = true;
    } else {
    ret = this.right.add(n);
    @@ -139,7 +131,7 @@ AVLTree.prototype.toArray = function(arr) {
    } else {
    arr = arr || [];
    }
    arr.push.apply(arr, this.elements);
    arr.push.apply(arr, this.node);
    if (this.right != null) {
    arr = this.right.toArray(arr);
    }
  18. Eh2406 revised this gist Mar 31, 2014. 1 changed file with 6 additions and 2 deletions.
    8 changes: 6 additions & 2 deletions avltree.js
    View file
    Original file line number Diff line number Diff line change
    @@ -6,7 +6,7 @@

    // Pass in the attribute you want to use for comparing
    function AVLTree(n, attr) {
    this.init(n, attr);
    return new AVLTree.prototype.init(n, attr);
    }

    AVLTree.prototype.init = function(n, attr) {
    @@ -16,8 +16,12 @@ AVLTree.prototype.init = function(n, attr) {
    this.node = n;
    this.depth = 1;
    this.elements = [n];
    //chain object
    return this;
    };

    AVLTree.prototype.init.prototype = AVLTree.prototype;

    AVLTree.prototype.balance = function() {
    var ldepth = this.left == null ? 0 : this.left.depth;
    var rdepth = this.right == null ? 0 : this.right.depth;
    @@ -34,7 +38,7 @@ AVLTree.prototype.balance = function() {
    }
    this.rotateLL();
    } else if (ldepth + 1 < rdepth) {
    // RR or RL rorarion
    // RR or RL rotation
    var rrdepth = this.right.right == null ? 0 : this.right.right.depth;
    var rldepth = this.right.left == null ? 0 : this.right.left.depth;

  19. Eh2406 revised this gist Mar 31, 2014. 1 changed file with 12 additions and 30 deletions.
    42 changes: 12 additions & 30 deletions avltree.js
    View file
    Original file line number Diff line number Diff line change
    @@ -95,20 +95,8 @@ AVLTree.prototype.getDepthFromChildren = function() {
    }
    };

    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), ret = false;
    var o = this.attr(n, this.node), ret = false;
    if (o == 0) {
    this.elements.push(n);
    return false;
    @@ -140,22 +128,16 @@ AVLTree.prototype.add = function(n) {
    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 [];
    // Convert tree to an array in sorted order
    AVLTree.prototype.toArray = function(arr) {
    if (this.left != null) {
    arr = this.left.toArray(arr);
    } else {
    arr = arr || [];
    }
    else if (value > substr) {
    if (this.right != null) {
    return this.right.findBest(value);
    }
    return [];
    arr.push.apply(arr, this.elements);
    if (this.right != null) {
    arr = this.right.toArray(arr);
    }
    return this.elements;
    }
    return arr;
    }
  20. Eh2406 revised this gist Mar 31, 2014. 1 changed file with 3 additions and 6 deletions.
    9 changes: 3 additions & 6 deletions avltree.js
    View file
    Original file line number Diff line number Diff line change
    @@ -108,14 +108,11 @@ AVLTree.prototype.compare = function(n1, n2) {
    };

    AVLTree.prototype.add = function(n) {
    var o = this.compare(n, this.node);
    var o = this.compare(n, this.node), ret = false;
    if (o == 0) {
    this.elements.push(n);
    return false;
    }

    var ret = false;
    if (o == -1) {
    } else if (o < 0) {
    if (this.left == null) {
    this.left = new AVLTree(n, this.attr);
    ret = true;
    @@ -125,7 +122,7 @@ AVLTree.prototype.add = function(n) {
    this.balance();
    }
    }
    } else if (o == 1) {
    } else { // o > 0
    if (this.right == null) {
    this.right = new AVLTree(n, this.attr);
    ret = true;
  21. Jeremy Stephens created this gist Apr 19, 2012.
    164 changes: 164 additions & 0 deletions avltree.js
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,164 @@
    // 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;
    }