realized by red-black treewhere denotes the size of the collection returned by findall the space usage is (noperation time sizeisempty ( findinsertremove (lognfindall (logn +sfigure illustrating the running time of searches and updates in red-black tree the time performance is ( per levelbroken into down phasewhich typically involves searchingand an up phasewhich typically involves recolorings and performing local trinode restructurings (rotations