title: Convert AVL Trees to Red Black tree
body: <p>I read this statement somewhere that the nodes of any AVL tree T can be colored “red” and “black” so that T becomes a red-black tree.</p>
  
  <p>This statement seems quite convincing but I didn't understand how to formally proof this statement.</p>
  
  <p>According to wiki, A red black tree should satisfy these five properties:</p>
  
  <p>a.A node is either red or black.</p>
  
  <p>b.The root is black. This rule is sometimes omitted. Since the root can always be changed from red to black, but not necessarily vice versa, </p>
  
  <p>c. All leaves (NIL) are black.</p>
  
  <p>d.If a node is red, then both its children are black.</p>
  
  <p>e.Every path from a given node to any of its descendant NIL nodes contains,the same number of black nodes. </p>
  
  <p>The four conditions is quite simple, I got stuck how to proof statement 5 </p>