红黑数算法及演示源代码

<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">int rb_insert(struct rb_tree 
*tree, int item)</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 lang="EN-US"><span style="mso-spacerun:
yes">&nbsp; </span>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 ak;//</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>struct rb_node *x, *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">&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>assert(tree != 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; </span>if (tree-&gt;root == 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; </span>tree-&gt;root = new_node(tree, item, 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"><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp; </span>return tree-&gt;root != 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; </span>}//</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>ak = 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>x = 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"><span style="mso-spacerun:
yes">&nbsp; </span>for (;;) {</span></p>
<p class="MsoNormal" style="margin-left:1.7gd;text-indent:-105.0pt;mso-char-indent-count:
-10.0;mso-char-indent-size:10.5pt"><span lang="EN-US"><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp; </span>int dir;//</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">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 lang="EN-US">1</span></p>
<p class="MsoNormal" style="margin-left:1.7gd;text-indent:-105.0pt;mso-char-indent-count:
-10.0;mso-char-indent-size:10.5pt"><span lang="EN-US"><span style="mso-spacerun:
yes">&nbsp;&nbsp; </span>//</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 == x-&gt;data)</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 2;//</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; </span>dir = item &gt; x-&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><span lang="EN-US">dir</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>ap[ak] = x;</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>ad[ak++] = dir;//</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; </span>y = x-&gt;link[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"><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp; </span>if (y == 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>x = x-&gt;link[dir] = new_node(tree, 
item, RB_RED);</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>if (x == 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">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></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>}</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>x = 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>}</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">for(;;)</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">linux</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">task_idle(){for(;;);}</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 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 = x-&gt;link[dir] = 
new_node(tree, item, RB_RED);</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: