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 four 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 since they aren' all fullthe height of the tree is somewhere between log ( + and log ( + )/ the 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 per node the result is search time proportional to *log some nodes contain one itemsome twoand some three if we estimate that the average is twosearch times will be proportional to *log this is small constant number that can be ignored in big notation thusfor trees the increased number of items per node tends to cancel out the decreased height of the tree the search times for tree and for balanced binary tree such as red-black tree are approximately equaland are both (lognstorage requirements each node in tree contains storage for three references to data items and four references to its children this space may be in the form of arraysas shown in tree javaor of individual variables not all this storage is used node with only one data item will waste / of the space for data and / the space for children node with two data items will waste / of the space for data and / of the space for childrenor put another wayit will use / of the available space