Very close to log based two of N. So easy to prove by correspondence with 2-3 trees that t he height is guaranteed to be less than two log base two N. Every search in left-leaning red black three is guaranteed to take less than two log base two of N cuz every path gets the same number of black links so you never have two red links in a row. 