What is the time complexity in a red-black tree for k consecutive calls to move forward in the iteration order?
In a binary search tree you can prove that any sequence of k calls to advance (moving forward in the iteration order) or to retreat (moving backwards in the iteration order) has worst case time O(h + k) where h is the height of the tree. Thus for a red-black tree (and also for other ordered collection data structures) any sequence of k calls to advance has worst-case time O(log n + k). Most likely you will find this fact useful for the homework. You can use it without proof.
