since the case action eliminates the double-red problem with single trinode restructuring and the case action performs no restructuring operationsat most one restructuring is needed in red-black tree insertion by the above analysis and the fact that restructuring or recoloring takes ( timewe have the followingproposition the insertion of key-value entry in red-black tree storing entries can be done in (logntime and requires (lognrecolorings and one trinode restructuring ( restructure operation