and red-black tree( -node( -node( -node 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 trees in factthe update algorithms for red-black trees are mysteriously complex without this intuition proposition the height of red-black tree storing entries is (lognjustificationlet 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 the external nodes of let be the ( , tree associated with tand let be the height of because of the correspondence between red-black trees and ( , treeswe know that henceby proposition <log( by the internal node propertyh < thuswe obtain <