performance of red-black trees the asymptotic performance of red-black tree is identical to that of an avl tree or ( tree in terms of the sorted map adtwith guaranteed logarithmic time bounds for most operations (see table for summary of the avl performance the primary advantage of red-black tree is that an insertion or deletion requires only constant number of restructuring operations (this is in contrast to avl trees and ( treesboth of which require logarithmic number of structural changes per map operation in the worst case that isan insertion or deletion in red-black tree requires logarithmic time for searchand may require logarithmic number of recoloring operations that cascade upward yet we showin the following propositionsthat there are constant number of rotations or restructure operations for single map operation proposition the insertion of an item in red-black tree storing items can be done in (log ntime and requires (log nrecolorings and at most one trinode restructuring justificationrecall that an insertion begins with downward searchthe creation of new leaf nodeand then potential upward effort to remedy double-red violation there may be logarithmically many recoloring operations due to an upward cascading of case applicationsbut single application of the case action eliminates the double-red problem with trinode restructuring thereforeat most one restructuring operation is needed for red-black tree insertion proposition the algorithm for deleting an item from red-black tree with items takes (log ntime and performs (log nrecolorings and at most two restructuring operations justificationa deletion begins with the standard binary search tree deletion algorithmwhich requires time proportional to the height of the treefor red-black treesthat height is (log nthe subsequent rebalancing takes place along an upward path from the parent of deleted node we considered three cases to remedy resulting black deficit case requires trinode restructuring operationyet completes the processso this case is applied at most once case may be applied logarithmically many timesbut it only involves recoloring of up to two nodes per application case requires rotationbut this case can only apply oncebecause if the rotation does not resolve the problemthe very next action will be terminal application of either case or case in the worst casethere will be (log nrecolorings from case single rotation from case and trinode restructuring from case