red-black tree is binary search tree with the following coloring properties every node is colored either red or black the root is black if node is redits children must be black every path from node to null pointer must contain the same number of black nodes consequence of the coloring rules is that the height of red-black tree is at most log( consequentlysearching is guaranteed to be logarithmic operation figure shows red-black tree red nodes are shown with double circles the difficultyas usualis inserting new item into the tree the new itemas usualis placed as leaf in the tree if we color this item blackthen we are certain to violate condition because we will create longer path of black nodes thusthe item must be colored red if the parent is blackwe are done if the parent is already redthen we will violate condition by having consecutive red nodes in this casewe have to adjust the tree to ensure that condition is enforced (without introducing violation of condition the basic operations that are used to do this are color changes and tree rotations bottom-up insertion as we have already mentionedif the parent of the newly inserted item is blackwe are done thus insertion of into the tree in figure is trivial there are several cases (each with mirror image symmetryto consider if the parent is red firstsuppose that the sibling of the parent is black (we adopt the convention that null nodes are blackthis would apply for an insertion of or but not for the insertion of let be the newly added leafp be its parents be the sibling of the parent (if it exists)and be the grandparent only and are red in this caseg is blackbecause otherwise there would be two consecutive red nodes prior to the insertionin violation of red-black rules adopting the splay tree terminologyxpand can form either zig-zig figure example of red-black tree (insertion sequence is