📄
字号:
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=gb2312">
<meta name="GENERATOR" content="Microsoft FrontPage 4.0">
<meta name="ProgId" content="FrontPage.Editor.Document">
<title>红黑树解读</title>
</head>
<body>
<p class="MsoNormal" align="center" style="text-align:center"><span style="font-size:16.0pt;mso-bidi-font-size:12.0pt;font-family:幼圆;mso-ascii-font-family:
"Times New Roman";letter-spacing:4.0pt">红黑树解读</span><span lang="EN-US" style="font-size:16.0pt;mso-bidi-font-size:12.0pt;mso-fareast-font-family:幼圆;
letter-spacing:4.0pt"><o:p>
</o:p>
</span></p>
<p class="MsoNormal"><span lang="EN-US"> <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:
"Times New Roman";mso-hansi-font-family:"Times New Roman"">在</span><span lang="EN-US">linux</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">的内核中在数据的组织上已经在许多的地方用到了红黑树，如在内存分配当中，对内存的管理就要用到。很多网友在网上都问这是一个什么样的数据结构。现在，我的这一篇文章就是解决大家这个问题的。</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"> <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:
"Times New Roman";mso-hansi-font-family:"Times New Roman"">红黑树是新进才出现的一种平衡二叉树。它有几个基本的要求：</span></p>
<p class="MsoNormal" style="margin-left:35.95pt;text-indent:-18.0pt;mso-list:
l0 level1 lfo1;tab-stops:list 35.95pt"><span lang="EN-US">1、<span style="font:7.0pt "Times New Roman"">
</span></span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">每一个树中的结点必须有颜色，且颜色只能是红色或者黑色。</span></p>
<p class="MsoNormal" style="margin-left:35.95pt;text-indent:-18.0pt;mso-list:
l0 level1 lfo1;tab-stops:list 35.95pt"><span lang="EN-US">2、<span style="font:7.0pt "Times New Roman"">
</span></span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">每一个外部结点必须是黑色。</span></p>
<p class="MsoNormal" style="margin-left:35.95pt;text-indent:-18.0pt;mso-list:
l0 level1 lfo1;tab-stops:list 35.95pt"><span lang="EN-US">3、<span style="font:7.0pt "Times New Roman"">
</span></span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">如果一个结点是红色，那么它的两个子结点必须是黑色。</span></p>
<p class="MsoNormal" style="margin-left:35.95pt;text-indent:-18.0pt;mso-list:
l0 level1 lfo1;tab-stops:list 35.95pt"><span lang="EN-US">4、<span style="font:7.0pt "Times New Roman"">
</span></span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">从每一个父结点到它的所有外部子结点经过的黑色子结点必须相同。</span></p>
<p class="MsoNormal" style="margin-left:17.95pt"><span lang="EN-US"><!--[if gte vml 1]><v:shapetype
id="_x0000_t75" coordsize="21600,21600" o:spt="75" o:preferrelative="t"
path="m@4@5l@4@11@9@11@9@5xe" filled="f" stroked="f">
<v:stroke joinstyle="miter"/>
<v:formulas>
<v:f eqn="if lineDrawn pixelLineWidth 0"/>
<v:f eqn="sum @0 1 0"/>
<v:f eqn="sum 0 0 @1"/>
<v:f eqn="prod @2 1 2"/>
<v:f eqn="prod @3 21600 pixelWidth"/>
<v:f eqn="prod @3 21600 pixelHeight"/>
<v:f eqn="sum @0 0 1"/>
<v:f eqn="prod @6 1 2"/>
<v:f eqn="prod @7 21600 pixelWidth"/>
<v:f eqn="sum @8 21600 0"/>
<v:f eqn="prod @7 21600 pixelHeight"/>
<v:f eqn="sum @10 21600 0"/>
</v:formulas>
<v:path o:extrusionok="f" gradientshapeok="t" o:connecttype="rect"/>
<o:lock v:ext="edit" aspectratio="t"/>
</v:shapetype><v:shape id="_x0000_i1025" type="#_x0000_t75" style='width:414.75pt;
height:200.25pt'>
<v:imagedata src="file:///E:/DOCUME~1/ADMINI~1.000/LOCALS~1/Temp/msoclip1/01/clip_image001.png"
o:title="display"/>
</v:shape><![endif]-->
<img src="红黑1.jpg" v:shapes="_x0000_i1025" width="553" height="267"></span></p>
<p class="MsoNormal" style="margin-left:17.95pt"><span lang="EN-US"> <o:p>
</o:p>
</span></p>
<p class="MsoNormal" style="margin-left:17.95pt"><span style="font-family:宋体;
mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"">图</span><span lang="EN-US">1.1</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">就是一个合法红黑树，而图</span><span lang="EN-US">1.2</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">就不是。</span></p>
<p class="MsoNormal" style="margin-left:17.95pt"><span lang="EN-US"> <o:p>
</o:p>
</span></p>
<p class="MsoNormal" style="margin-left:17.95pt"><span style="font-family:宋体;
mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"">红黑树之所以是一个好的平衡二叉树可以从以下的一个定理得到。</span></p>
<p class="MsoNormal" style="margin-left:17.95pt"><span lang="EN-US"> <o:p>
</o:p>
</span></p>
<p class="MsoNormal" style="margin-left:17.95pt"><span style="font-family:宋体;
mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"">定理：</span></p>
<p class="MsoNormal" style="margin-left:17.95pt"><span style="mso-spacerun: yes" lang="EN-US">
</span><span style="font-family:宋体;
mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"">如果一个红黑树有</span><span lang="EN-US">n</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">个结点，那它的高度最多是</span><span lang="EN-US">2lg(n+1)</span></p>
<p class="MsoNormal" style="margin-left:17.95pt"><span lang="EN-US"> <o:p>
</o:p>
</span></p>
<p class="MsoNormal" style="margin-left:17.95pt"><span style="font-family:宋体;
mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"">证明：</span></p>
<p class="MsoNormal" style="margin-left:17.95pt"><span style="mso-spacerun: yes" lang="EN-US">
</span><span style="font-family:宋体;
mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"">我们先定义一个黑高度</span><span lang="EN-US">bh</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">，这表明根结点到一个外部结点的路径上黑结点的个数。（对图</span><span lang="EN-US">1.1</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">的根结点而言，它的黑高度就是</span><span lang="EN-US">2</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">）先证明对一个有</span><span lang="EN-US">n</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">个结点的红黑树的黑高度</span><span lang="EN-US">n>=2<sup>bh</sup>-1</span></p>
<p class="MsoNormal" style="margin-left:17.95pt"><span style="mso-spacerun: yes" lang="EN-US">
</span><span style="font-family:宋体;
mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"">用归纳方法证明。</span></p>
<p class="MsoNormal" style="margin-left:17.95pt"><span style="mso-spacerun: yes" lang="EN-US">
</span><span style="font-family:宋体;
mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"">如果</span><span lang="EN-US">bh=0
</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">时结点数是</span><span lang="EN-US">1</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">，</span><span lang="EN-US">1>=2<sup>0</sup>-1</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">成立</span></p>
<p class="MsoNormal" style="margin-left:17.95pt"><span lang="EN-US"> <o:p>
</o:p>
</span></p>
<p class="MsoNormal" style="margin-left:17.95pt"><span style="mso-spacerun: yes" lang="EN-US"> </span><span style="font-family:宋体;
mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"">并假定在</span><span lang="EN-US">bh</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">以下时也成立</span><span lang="EN-US">,n>=2<sup>bh</sup>-1<sup><o:p>
</o:p>
</sup></span></p>
<p class="MsoNormal" style="margin-left:17.95pt"><span style="font-family:宋体;
mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"">当高度是</span><span lang="EN-US">bh+1</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">时，这时红黑树的结点数是由两个黑高度分别为</span><span lang="EN-US">bh</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">高度的子树所组成，（不论根结点的子结点是黑色还是红色，因为红色的话比黑色的子树可能的结点数还要多）这时两个子树的结点数和大于</span><span lang="EN-US">2<sup>bh</sup>-1+2<sup>bh</sup>-1</span><span style="font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"">，然后加上根结点的一个，就可以得到</span><span lang="EN-US">2<sup>bh+1</sup>-1</span></p>
<p class="MsoNormal" style="margin-left:17.95pt"><span lang="EN-US"> <o:p>
</o:p>
</span></p>
<p class="MsoNormal" style="margin-left:17.95pt"><span style="font-family:宋体;
mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"">这个定理的逆就是</span><span lang="EN-US">bh<=lg(n+1)</span></p>
<p class="MsoNormal" style="margin-left:17.95pt"><span style="font-family:宋体;
mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"">因为黑高度至少是红黑树一半，（红色结点的子结点必须是黑色）。所以整个红黑树的高度就是</span><span lang="EN-US">h<=2lg(n+1)</span></p>
<p class="MsoNormal" style="margin-left:17.95pt"><span lang="EN-US"> <o:p>
</o:p>
</span></p>
<p class="MsoNormal" style="margin-left:17.95pt"><span style="font-family:宋体;
mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"">这就保证了红黑树的查找的复杂度是</span><span lang="EN-US">O</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">（</span><span lang="EN-US">lgn</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">），这是一个很好的平衡二叉树。</span></p>
<p class="MsoNormal" style="margin-left:17.95pt"><span lang="EN-US"> <o:p>
</o:p>
</span></p>
<p class="MsoNormal" style="margin-left:17.95pt"><span style="font-family:宋体;
mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"">下面我要结合真正的源代码来分析红黑树在添加与删除时用的算法。</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"> <o:p>
</o:p>
</span></p>
<p class="MsoBodyTextIndent"><span style="font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman"">在这当中的添加与删除本身都没有什么难度，但为了满足红黑树的四个要求，作一些调整则要详细的讲说。</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"> <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:
"Times New Roman";mso-hansi-font-family:"Times New Roman"">下面是添加的例子的开始部分的源代码</span></p>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -