justificationlet be red-black tree storing entriesand let be the height of we justify this proposition by establishing the following factlog( < < log( let be the common black depth of all nodes of having zero or one children let be the ( tree associated with and let be the height of (excluding trivial leavesbecause of the correspondence between red-black trees and ( treeswe know that henceby proposition <log( ) by the red propertyh < thuswe obtain < log( ) the other inequalitylog( <hfollows from proposition and the fact that has nodes red-black tree operations the algorithm for searching in red-black tree is the same as that for standard binary search tree (section thussearching in red-black tree takes time proportional to the height of the treewhich is (log nby proposition the correspondence between ( trees and red-black trees provides important intuition that we will use in our discussion of how to perform updates in red-black treesin factthe update algorithms for red-black trees can seem mysteriously complex without this intuition split and fuse operations of ( tree will be effectively mimicked by recoloring neighboring red-black tree nodes rotation within red-black tree will be used to change orientations of -node between the two forms shown in figure (binsertion now consider the insertion of key-value pair (kvinto red-black tree the algorithm initially proceeds as in standard binary search tree (section namelywe search for in until we reach null subtreeand we introduce new leaf at that positionstoring the item in the special case that is the only node of and thus the rootwe color it black in all other caseswe color red this action corresponds to inserting (kvinto node of the ( tree with external children the insertion preserves the root and depth properties of but it may violate the red property indeedif is not the root of and the parent of is redthen we have parent and child (namelyy and xthat are both red note that by the root propertyy cannot be the root of and by the red property (which was previously satisfied)the parent of must be black since and its parent are redbut ' grandparent is blackwe call this violation of the red property double red at node to remedy double redwe consider two cases