public static <TNode extends AvlNode> TNode remove(TNode root, Object key,
      final AvlKeyComparator<TNode> keyComparator, final AtomicBoolean removed) {
      if (root == null) return null;

      int cmp = keyComparator.compareKey(root, key);
      if (cmp == 0) {
        if (removed != null) removed.set(true);

        TNode q = (TNode) root.avlLeft;
        TNode r = (TNode) root.avlRight;
        if (r == null) return q;
        TNode min = getFirst(r);
        min.avlRight = removeMin(r);
        min.avlLeft = q;
        return balance(min);
      } else if (cmp > 0) {
        root.avlLeft = remove((TNode) root.avlLeft, key, keyComparator);
      } else /* if (cmp < 0) */ {
        root.avlRight = remove((TNode) root.avlRight, key, keyComparator);
      }
      return balance(root);
    }
Removes the node matching the specified key from the tree
@param root          the current root of the tree
@param key           the key for the node we are trying to find
@param keyComparator the comparator to use to match node and key
@param removed       will be set to true if the node was found and removed, otherwise false
@return the new root of the tree
hbase-common/src/main/java/org/apache/hadoop/hbase/util/AvlUtil.java