private Node < K , V > nextGreater ( final Node < K , V > node , final int index ) { Node < K , V > rval ; if ( node == null ) { rval = null ; } else if ( node . getRight ( index ) != null ) { // everything to the node's right is larger. The least of // the right node's descendants is the next larger node rval = leastNode ( node . getRight ( index ) , index ) ; } else { // traverse up our ancestry until we find an ancestor that // is null or one whose left child is our ancestor. If we // find a null, then this node IS the largest node in the // tree, and there is no greater node. Otherwise, we are // the largest node in the subtree on that ancestor's left // ... and that ancestor is the next greatest node Node < K , V > parent = node . getParent ( index ) ; Node < K , V > child = node ; while ( ( parent != null ) && ( child == parent . getRight ( index ) ) ) { child = parent ; parent = parent . getParent ( index ) ; } rval = parent ; } return rval ; }
get the next larger node from the specified node