the fact that has internal nodes we assume that red-black tree is realized with linked structure for binary trees (section )in which we store dictionary entry and color indicator at each node thus the space requirement for storing keys is (nthe algorithm for searching in red-black tree is the same as that for standard binary search tree (section thussearching in red-black tree takes (logntime update operations performing the update operations in red-black tree is similar to that of binary search treeexcept that we must additionally restore the color properties insertion now consider the insertion of an entry with key into red-black tree tkeeping in mind the correspondence between and its associated ( , tree and the insertion algorithm for the algorithm initially proceeds as in binary search tree (section namelywe search for in until we reach an external node of tand we replace this node with an internal node zstoring ( ,xand having two external-node children if is the root of twe color blackelse we color red we also color the children of black this action corresponds to inserting ( ,xinto node of the ( , tree with external children in additionthis action preserves the rootexternal and depth properties of tbut it may violate the internal property indeedif is not the root of and the parent of is redthen we have parent and child (namelyv and zthat are both red note that by the root propertyv cannot be the root of tand by the internal 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 internal property double red at node to remedy double redwe consider two cases case the sibling of is black (see figure in this casethe double red denotes the fact that we have created in our red-black tree malformed replacement for corresponding -node of the ( , tree which has as its children the four black children of uvand our malformed replacement has one red node (vthat is the parent of another red node ( )while we want it to have the two red nodes as siblings instead to fix this problemwe perform trinode restructuring of the trinode restructuring is done by the operation restructure( )which consists of the following steps (see again figure this operation is also discussed in section )