AVLTree.js

function(window, undefined) {
  var BIND = function(fn, selfObj, arguments) {
    if (!fn) {
      throw new Error;
    }
    if (arguments.length > 2) {
      var boundArgs = Array.prototype.slice.call(arguments, 2);
      return function() {
        var newArgs = Array.prototype.slice.call(arguments);
        Array.prototype.unshift.apply(newArgs, boundArgs);
        return fn.apply(selfObj, newArgs);
      };
    } else {
      return function() {
        return fn.apply(selfObj, arguments);
      };
    }
  };
  AVLTree = function(comparator) {
    this._comparator = comparator || AVLTree.DEFAULT_COMPARATOR;
  };
  AVLTree.DEFAULT_COMPARATOR = function(a, b) {
    if (String(a) < String(b)) {
      return -1;
    } else {
      if (String(a) > String(b)) {
        return 1;
      }
    }
    return 0;
  };
  AVLTree.prototype._root = null;
  AVLTree.prototype._comparator = null;
  AVLTree.prototype._minNode = null;
  AVLTree.prototype._maxNode = null;
  AVLTree.prototype.add = function(value) {
    if (this._root == null) {
      this._root = new AVLTree.Node(value);
      this._minNode = this._root;
      this._maxNode = this._root;
      return true;
    }
    var newNode = null;
    this._traverse(function(node) {
      var retNode = null;
      if (this._comparator(node.value, value) > 0) {
        retNode = node._left;
        if (node._left == null) {
          newNode = new AVLTree.Node(value, node);
          node._left = newNode;
          if (node == this._minNode) {
            this._minNode = newNode;
          }
        }
      } else {
        if (this._comparator(node.value, value) < 0) {
          retNode = node._right;
          if (node._right == null) {
            newNode = new AVLTree.Node(value, node);
            node._right = newNode;
            if (node == this._maxNode) {
              this._maxNode = newNode;
            }
          }
        }
      }
      return retNode;
    });
    if (newNode) {
      this._traverse(function(node) {
        node.count++;
        return node._parent;
      }, newNode._parent);
      this._balance(newNode._parent);
    }
    return !!newNode;
  };
  AVLTree.prototype.remove = function(value) {
    var retValue = null;
    this._traverse(function(node) {
      var retNode = null;
      if (this._comparator(node.value, value) > 0) {
        retNode = node._left;
      } else {
        if (this._comparator(node.value, value) < 0) {
          retNode = node._right;
        } else {
          retValue = node.value;
          this._removeNode(node);
        }
      }
      return retNode;
    });
    return retValue;
  };
  AVLTree.prototype.clear = function() {
    this._root = null;
    this._minNode = null;
    this._maxNode = null;
  };
  AVLTree.prototype.contains = function(value) {
    var isContained = false;
    this._traverse(function(node) {
      var retNode = null;
      if (this._comparator(node.value, value) > 0) {
        retNode = node._left;
      } else {
        if (this._comparator(node.value, value) < 0) {
          retNode = node._right;
        } else {
          isContained = true;
        }
      }
      return retNode;
    });
    return isContained;
  };
  AVLTree.prototype.getCount = function() {
    return this._root ? this._root.count : 0;
  };
  AVLTree.prototype.getNthValue = function(n) {
    if (n < 0 || n >= this.getCount()) {
      return null;
    }
    return this._getNthNode(n).value;
  };
  AVLTree.prototype.getMinimum = function() {
    return this._getMinNode().value;
  };
  AVLTree.prototype.getMaximum = function() {
    return this._getMaxNode().value;
  };
  AVLTree.prototype.getHeight = function() {
    return this._root ? this._root.height : 0;
  };
  AVLTree.prototype.getValues = function() {
    var retVal = [];
    this.inOrderTraverse(function(value) {
      retVal.push(value);
    });
    return retVal;
  };
  AVLTree.prototype.inOrderTraverse = function(func, startValue) {
    if (!this._root) {
      return;
    }
    var startNode;
    if (startValue) {
      this._traverse(function(node) {
        var retNode = null;
        if (this._comparator(node.value, startValue) > 0) {
          retNode = node._left;
          startNode = node;
        } else {
          if (this._comparator(node.value, startValue) < 0) {
            retNode = node._right;
          } else {
            startNode = node;
          }
        }
        return retNode;
      });
    } else {
      startNode = this._getMinNode();
    }
    var node = startNode, previous = startNode._left ? startNode._left : startNode;
    while (node != null) {
      if (node._left != null && node._left != previous && node._right != previous) {
        node = node._left;
      } else {
        if (node._right != previous) {
          if (func(node.value)) {
            return;
          }
        }
        var temp = node;
        node = node._right != null && node._right != previous ? node._right : node._parent;
        previous = temp;
      }
    }
  };
  AVLTree.prototype.reverseOrderTraverse = function(func, startValue) {
    if (!this._root) {
      return;
    }
    var startNode;
    if (startValue) {
      this._traverse(BIND(function(node) {
        var retNode = null;
        if (this._comparator(node.value, startValue) > 0) {
          retNode = node._left;
        } else {
          if (this._comparator(node.value, startValue) < 0) {
            retNode = node._right;
            startNode = node;
          } else {
            startNode = node;
          }
        }
        return retNode;
      }, this));
    } else {
      startNode = this._getMaxNode();
    }
    var node = startNode, prev = startNode._right ? startNode._right : startNode;
    while (node != null) {
      if (node._right != null && node._right != prev && node._left != prev) {
        node = node._right;
      } else {
        if (node._left != prev) {
          if (func(node.value)) {
            return;
          }
        }
        var temp = node;
        node = node._left != null && node._left != prev ? node._left : node._parent;
        prev = temp;
      }
    }
  };
  AVLTree.prototype.printAVLTree = function() {
    if (this._root !== null) {
      return this._root._inOrderPrint();
    }
    return false;
  };
  AVLTree.prototype._traverse = function(traversalFunc, startNode, endNode) {
    var node = startNode ? startNode : this._root;
    var endNode = endNode ? endNode : null;
    while (node && node != endNode) {
      node = traversalFunc.call(this, node);
    }
  };
  AVLTree.prototype._balance = function(node) {
    this._traverse(function(node) {
      var leftHeight = node._left ? node._left.height : 0;
      var rightHeight = node._right ? node._right.height : 0;
      if (leftHeight - rightHeight > 1) {
        if (node._left._right && (!node._left._left || node._left._left.height < node._left._right.height)) {
          this._leftRotate(node._left);
        }
        this._rightRotate(node);
      } else {
        if (rightHeight - leftHeight > 1) {
          if (node._right._left && (!node._right._right || node._right._right.height < node._right._left.height)) {
            this._rightRotate(node._right);
          }
          this._leftRotate(node);
        }
      }
      leftHeight = node._left ? node._left.height : 0;
      rightHeight = node._right ? node._right.height : 0;
      node.height = Math.max(leftHeight, rightHeight) + 1;
      return node._parent;
    }, node);
  };
  AVLTree.prototype._leftRotate = function(node) {
    if (node.isLeftChild()) {
      node._parent._left = node._right;
      node._right._parent = node._parent;
    } else {
      if (node.isRightChild()) {
        node._parent._right = node._right;
        node._right._parent = node._parent;
      } else {
        this._root = node._right;
        this._root._parent = null;
      }
    }
    var temp = node._right;
    node._right = node._right._left;
    if (node._right != null) {
      node._right._parent = node;
    }
    temp._left = node;
    node._parent = temp;
    temp.count = node.count;
    node.count -= (temp._right ? temp._right.count : 0) + 1;
  };
  AVLTree.prototype._rightRotate = function(node) {
    if (node.isLeftChild()) {
      node._parent._left = node._left;
      node._left._parent = node._parent;
    } else {
      if (node.isRightChild()) {
        node._parent._right = node._left;
        node._left._parent = node._parent;
      } else {
        this._root = node._left;
        this._root._parent = null;
      }
    }
    var temp = node._left;
    node._left = node._left._right;
    if (node._left != null) {
      node._left._parent = node;
    }
    temp._right = node;
    node._parent = temp;
    temp.count = node.count;
    node.count -= (temp._left ? temp._left.count : 0) + 1;
  };
  AVLTree.prototype._removeNode = function(node) {
    if (node._left != null || node._right != null) {
      var balanceBegin = null;
      var replacementNode;
      if (node._left != null) {
        r = this._getMaxNode(node._left);
        this._traverse(function(node) {
          node.count--;
          return node._parent;
        }, replacementNode);
        if (replacementNode != node._left) {
          replacementNode._parent._right = replacementNode._left;
          if (replacementNode._left) {
            replacementNode._left._parent = replacementNode._parent;
          }
          replacementNode._left = node._left;
          replacementNode._left._parent = replacementNode;
          balanceBegin = replacementNode._parent;
        }
        replacementNode._parent = node._parent;
        replacementNode._right = node._right;
        if (replacementNode._right) {
          replacementNode._right._parent = replacementNode;
        }
        if (node == this._maxNode) {
          this._maxNode = replacementNode;
        }
        replacementNode.count = node.count;
      } else {
        r = this._getMinNode(node._right);
        this._traverse(function(node) {
          node.count--;
          return node._parent;
        }, replacementNode);
        if (replacementNode != node._right) {
          replacementNode._parent._left = replacementNode._right;
          if (replacementNode._right) {
            replacementNode._right._parent = replacementNode._parent;
          }
          replacementNode._right = node._right;
          replacementNode._right._parent = replacementNode;
          balanceBegin = replacementNode._parent;
        }
        replacementNode._parent = node._parent;
        replacementNode._left = node._left;
        if (replacementNode._left) {
          replacementNode._left._parent = replacementNode;
        }
        if (node == this._minNode) {
          this._minNode = replacementNode;
        }
        replacementNode.count = node.count;
      }
      if (node.isLeftChild()) {
        node._parent._left = replacementNode;
      } else {
        if (node.isRightChild()) {
          node._parent._right = replacementNode;
        } else {
          this._root = replacementNode;
        }
      }
      this._balance(balanceBegin ? balanceBegin : replacementNode);
    } else {
      this._traverse(function(node) {
        node.count--;
        return node._parent;
      }, node._parent);
      if (node.isLeftChild()) {
        this.special = 1;
        node._parent._left = null;
        if (node == this._minNode) {
          this._minNode = node._parent;
        }
        this._balance(node._parent);
      } else {
        if (node.isRightChild()) {
          node._parent._right = null;
          if (node == this._maxNode) {
            this._maxNode = node._parent;
          }
          this._balance(node._parent);
        } else {
          this.clear();
        }
      }
    }
  };
  AVLTree.prototype._getNthNode = function(n, rootNode) {
    var root = rootNode || this._root;
    var numNodesInLeftSubtree = root._left ? root._left.count : 0;
    if (n < numNodesInLeftSubtree) {
      return this._getNthNode(n, root._left);
    } else {
      if (n == numNodesInLeftSubtree) {
        return root;
      } else {
        return this._getNthNode(n - numNodesInLeftSubtree - 1, root._right);
      }
    }
  };
  AVLTree.prototype._getMinNode = function(rootNode) {
    if (!rootNode) {
      return this._minNode;
    }
    var minNode = rootNode;
    this._traverse(function(node) {
      var retNode = null;
      if (node._left) {
        minNode = node._left;
        retNode = node._left;
      }
      return retNode;
    }, rootNode);
    return minNode;
  };
  AVLTree.prototype._getMaxNode = function(rootNode) {
    if (!rootNode) {
      return this._maxNode;
    }
    var maxNode = rootNode;
    this._traverse(function(node) {
      var retNode = null;
      if (node._right) {
        maxNode = node._right;
        retNode = node._right;
      }
      return retNode;
    }, rootNode);
    return maxNode;
  };
  AVLTree.Node = function(value, parent) {
    this.value = value;
    this._parent = parent ? parent : null;
    this.count = 1;
  };
  AVLTree.Node.prototype._inOrderPrint = function(padding) {
    padding = padding || "";
    padding = "--" + padding;
    if (this._left !== null) {
      this._left._inOrderPrint(padding);
    }
    console.log(padding + this.value);
    if (this._right !== null) {
      this._right._inOrderPrint(padding);
    }
  };
  AVLTree.Node.prototype._left = null;
  AVLTree.Node.prototype._right = null;
  AVLTree.Node.prototype.height = 1;
  AVLTree.Node.prototype.isRightChild = function() {
    return !!this._parent && this._parent._right == this;
  };
  AVLTree.Node.prototype.isLeftChild = function() {
    return !!this._parent && this._parent._left == this;
  };
  if (typeof module === "object" && module && typeof module.exports === "object") {
    module.exports = AVLTree;
  } else {
    window.AVLTree = AVLTree;
    if (typeof define === "function" && define.amd) {
      define("avltree", [], function() {
        return AVLTree;
      });
    }
  }
})(window);