Yes, but the incrmental sorting problem requires that the k elements are not only sorted, but are the k first elements of the whole sequence of length N.
How would you use an RB tree to do incremental sorting? Wouldn't you have to insert all the elements into the tree up-front? That would certainly be slower, but maybe you mean something different.