We can derive a simple (?) rule for determining the node in the binary search tree that immediately follows node i in the sorted order (returns NULL for max element in tree):
int Successor( Tree T, int i ) {
int j;
if( T[right][i] != NULL ) {
j = T[right][i];
while( T[left][j] != NULL ) // T[leftcolor][j] = black;
j = T[left][j];
return j;
}
j = T[parent][i];
while( T[parent][j] != NULL && j == isrightchild(T, j))
j = T[parent][j]; // T[rightcolor][j] = black;
return T[parent][j];
}
Running time in terms of the height of the tree?
How do test for being a right child?
How could this be used to delete an element from the tree?
How could this be used to sort?
