红黑数算法及演示源代码

<p class="MsoNormal" style="text-indent:17.95pt;mso-char-indent-count:1.71;
mso-char-indent-size:10.45pt"><span lang="EN-US">ap[ak - 3]-&gt;link[ad[ak - 3]] 
= y;</span></p>
<p class="MsoNormal" style="text-indent:17.95pt;mso-char-indent-count:1.71;
mso-char-indent-size:10.45pt"><span lang="EN-US">break;</span></p>
<p class="MsoNormal" style="text-indent:17.95pt;mso-char-indent-count:1.71;
mso-char-indent-size:10.45pt"><span lang="EN-US"><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>}</span></p>
<p class="MsoNormal" style="text-indent:17.95pt;mso-char-indent-count:1.71;
mso-char-indent-size:10.45pt"><span lang="EN-US"><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp; </span>}</span></p>
<p class="MsoNormal" style="text-indent:17.95pt;mso-char-indent-count:1.71;
mso-char-indent-size:10.45pt"><span lang="EN-US">&nbsp;<o:p>
</o:p>
</span></p>
<p class="MsoNormal" style="text-indent:17.95pt;mso-char-indent-count:1.71;
mso-char-indent-size:10.45pt"><span style="font-family:宋体;mso-ascii-font-family:
&quot;Times New Roman&quot;;mso-hansi-font-family:&quot;Times New Roman&quot;">最后还有一点要说明</span></p>
<p class="MsoNormal" style="text-indent:17.95pt;mso-char-indent-count:1.71;
mso-char-indent-size:10.45pt"><span lang="EN-US">tree-&gt;root-&gt;color = 
RB_BLACK;</span></p>
<p class="MsoNormal" style="text-indent:17.95pt;mso-char-indent-count:1.71;
mso-char-indent-size:10.45pt"><span lang="EN-US">&nbsp;<o:p>
</o:p>
</span></p>
<p class="MsoNormal" style="text-indent:17.95pt;mso-char-indent-count:1.71;
mso-char-indent-size:10.45pt"><span lang="EN-US"><span style="mso-spacerun:
yes">&nbsp; </span>return 1;</span></p>
<p class="MsoNormal" style="text-indent:17.95pt;mso-char-indent-count:1.71;
mso-char-indent-size:10.45pt"><span lang="EN-US">}</span></p>
<p class="MsoNormal" style="text-indent:17.95pt;mso-char-indent-count:1.71;
mso-char-indent-size:10.45pt"><span style="font-family:宋体;mso-ascii-font-family:
&quot;Times New Roman&quot;;mso-hansi-font-family:&quot;Times New Roman&quot;">这是保证根结点必是黑色，因为在上面的过程中由于父或爷爷的结点可能变成红色而要加以考虑的，</span></p>
<p class="MsoNormal" style="text-indent:17.95pt;mso-char-indent-count:1.71;
mso-char-indent-size:10.45pt"><span lang="EN-US">&nbsp;<o:p>
</o:p>
</span></p>
<p class="MsoNormal" style="text-indent:17.95pt;mso-char-indent-count:1.71;
mso-char-indent-size:10.45pt"><span style="font-family:宋体;mso-ascii-font-family:
&quot;Times New Roman&quot;;mso-hansi-font-family:&quot;Times New Roman&quot;">综合三种情况，当第一种情况出现以后，到</span><span lang="EN-US">x</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;
mso-hansi-font-family:&quot;Times New Roman&quot;">的爷爷结点</span><span lang="EN-US">pp(x)</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;">的结点取代</span><span lang="EN-US">x</span><span style="font-family:
宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:&quot;Times New Roman&quot;">再进入下一个循环以外，（这时又要用六种情况来判断，）其余的两种情况就最多进行两次旋转就可以了。</span></p>
<p class="MsoNormal" style="text-indent:17.95pt;mso-char-indent-count:1.71;
mso-char-indent-size:10.45pt"><span lang="EN-US">&nbsp;<o:p>
</o:p>
</span></p>
<p class="MsoNormal" style="text-indent:17.95pt;mso-char-indent-count:1.71;
mso-char-indent-size:10.45pt"><span lang="EN-US">&nbsp;<o:p>
</o:p>
</span></p>
<p class="MsoNormal" style="text-indent:17.95pt;mso-char-indent-count:1.71;
mso-char-indent-size:10.45pt"><span style="font-family:宋体;mso-ascii-font-family:
&quot;Times New Roman&quot;;mso-hansi-font-family:&quot;Times New Roman&quot;">下面是删除的分析。</span></p>
<p class="MsoNormal" style="text-indent:17.95pt;mso-char-indent-count:1.71;
mso-char-indent-size:10.45pt"><span lang="EN-US">&nbsp;<o:p>
</o:p>
</span></p>
<p class="MsoNormal" style="text-indent:17.95pt;mso-char-indent-count:1.71;
mso-char-indent-size:10.45pt"><span lang="EN-US">struct rb_node *ap[48];//</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;">用以保存删除过程中的经过的结点指针</span></p>
<p class="MsoNormal" style="text-indent:17.95pt;mso-char-indent-count:1.71;
mso-char-indent-size:10.45pt"><span lang="EN-US"><span style="mso-spacerun:
yes">&nbsp; </span>int ad[48];//</span><span style="font-family:宋体;mso-ascii-font-family:
&quot;Times New Roman&quot;;mso-hansi-font-family:&quot;Times New Roman&quot;">用以保存删除过程中的</span><span lang="EN-US">ap[i]</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;
mso-hansi-font-family:&quot;Times New Roman&quot;">经过左右子结点</span></p>
<p class="MsoNormal" style="text-indent:17.95pt;mso-char-indent-count:1.71;
mso-char-indent-size:10.45pt"><span lang="EN-US"><span style="mso-spacerun:
yes">&nbsp; </span>int k;//</span><span style="font-family:宋体;mso-ascii-font-family:
&quot;Times New Roman&quot;;mso-hansi-font-family:&quot;Times New Roman&quot;">层数</span></p>
<p class="MsoNormal" style="text-indent:17.95pt;mso-char-indent-count:1.71;
mso-char-indent-size:10.45pt"><span lang="EN-US">&nbsp;<o:p>
</o:p>
</span></p>
<p class="MsoNormal" style="text-indent:17.95pt;mso-char-indent-count:1.71;
mso-char-indent-size:10.45pt"><span lang="EN-US">&nbsp;<o:p>
</o:p>
</span></p>
<p class="MsoNormal" style="text-indent:17.95pt;mso-char-indent-count:1.71;
mso-char-indent-size:10.45pt"><span lang="EN-US">struct rb_node *w, *x, *y, *z;</span></p>
<p class="MsoNormal" style="text-indent:17.95pt;mso-char-indent-count:1.71;
mso-char-indent-size:10.45pt"><span lang="EN-US">//y</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;">就是真正删除的结点，</span><span lang="EN-US">z</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;">是被要求删除的结点（至于这两点的有何不同，在下面会讲</span></p>
<p class="MsoNormal" style="text-indent:17.95pt;mso-char-indent-count:1.71;
mso-char-indent-size:10.45pt"><span lang="EN-US">//</span><span style="font-family:
宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:&quot;Times New Roman&quot;">到）</span></p>
<p class="MsoNormal" style="text-indent:17.95pt;mso-char-indent-count:1.71;
mso-char-indent-size:10.45pt"><span lang="EN-US">//x</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;">是</span><span lang="EN-US">y</span><span style="font-family:
宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:&quot;Times New Roman&quot;">的右子结点</span> 
<span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;">，</span><span lang="EN-US">w</span><span style="font-family:
宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:&quot;Times New Roman&quot;">是</span><span lang="EN-US">y</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;
mso-hansi-font-family:&quot;Times New Roman&quot;">的兄弟结点</span></p>
<p class="MsoNormal" style="text-indent:17.95pt;mso-char-indent-count:1.71;
mso-char-indent-size:10.45pt"><span lang="EN-US"><span style="mso-spacerun:
yes">&nbsp; </span>assert(tree != NULL);//</span><span style="font-family:宋体;
mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:&quot;Times New Roman&quot;">保证确有其红黑树</span></p>
<p class="MsoNormal" style="text-indent:17.95pt;mso-char-indent-count:1.71;
mso-char-indent-size:10.45pt"><span lang="EN-US">&nbsp;<o:p>
</o:p>
</span></p>
<p class="MsoNormal" style="text-indent:17.95pt;mso-char-indent-count:1.71;
mso-char-indent-size:10.45pt"><span lang="EN-US"><span style="mso-spacerun:
yes">&nbsp; </span>ad[0] = 0;</span></p>
<p class="MsoNormal" style="text-indent:17.95pt;mso-char-indent-count:1.71;
mso-char-indent-size:10.45pt"><span lang="EN-US"><span style="mso-spacerun:
yes">&nbsp; </span>ap[0] = (struct rb_node *) &amp;tree-&gt;root;</span></p>
<p class="MsoNormal" style="text-indent:17.95pt;mso-char-indent-count:1.71;
mso-char-indent-size:10.45pt"><span lang="EN-US"><span style="mso-spacerun:
yes">&nbsp; </span>k = 1;</span></p>
<p class="MsoNormal" style="text-indent:17.95pt;mso-char-indent-count:1.71;
mso-char-indent-size:10.45pt"><span lang="EN-US">&nbsp;<o:p>
</o:p>
</span></p>
<p class="MsoNormal" style="text-indent:17.95pt;mso-char-indent-count:1.71;
mso-char-indent-size:10.45pt"><span lang="EN-US"><span style="mso-spacerun:
yes">&nbsp; </span>z = tree-&gt;root;//</span><span style="font-family:宋体;
mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:&quot;Times New Roman&quot;">先从根结点找</span></p>
<p class="MsoNormal" style="text-indent:17.95pt;mso-char-indent-count:1.71;
mso-char-indent-size:10.45pt"><span lang="EN-US">&nbsp;<o:p>
</o:p>
</span></p>
<p class="MsoNormal" style="text-indent:17.95pt;mso-char-indent-count:1.71;
mso-char-indent-size:10.45pt"><span lang="EN-US">for (;;) {</span></p>
<p class="MsoNormal" style="text-indent:17.95pt;mso-char-indent-count:1.71;
mso-char-indent-size:10.45pt"><span lang="EN-US"><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp; </span>int dir;</span></p>
<p class="MsoNormal" style="text-indent:17.95pt;mso-char-indent-count:1.71;
mso-char-indent-size:10.45pt"><span lang="EN-US">&nbsp;<o:p>
</o:p>
</span></p>
<p class="MsoNormal" style="text-indent:17.95pt;mso-char-indent-count:1.71;
mso-char-indent-size:10.45pt"><span lang="EN-US"><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp; </span>if (z == NULL)</span></p>
<p class="MsoNormal" style="text-indent:17.95pt;mso-char-indent-count:1.71;
mso-char-indent-size:10.45pt"><span lang="EN-US"><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>return 0;//</span><span style="font-family:宋体;mso-ascii-font-family:
&quot;Times New Roman&quot;;mso-hansi-font-family:&quot;Times New Roman&quot;">如没有发现这样要求的结点</span> 
<span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;">，就返回</span></p>
<p class="MsoNormal" style="text-indent:17.95pt;mso-char-indent-count:1.71;
mso-char-indent-size:10.45pt"><span lang="EN-US">&nbsp;<o:p>
</o:p>
</span></p>
<p class="MsoNormal" style="text-indent:17.95pt;mso-char-indent-count:1.71;
mso-char-indent-size:10.45pt"><span lang="EN-US"><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp; </span>if (item == z-&gt;data)//</span><span style="font-family:宋体;
mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:&quot;Times New Roman&quot;">找到了</span></p>
<p class="MsoNormal" style="text-indent:17.95pt;mso-char-indent-count:1.71;
mso-char-indent-size:10.45pt"><span lang="EN-US"><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>break;</span></p>
<p class="MsoNormal" style="text-indent:17.95pt;mso-char-indent-count:1.71;
mso-char-indent-size:10.45pt"><span lang="EN-US"><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp; </span>dir = item &gt; z-&gt;data;//</span><spa