public static <TNode extends AvlNode> TNode insert(TNode root, TNode node) {
      if (root == null) return node;

      int cmp = node.compareTo(root);
      assert cmp != 0 : "node already inserted: " + root;
      if (cmp < 0) {
        root.avlLeft = insert(root.avlLeft, node);
      } else {
        root.avlRight = insert(root.avlRight, node);
      }
      return balance(root);
    }
Insert a node into the tree. It uses the AvlNode.compareTo() for ordering. NOTE: The node
must not be already in the tree.
@param root the current root of the tree
@param node the node to insert
@return the new root of the tree
hbase-common/src/main/java/org/apache/hadoop/hbase/util/AvlUtil.java