Dear,
First let you know the Red-Black Tree
It is a self balancing Binary search tree allow efficient in-order traversal of elements provided that there is a way to locate the parent of any node. The search-time results from the traversal from root to leaf, and therefore a balanced tree, having the least possible tree height, results in O(log n) search time.
red-black tree is a binary search tree where each node has a color attribute, the value of which is either red or black. In addition to the ordinary requirements imposed on binary search trees,
Following properties will consider
- A node is either red or black.
- The root is black. (This rule is used in some definitions and not others. Since the root can always be changed from red to black but not necessarily vice-versa this rule has little effect on analysis.)
- All leaves are black, even when the parent is black (The leaves are the null children.)
- Both children of every red node are black.
- All paths from any given node to its leaf nodes contain the same number of black nodes.is threatened only by adding a black node, repainting a red node black, or a rotation.
Insertion:
Insertion begins by adding the node as simple binary search tree and coloring it red. What happens next depends on the color of other nearby nodes.
- Property 3 (All leaves, including nulls, are black) always holds.
- Property 4 (Both children of every red node are black) is threatened only by adding a red node, repainting a black node red, or a rotation.
- Property 5 (All paths from any given node to its leaf nodes contain the same number of black nodes) is threatened only by adding a black node, repainting a red node black, or a rotation.
so, now we need to implement RB-INSERT tree for 'n' nodes.
there is any empty tree shouldn't call Red-Black tree. It needs to satisfy above properties.
Insertion begins by adding the node as simple binary search tree and coloring it red in RB-INSERT(T, z). If we needs to implement RB-INSERT-FIXUP(T, z) in these three cases atleast one node as red. So, we can easily say more than one node contains atleast one red.