How does the R-B tree's find function implement in SGI STL?

Question

Recently, I was learning SGI STL source code. when I read the R-B tree's find function, I cannot understand its code. First, paste the code, and there is an example, could anyone explain the find progress? Thanks.

template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
typename rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::iterator 
rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::find(const Key& k) {
    link_type y = header;        // Last node which is not less than k. 
    link_type x = root();        // Current node. 

    while (x != 0) 
        if (!key_compare(key(x), k)) 
            y = x, x = left(x); //value of x is bigger than k
        else
            x = right(x); //value of x is less than k

        iterator j = iterator(y);   
    return (j == end() || key_compare(k, key(j.node))) ? end() : j;
}

One example,

I want to find node with value 70, and 90. Could anyone show me the progress? Thanks. And, What confused me is the code: [else x=right(x); and the return statement].

Thanks, I got this answer. Solved, I will give a example to find 70.

First, [x=root()=30, y=header], 30<70, so [x=x->right=60]; 
Second, 60<70:[x=x->right=70]; 
Then, 70>=70, so[ y=x=70, x = x->left=65]; 
last, 65<70:[x=x->right=NULL]; 
iterator j = iterator(y); 
return j;

Answer 1

In Red Black trees and all Binary search trees left child of any node is less and right child is greater than the node. To find a node with key we first compare the key with root node. IF it is greater then root's key we go to root's right child and compare key to it, otherwise we go to left child. Thus we can find 90 by visiting nodes 30->60->70->85->90. Since the height of RB tree is at most 2log(n+1) we can find any node in O(log(n)) time where n is number of nodes.