Search code examples
data-structuresred-black-tree

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

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?

Solution

  • 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