title: Removing node from a totally black red black tree
body: <p>I am reading the <a href="http://en.wikipedia.org/wiki/Red%E2%80%93black_tree#Removal" rel="nofollow">Wikipedia explanation of red black tree removal process</a>.</p>
  
  <p>There is one simple thing which I am not able to understand.</p>
  
  <p>Example: I have a totally black RBTree</p>
  
  <pre><code>                     3(B)
                   /          \
                  /            \
                 1(B)          5(B)
               /     \        /    \
              /       \      /      \
             0(B)     2(B) 4(B)     6(B)
  </code></pre>
  
  <p>Wikipedia states that if you have a node to delete with 2 leaf children and the sibling is also a node with 2 Leaf children, then we can simply remove the node and recolor the parent and sibling.</p>
  
  <p>Suppose in the tree above I want to delete 0. Then no amount of recoloring 1 or 2 helps because no matter what you do, the two subrees (the 1 side) and the 5 side end up with different black heights.</p>
  
  <p>What am I missing?</p>
  
  <p>I found that Wikipedia had a very good explanation of insert, but the explanation of delete is confusing.</p>