although these arrangements are equally validyou can see that the tree in bis not balancedwhile that in cis given the red-black tree in )we would want to rotate it to the right (and perform two color changesto balance it amazinglythis rotation results in the exact same tree shown in cthus we see an equivalence between rotations in red-black trees and the choice of which node to make the parent when transforming trees to red-black trees although we don' show ita similar equivalence can be seen for the double rotation necessary for inside grandchildren efficiency of trees it' harder to analyze the efficiency of tree than red-black treebut the equivalence of red-black trees and trees gives us starting point speed as we saw in in red-black tree one node on each level must be visited during searchwhether to find an existing node or insert new one the number of levels in red-black tree ( balanced binary treeis about log ( + )so search times are proportional to this one node must be visited at each level in tree as wellbut the tree is shorter (has fewer levelsthan red-black tree with the same number of data items refer to figure where the tree has three levels and the red-black tree has five more specificallyin trees there are up to children per node if every node were fullthe height of the tree would be proportional to log logarithms to the base and to the base differ by constant factor of thusthe height of tree would be about half that of red-black treeprovided that all the nodes were full because they aren' all fullthe height of the tree is somewhere between log ( + and log ( + )/ thusthe reduced height of the tree decreases search times slightly compared with red-black trees on the other handthere are more items to examine in each nodewhich increases the search time because the data items in the node are examined using linear searchthis multiplies the search times by an amount proportional to mthe average number of items