private RedBlackTreeNode < Key , Value > select ( RedBlackTreeNode < Key , Value > x , int k ) { // assert x != null; // assert k >= 0 && k < size(x); int t = size ( x . getLeft ( ) ) ; if ( t > k ) return select ( x . getLeft ( ) , k ) ; else if ( t < k ) return select ( x . getRight ( ) , k - t - 1 ) ; else return x ; }
the key of rank k in the subtree rooted at x