Why Red Black Trees always having nil nodes as their leaf nodes and what is it implies?

Question

I don't know why we need the NIL node as a leaf node in Red-Black Trees. Can anyone give an explanation about its purpose?

Answer 1

NIL is a special type of node which indicates the leaf nodes in the other trees like binary search trees and AVL trees

NIL nodes helps for balancing the black height

When you delete a node black height is immediately pass to child if it has no children it has to passed someone... so NIL nodes helps to it

Another way when you insert a new node nil node helps us to identify the case we have faced (either uncle red or uncle black) sometimes uncle will can be NIL node

Answer 2

Red-black trees don't need NIL nodes. Indeed, in typical implementations of the structure, NIL nodes are omitted entirely to reduce memory consumption. Moreover, we can alter the definition of red-black tree to avoid mention of NIL nodes without losing any of the essential qualities of the structure:

Define a red-black tree to be a binary search tree with the additional properties that

1. Each node possesses a color attribute which is either red or black.
2. If a black node has just one child, the child must be red and a leaf.
3. A red node is either a leaf or has two black children.
4. All paths from root to leaf must have the same number of black nodes.

Take any red-black tree with NIL nodes, erase the NIL nodes, and it will satisfy the definition above. Conversely, take a tree that satisfies the definition above, put black NIL nodes beneath each non-NIL node with fewer than two children so that they have two children, and it will be a red-black tree according to the standard definition.