Seach Cost of Binary Search Tree VS Red-Black Tree

Question

I know that a Red-Black Tree is just a balanced binary search tree. So I computed the average search cost(basically the number of comparisons) for data sets with the number of elements being 2^n. The data was designed in such a way that it would form a perfect binary search tree. However, after calculating the average cost, I realized that the computed average search costs for the Red-black tree is slightly higher that for the perfectly balanced binary search trees. Here is my table:

# of elements    Binary S. Tree     Red-Black Tree
    1          |    1            |   1
    3          |  1.66667        |   1.6667
    7          |  2.42857        |   2.71429
    15         |  3.26667        |   3.4
    31         |  4.16129        |   4.48387
    63         |  5.09524        |   5.50794
    127        |  6.05512        |   6.44882
    255        |  7.03137        |   7.31373
    511        |  8.01761        |   8.40509
    1023       |  9.00978        |   9.45357
    2047       |  10.0054        |   10.4919
    4095       |  11.0029        |   11.5314

I have two questions: How do you justify that and also is there a lower bound for on the computed average costs for Red-Black Trees?

Answer 1

The accepted search complexity for an RB tree is amortized O(log n), that is both an upper and lower bound. A perfectly balanced tree will have search complexity that is actually O(log n) rather than merely amortized.

The difficulty of specifying red-black trees to any tighter bounds is that it depends very much on the implementation and the data that is inserted (and perhaps removed). For example, if you build a red-black tree by inserting items from a already sorted array one-by-one in order you will end up with a maximally unbalanced red-black tree. But it is also possible to create an red-black tree from that array and have it be optimally balanced (by creating the initial tree with something other than the red-black algorithm and only switching to the RB algorithm for further inserts/removes).