avltree.js

// 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;
}

do u have an example of this implementation? i don't know how add a new node :(