Black depth in Red Black tree? How to know if it is balanced?

I have a midterm on tuesday, and am having trouble understanding red black trees. How do I know the tree is balanced? I know it has something to do with the correct amount of black nodes, and the black depth. But I don't quite understand it. I need to know this because you base the tree rotations on this. If someone could provide step by step explanation, that would be great. Thanks!

The rules for a red-black tree are :

• The root is black
• Nil nodes are black (sometimes omitted)
• A red node cannot have a red child
• The path from the root to every leaf contains the same number of black nodes

So, the rule you are referring to is the last I assume. Another way to put it by drawing the tree : If you represent a red-black tree with black links being vertical and red links being horizontal, then all of the leaves end up on the same layer.

If a tree follows these four rules, then it is a valid red-black tree. Rule 1 and 2 are easy to fix. If the tree does not follow rule 3 it is code red violation and if it does not follow rule 4 it is called a black violation.

In the below examples, the two trees contain a black violation, because the fourth rule is not respected.

        2,B                   2,B 

       /   \                 /   \ 

     1,B   0,R           1,B      6,B  

                        /        /   \   

                       0,B      4,R   8,R

If your concern is to determine whether a red-black tree is valid or not, then maybe you should just draw some and look if they respect the rules. If you need to understand the operations, you'd need to look at some tutorials, there are plenty on the Internet.

In any case, a great tutorial about red-black trees can be found here : http://eternallyconfuzzled.com/tuts/datastructures/jsw_tut_rbtree.aspx

You can just skip the implementations part if you're not interested, but it goes through the rules, representation and algorithms explaining why it works this way.

Hope this helps.