suggested new API funcs (with code): find_ge() and find_gt()

[lsemprini]

Currently, find() lets us fetch the node EXACTLY equal to a key.

Currently there is no easy way to fetch the node >= or > key. range() kind of does it, but only works for the >= case, and, much more importantly, requires the user to provide a key value for "end" that is "infinity" or "past the end of any possible key," which is not always easy to create depending on the application.

Even worse, when noDuplicates is false, find() essentially returns a random node when the tree contains more than one node with the same key (whichever node happens to be higher up in the tree), which is unlikely to be what any user wants in any application.

To fix all 3 of these problems, let me offer you 2 new API funcs that you could drop in:

  /**
   * Return the first node whose key is >= `key`.
   * Return null if tree is empty or all node keys are < `key`.
   * If tree was created with !noDuplicates and tree contains 
   * more than one node with the first key >= `key`, 
   * returns the first such node.
   * @param{Key}    key
   * @return {?Node}
   */
  AVLTree.prototype.find_ge = function find_ge(key) {

    var Q = [];
    var compare = this._comparator;
    var node = this._root, cmp;

    while (Q.length !== 0 || node) {
      if (node) {
        Q.push(node);
        /* if ( this._noDuplicates) node.key >  node.left subtree nodes
         * if (!this._noDuplicates) node.key >= node.left subtree nodes
         */
        cmp = compare(node.key, key);
        if (this._noDuplicates && cmp <= 0)
          /* node.key <= key, so node.left subtree
           * cannot contain the node we want to return.
           * if node.key === key, we can still skip node.left
           * because tree contains no duplicates.
           */
          node = null;
        else if (!this._noDuplicates && cmp < 0)
          /* node.key < key, so node.left subtree
           * cannot contain the node we want to return.
           * if node.key === key, we must still examine node.left
           * because tree might contain duplicates and we
           * must return first node matching key.
           */
          node = null;
        else
          node = node.left;
      } else {
        node = Q.pop();
        if (compare(node.key, key) >= 0) {
          return node;
        }
        node = node.right;
      }
    }
    return null;
  };

  /**
   * Return the first node whose key is > `key`.
   * Return null if tree is empty or all node keys are <= `key`.
   * If tree was created with !noDuplicates and tree contains 
   * more than one node with the first key > `key`, 
   * returns the first such node.
   * @param{Key}    key
   * @return {?Node}
   */
  AVLTree.prototype.find_gt = function find_gt(key) {

    var Q = [];
    var compare = this._comparator;
    var node = this._root, cmp;

    while (Q.length !== 0 || node) {
      if (node) {
        Q.push(node);
        /* if ( this._noDuplicates) node.key >  node.left subtree nodes
         * if (!this._noDuplicates) node.key >= node.left subtree nodes
         */
        cmp = compare(node.key, key);
        if (cmp <= 0)
          /* node.key <= key, so node.left subtree
           * cannot contain the node we want to return.
           * if node.key === key, we can still skip node.left
           * regardless of this._noDuplicates.
           */
          node = null;
        else
          node = node.left;
      } else {
        node = Q.pop();
        if (compare(node.key, key) >= 0) {
          return node;
        }
        node = node.right;
      }
    }
    return null;
  };

NOTE I have tested find_ge() somewhat and have not yet tested find_gt() so be sure to check them over...

It would be nice to also include find_lt() and find_le() which return the HIGHEST node satisfying the condition and, if noDuplicates is false, return the last node in a possible group of nodes that have the highest key.