data structures using case running time for its operations and is efficient to use as searchinginsertionand deletion can all be done in (log ntimewhere is the number of nodes in the tree practicallya red-black tree is binary search tree which inserts and removes intelligentlyto keep the tree reasonably balanced special point to note about the red-black tree is that in this treeno data is stored in the leaf nodes properties of red-black trees red-black tree is binary search tree in which every node has colour which is either red or black apart from the other restrictions of binary search treethe red-black tree has the following additional requirements the colour of node is either red or black the colour of the root node is always black all leaf nodes are black every red node has both the children coloured in black every simple path from given node to any of its leaf nodes has an equal number of black nodes look at fig which shows red-black tree black red null null null null null null null null null null null figure red-black tree these constraints enforce critical property of red-black trees the longest path from the root node to any leaf node is no more than twice as long as the shortest path from the root to any other leaf in that tree this results in roughly balanced tree since operations such as insertiondeletionand searching require worst-case times proportional to the height of the treethis theoretical upper bound on the height allows red-black trees to be efficient in the worst caseunlike ordinary binary search trees to understand the importance of these propertiesit suffices to note that according to property no path can have two red nodes in row the shortest possible path will have all black nodesand the longest possible path would alternately have red and black node since all maximal paths have the same number of black nodes (property )no path is more than twice as long as any other path figure shows some binary search trees that are not red-black trees