Red Black Tree | is this tree balanced?

Question

I have recently begun studying the structure of the red-black tree and am struggling to determine whether it is balanced. And explain why it is still balanced, or vice versa.

                                     10(black node)
                                       /          \
                              8(black node)       None (black node)
                              /           \
                      None(black node)   None(black node)

I just want to get an explanation of the theory on red black trees.

Answer 1

No, that tree is not balanced. For red-black trees "balanced" means that every path from the root to a leaf has the same number of black nodes. This is not the case in your example tree, as the paths that include node 8 have 3 black nodes, while the path that goes to the rightmost leaf has only 2 black nodes.

As a consequence of that rule, a node with one NIL child cannot have another child that is a black non-NIL node. In your tree the root node violates that rule.

If you would color the node with value 8 with red, then the tree becomes a valid red-black tree, because then you reduce the number of black nodes on the root-to-leaf paths that pass via that node.

For an in-depth explanation on red-black trees, please see the Wikipedia article on red-black trees