public Object insert(K value) {
    //
    //  We initialise the node first, based on the assumption we can always add
    //  more.  In the special case of an empty tree, assign this as the root.
    final Node i = new Node() ;
    i.value = value ;
    i.belongs = this ;
    if (root == null) {
      i.side = Side.R ;
      root = i ;
    }
    else {
      //
      //  Otherwise, search for the first unoccupied leaf node intermediate in
      //  value between existing entries-
      Node n = root ; while (true) {
        final int comp = compare(value, (K) n.value) ;
        final Side s = (comp > 0) ? Side.R : Side.L ;
        final Node k = kidFor(n, s) ;
        if (k == null) { setParent(n, i, s) ; break ; }
        else n = k ;
      }
      //
      //  Finally, propagate the change as a signal up the tree structure,
      //  rebalancing as required, and return the original node.
      flagForUpdate(i) ;
      updateHeight(i.parent) ;
      balanceFrom(i.parent.parent) ;
    }
    size++ ;
    if (verbose) {
      I.say("\n\n...AFTER INSERTION:") ;
      I.say(this.toString()) ;
    }
    return i ;
  }