3><span class="section-number">6.4.2.2. </span>Red-Black Trees<a class="headerlink" href="#red-black-trees" title="Link to this heading">#</a></h3>
<ul class="simple">
<li><p>definition</p>
<ol class="arabic simple">
<li><p>A node is either red or black</p></li>
<li><p>The root is black</p></li>
<li><p>All leaves are black
The leaves may be the NULL children</p></li>
<li><p>Both children of every red node are black
Therefore, a black node is the only possible parent for a red node</p></li>
<li><p>Every simp