/** Inserts a right child at a given node. */ public Position insertRight(Position v, Object e) throws InvalidPositionException { if (hasRight(v)) throw new InvalidPositionException("Node already has a right child"); BTPosition vv = (BTPosition)v; BTPosition w = createNode(e, vv, null, null); vv.setRight(w); size++; return w; } /** Removes a node with zero or one child. */ public Object remove(Position v) throws InvalidPositionException { if (hasLeft(v) && hasRight(v)) throw new InvalidPositionException("Cannot remove node w/ 2 children"); BTPosition vv = (BTPosition)v; BTPosition ww; // the only child of v, if any if (hasLeft(v)) ww = (BTPosition) left(v); else if (hasRight(v)) ww = (BTPosition) right(v); else ww = null; if (v == root()) { if (ww != null) ww.setParent(null); root = ww; } else { BTPosition uu = (BTPosition) parent(v); if (hasLeft(uu) && v == left(uu)) uu.setLeft(ww); else uu.setRight(ww); if(ww != null) ww.setParent(uu); } size--; return v.element(); }