public static <TNode extends AvlNode> TNode insert(TNode root, Object key,
      final AvlKeyComparator<TNode> keyComparator,
      final AvlInsertOrReplace<TNode> insertOrReplace) {
      if (root == null) {
        return insertOrReplace.insert(key);
      }

      int cmp = keyComparator.compareKey(root, key);
      if (cmp < 0) {
        root.avlLeft = insert((TNode) root.avlLeft, key, keyComparator, insertOrReplace);
      } else if (cmp > 0) {
        root.avlRight = insert((TNode) root.avlRight, key, keyComparator, insertOrReplace);
      } else {
        TNode left = (TNode) root.avlLeft;
        TNode right = (TNode) root.avlRight;
        root = insertOrReplace.replace(key, root);
        root.avlLeft = left;
        root.avlRight = right;
        return root;
      }
      return balance(root);
    }
Insert a node into the tree. This is useful when you want to create a new node or replace the
content depending if the node already exists or not. Using AvlInsertOrReplace class you can
return the node to add/replace.
@param root            the current root of the tree
@param key             the key for the node we are trying to insert
@param keyComparator   the comparator to use to match node and key
@param insertOrReplace the class to use to insert or replace the node
@return the new root of the tree
hbase-common/src/main/java/org/apache/hadoop/hbase/util/AvlUtil.java