A search in a red-blck tree with N nodes built from random keys seems to require about lg N comparisons, and an insertion seems to require less than one rotation, on the average. A search in a red-black tree with N nodes requires fewer than 2 lg N +2 comparisons, and an insertion requires fewer than 1/4 as many rotations as comparisons.