最短路径的求解算法_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
最短路径的求解算法
上传于||暂无简介
阅读已结束，如果下载本文需要使用5下载券
想免费下载本文？
你可能喜欢数据结构（3）
&原文地址：原文作者：张鹏飞
& 只想说：温故而知新，可以为师矣。我大二的《数据结构》是由申老师讲的，那时候
不怎么明白，估计太理论化了(ps：或许是因为我睡觉了)；今天把老王的2011年课件又
看了一遍，给大二的孩子们又讲了一遍，随手谷歌了N多资料，算是彻底搞懂了最短路
径问题。请读者尽情享用……
&&&&&&& 我坚信：没有不好的学生，只有垃圾的教育。不过没有人理所当然的对你好，
所以要学会感恩。
一.问题引入
&&&&&&& 问题：从某顶点出发，沿图的边到达另一顶点所经过的路径中，各边上权值之
和最小的一条路径——最短路径。解决最短路的问题有以下算法，Dijkstra算法，
Bellman-Ford算法，Floyd算法和SPFA算法，另外还有著名的启发式搜索算法A*，不过
A*准备单独出一篇，其中Floyd算法可以求解任意两点间的最短路径的长度。笔者认为
任意一个最短路算法都是基于这样一个事实：从任意节点A到任意节点B的最短路径不外
乎2种可能，1是直接从A到B，2是从A经过若干个节点到B。
二.Dijkstra算法
&&&&&&& 该算法在《数据结构》课本里是以贪心的形式讲解的，不过在《运筹学》教材
里被编排在动态规划章节，建议读者两篇都看看。
&&&&&&&&&&&
&&&&&&& 观察右边表格发现除最后一个节点外其他均已经求出最短路径。
&&&&&&& (1)&& 迪杰斯特拉(Dijkstra)算法按路径长度(看下面表格的最后一行，就是
next点)递增次序产生最短路径。先把V分成两组：
S：已求出最短路径的顶点的集合
V-S=T：尚未确定最短路径的顶点集合
&&&&&&& 将T中顶点按最短路径递增的次序加入到S中，依据：可以证明V0到T中顶点Vk
的最短路径，或是从V0到Vk的直接路径的权值或是从V0经S中顶点到Vk的路径权值之
和（反证法可证，说实话，真不明白哦）。
&&&&&&& (2)&& 求最短路径步骤
初使时令 S={V0},T={其余顶点}，T中顶点对应的距离值，&若存在&V0,Vi&，为&V0,Vi&弧上的权值（和ＳＰＦＡ初始化方式不同），若不存在&V0,Vi&，为Inf。从T中选取一个其距离值为最小的顶点W(贪心体现在此处)，加入S(注意不是直接从S集合中选取，理解这个对于理解vis数组的作用至关重要)，对T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的距离值比不加W的路径要短，则修改此距离值（上面两个并列for循环，使用最小点更新）。重复上述步骤，直到S中包含所有顶点，即S=V为止（说明最外层是除起点外的遍历）。
&&&&&&& 下面是上图的求解过程，按列来看，第一列是初始化过程，最后一行是每次求得的next点。
&&&&&&&&&&&
&&&&&&& (3)&& 问题：Dijkstar能否处理负权边？(下面的解释引自网上某大虾)
&&&&&&&&&&&& 答案是不能，这与贪心选择性质有关(ps：貌似还是动态规划啊，晕
了)，每次都找一个距源点最近的点（dmin），然后将该距离定为这个点到源点的最短
路径；但如果存在负权边，那就有可能先通过并不是距源点最近的一个次优点
（dmin'），再通过这个负权边L(L&0)，使得路径之和更小（dmin'+L&dmin）,则
dmin'+L成为最短路径，并不是dmin，这样dijkstra就被囧掉了。比如n=3，邻接矩
用dijkstra求得d[1，2]=3，事实上d[1，2]=2，就是通过了1-3-2使得路径减小。不知
道讲得清楚不清楚。
二.Floyd算法
&&&&&&& 参考了南阳理工牛帅(目前在新浪)的博客。
&&&&&&& Floyd算法的基本思想如下：从任意节点A到任意节点B的最短路径不外乎2种可
能，1是直接从A到B，2是从A经过若干个节点到B，所以，我们假设dist(AB)为节点A到
节点B的最短路径的距离，对于每一个节点K，我们检查dist(AK) + dist(KB)&
& dist(AB)是否成立，如果成立，证明从A到K再到B的路径比A直接到B的路径短，我们
便设置 dist(AB) = dist(AK) + dist(KB)，这样一来，当我们遍历完所有节点K，
dist(AB)中记录的便是A到B的最短路径的距离。
&&&&&&& 很简单吧，代码看起来可能像下面这样：
for (int i=0; i&n; ++i) {
for (int j=0; j&n; ++j) {
for (int k=0; k&n; ++k) {
if (dist[i][k] + dist[k][j] & dist[i][j] ) {
dist[i][j] = dist[i][k] + dist[k][j];
&&&&&&& 但是这里我们要注意循环的嵌套顺序，如果把检查所有节点K放在最内层，那
么结果将是不正确的，为什么呢？因为这样便过早的把i到j的最短路径确定下来了，而
当后面存在更短的路径时，已经不再会更新了。
&&&&&&& 让我们来看一个例子，看下图：
&&&&&&& 图中红色的数字代表边的权重。如果我们在最内层检查所有节点K，那么对于
A-&B，我们只能发现一条路径，就是A-&B，路径距离为9，而这显然是不正确的，真实
的最短路径是A-&D-&C-&B，路径距离为6。造成错误的原因就是我们把检查所有节点K放
在最内层，造成过早的把A到B的最短路径确定下来了，当确定A-&B的最短路径时
dist(AC)尚未被计算。所以，我们需要改写循环顺序，如下：
&&&&&&& ps：个人觉得，这和银行家算法判断安全状态(每种资源去测试所有线程)，树
状数组更新(更新所有相关项)一样的思想。
for (int k=0; k&n; ++k) {
for (int i=0; i&n; ++i) {
for (int j=0; j&n; ++j) {
实际中为防止溢出，往往需要选判断 dist[i][k]和dist[k][j
都不是Inf ，只要一个是Inf，那么就肯定不必更新。
if (dist[i][k] + dist[k][j] & dist[i][j] ) {
dist[i][j] = dist[i][k] + dist[k][j];
&&&&&&& 如果还是看不懂，那就用草稿纸模拟一遍，之后你就会豁然开朗。半个小时足
矣（早知道的话会节省很多个半小时了。。）
&&&&&& 再来看路径保存问题：
void floyd() {
for(int i=1; i&= i++){
for(int j=1; j&= j++){
if(map[i][j]==Inf){
path[i][j] = -1;//表示
i -& j 不通
path[i][j] =// 表示 i -& j 前驱为 i
for(int k=1; k&=n; k++) {
for(int i=1; i&=n; i++) {
for(int j=1; j&=n; j++) {
if(!(dist[i][k]==Inf||dist[k][j]==Inf)&&dist[i][j] & dist[i][k] + dist[k][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
path[i][k] =
path[i][j] = path[k][j];
void printPath(int from, int to) {
* 这是倒序输出，若想正序可放入栈中，然后输出。
* 这样的输出为什么正确呢？个人认为用到了最优子结构性质，
* 即最短路径的子路径仍然是最短路径
while(path[from][to]!=from) {
System.out.print(path[from][to] +& &);
to = path[from][to];
&&&&&&& 《数据结构》课本上的那种方式我现在还是不想看，看着不舒服……
&&&&&&& Floyd算法另一种理解DP，为理论爱好者准备的，上面这个形式的算法其实是
Floyd算法的精简版，而真正的Floyd算法是一种基于DP(Dynamic Programming)的最短
路径算法。设图G中n 个顶点的编号为1到n。令c [i, j, k]表示从i 到j 的最短路径的
长度，其中k 表示该路径中的最大顶点，也就是说c[i,j,k]这条最短路径所通过的中间
顶点最大不超过k。因此，如果G中包含边&i, j&，则c[i, j, 0] =边&i, j& 的长度；
若i= j ，则c[i,j,0]=0；如果G中不包含边&i, j&，则c (i, j, 0)= +∞。c[i, j, n]
&则是从i 到j 的最短路径的长度。对于任意的k&0，通过分析可以得到：中间顶点不超
过k 的i 到j 的最短路径有两种可能：该路径含或不含中间顶点k。若不含，则该路径
长度应为c[i, j, k-1]，否则长度为 c[i, k, k-1] +c [k, j, k-1]。c[i, j, k]可取
两者中的最小值。状态转移方程：c[i, j, k]=min{c[i, j, k-1], c [i, k, k-1]+c
&[k, j, k-1]}，k＞0。这样，问题便具有了最优子结构性质，可以用动态规划方法来
&&&&&&& 看另一个DP(直接引用王老师课件)
&&&&&&&&&&&&&&&&&&&&&&&
&&&&&&& 说了这么多，相信读者已经跃跃欲试了，咱们看一道例题，以ZOJ 1092为
例：给你一组国家和国家间的部分货币汇率兑换表，问你是否存在一种方式，从一种货
币出发，经过一系列的货币兑换，最后返回该货币时大于出发时的数值(ps：这就是所
谓的投机倒把吧)，下面是一组输入。
3&&& //国家数&
USDollar& //国家名&
BritishPound&
FrenchFranc&
&& 3&&& //货币兑换数&
USDollar 0.5 BritishPound& //部分货币汇率兑换表&
BritishPound 10.0 FrenchFranc&
FrenchFranc 0.21 USDollar
&&&&&&& 月赛做的题，不过当时用的思路是求强连通分量(ps：明明说的，那时我和华
杰感觉好有道理)，也没做出来，现在知道了直接floyd算法就ok了。
&&&&&&& 思路分析：输入的时候可以采用Map&String,Integer& map = new
&HashMap&String,Integer&()主要是为了获得再次包含汇率输入时候的下标以建图(感
觉自己写的好拗口)，或者第一次直接存入String数组str，再次输入的时候每次遍历
str数组，若是equals那么就把str的下标赋值给该币种建图。下面就是floyd算法啦，
初始化其它点为-1，对角线为1，采用乘法更新求最大值。
三.Bellman-Ford算法
&&&&&&& 为了能够求解边上带有负值的单源最短路径问题，Bellman(贝尔曼，动态规划
提出者)和Ford(福特)提出了从源点逐次绕过其他顶点，以缩短到达终点的最短路径长
度的方法。&Bellman-ford算法是求含负权图的单源最短路径算法，效率很低，但代码
很容易写。即进行不停地松弛，每次松弛把每条边都更新一下，若n-1次松弛后还能更
新，则说明图中有负环，无法得出结果，否则就成功完成。Bellman-ford算法有一个小
优化：每次松弛先设一个flag，初值为FALSE，若有边更新则赋值为TRUE，最终如果还
是FALSE则直接成功退出。Bellman-ford算法浪费了许多时间做无必要的松弛，所以
SPFA算法用队列进行了优化，效果十分显著，高效难以想象。SPFA还有SLF，LLL，滚动
数组等优化。
&&&&&&& 关于SPFA，请看我这一篇
&&&&&&&&递推公式(求顶点u到源点v的最短路径)：
&&&&&&&& dist 1 [u] = Edge[v][u]
&&&&&&&& dist k [u] = min{ dist k-1 [u], min{ dist k-1 [j] + Edge[j][u] } }, j=0,1,…,n-1,j≠u
&&&&&&&& Dijkstra算法和Bellman算法思想有很大的区别：Dijkstra算法在求解过程
中，源点到集合S内各顶点的最短路径一旦求出，则之后不变了，修改& 的仅仅是源点
到T集合中各顶点的最短路径长度。Bellman算法在求解过程中，每次循环都要修改所有
顶点的dist[ ]，也就是说源点到各顶点最短路径长度一直要到Bellman算法结束才确定
&&&&&&&&算法适用条件
1.单源最短路径(从源点s到其它所有顶点v)有向图&无向图(无向图可以看作(u,v),(v,u)同属于边集E的有向图)边权可正可负(如有负权回路输出错误提示)差分约束系统(至今貌似只看过一道题)
&&&&&&& Bellman-Ford算法描述：
初始化：将除源点外的所有顶点的最短距离估计值 d[v] ←+∞, d[s] ←0迭代求解：反复对边集E中的每条边进行松弛操作，使得顶点集V中的每个顶点v的最短距离估计值逐步逼近其最短距离；（运行|v|-1次，看下面的描述性证明(当做树)）检验负权回路：判断边集E中的每一条边的两个端点是否收敛。如果存在未收敛的顶点，则算法返回false，表明问题无解；否则算法返回true，并且从源点可达的顶点v的最短距离保存在d[v]中
&&&&&&&&描述性证明：(这个解释很好)
&&&&&&& 首先指出，图的任意一条最短路径既不能包含负权回路，也不会包含正权回
路，因此它最多包含|v|-1条边。
其次，从源点s可达的所有顶点如果 存在最短路径，则这些最短路径构成一个以s为根
的最短路径树。Bellman-Ford算法的迭代松弛操作，实际上就是按顶点距离s的层次，
逐层生成这棵最短路径树的过程。
在对每条边进行1遍松弛的时候，生成了从s出发，层次至多为1的那些树枝。也就是
说，找到了与s至多有1条边相联的那些顶点的最短路径；对每条边进行第2遍松弛的时
候，生成了第2层次的树枝，就是说找到了经过2条边相连的那些顶点的最短路径……。
因为最短路径最多只包含|v|-1条边，所以，只需要循环|v|-1 次。
每实施一次松弛操作，最短路径树上就会有一层顶点达到其最短距离，此后这层顶点的
最短距离值就会一直保持不变，不再受后续松弛操作的影响。（但是，每次还要判断松
弛，这里浪费了大量的时间，这就是Bellman-Ford算法效率底下的原因，也正是SPFA优
化的所在）。
，如图(没找到画图工具的射线)，若是B和C的最短路径
不更新，那么点D的最短路径肯定也无法更新，这就是优化所在。
如果没有负权回路，由于最短路径树的高度最多只能是|v|-1，所以最多经过|v|-1遍松
弛操作后，所有从s可达的顶点必将求出最短距离。如果 d[v]仍保持 +∞，则表明从s
到v不可达。
如果有负权回路，那么第 |v|-1 遍松弛操作仍然会成功，这时，负权回路上的顶点不
&&&&&&&&&&&&参考来源：
&&&&&&& 问题：Bellman-Ford算法是否一定要循环n-1次么？未必！其实只要在某次循
环过程中，考虑每条边后，都没能改变当前源点到所有顶点的最短路径长度，那么
Bellman-Ford算法就可以提前结束了(开篇提出的小优化就是这个)。
&&&&&&& 上代码(来自牛帅)
#include&iostream&
#include&cstdio&
using namespace
#define MAX 0x3f3f3f3f
#define N 1010
int nodenum, edgenum, //点，边，起点
typedef struct Edge //边
Edge edge[N];
int dis[N], pre[N];
bool Bellman_Ford()
for(int i = 1; i &= ++i) //初始化
dis[i] = (i == original ? 0 : MAX);
for(int i = 1; i &= nodenum - 1; ++i)
for(int j = 1; j &= ++j)
if(dis[edge[j].v] & dis[edge[j].u] + edge[j].cost) //松弛（顺序一定不能反~）
dis[edge[j].v] = dis[edge[j].u] + edge[j].
pre[edge[j].v] = edge[j].u;
bool flag = 1; //判断是否含有负权回路
for(int i = 1; i &= ++i)
if(dis[edge[i].v] & dis[edge[i].u] + edge[i].cost)
void print_path(int root) //打印最短路的路径（反向）
while(root != pre[root]) //前驱
printf(&%d--&&, root);
root = pre[root];
if(root == pre[root])
printf(&%d\n&, root);
int main()
scanf(&%d%d%d&, &nodenum, &edgenum, &original);
pre[original] =
for(int i = 1; i &= ++i)
scanf(&%d%d%d&, &edge[i].u, &edge[i].v, &edge[i].cost);
if(Bellman_Ford())
for(int i = 1; i &= ++i) //每个点最短路
printf(&%d\n&, dis[i]);
printf(&Path:&);
print_path(i);
printf(&have negative circle\n&);
四.SPFA算法
&&&&&&& 用一个队列来进行维护。初始时将源加入队列。每次从队列中取出一个元素，
并对所有与他相邻的点进行松弛，若某个相邻的点松弛成功，则将其入队。直到队列为
空时算法结束；这个算法，简单的说就是队列优化的bellman-ford，利用了每个点不会
更新次数太多的特点发明的此算法(看我上面那个图，只有相邻点更新了，该点才有可
能更新) 。
&&&&&&&&&代码参见&：&
&&&&&&& 整理该篇博文的时候，一哥们发布网站到我们群，网站很精美，一牛神
(acmol)使用fork炸弹，结果服务器立马挂啦，更改后又挂啦，目测目前无限挂中。。。
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：14237次
排名：千里之外
原创：48篇
(15)(3)(4)(14)(18)(1)最短路径算法与应用中的问题分析(史上最全路径算法总结)_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
最短路径算法与应用中的问题分析(史上最全路径算法总结)
上传于||暂无简介
阅读已结束，如果下载本文需要使用1下载券
想免费下载本文？
下载文档到电脑，查找使用更方便
还剩7页未读，继续阅读
你可能喜欢1491人阅读
《算法导论》（64）
红黑树的定义：红黑树是一种较为“平衡的”二叉查找树，其每个结点上增加了一个储存颜色的位置，可以是红也可以是黑色的，并且有父亲结点。基本操作时间为O(lgn).
红黑树的性质：1)每个结点或是红的，或是黑的。2)根结点是黑的。&3)每个叶结点(NIL)是黑的。&4)若一个结点是红的，则它的两个儿子都是黑的。5)对每个结点，从该结点到其子孙结点的所有路径上的黑色结点数目相同。
黑高度：从某个结点x出发(不包括该结点)到达一个叶结点的任意一条路径上，黑色结点的个数称为该结点x的黑高度，用bh(x)表示。
引理13.1 一棵有n个内结点的红黑树的高度至多为2lg(n+1).
13.1-1 使用图13-1a的格式，画出在关键字集合{1,2,....,15}上高度为3的完全二叉查找树。以三种不同方式，向图中加入NIL叶结点并对各结点着色，使所得的红黑树的黑高度分别为2,3,4.
图1表示黑度为4的红黑树，图2表示黑度为3的红黑树，图3表示黑度为2的红黑树。
13.1-2对图13-1中的红黑树，画出调用TREE-INSERT插入关键字36后的结果。结果插入的结点被标为红色，所得的树是否还是一棵红黑树？如果该结点被标为黑色呢？
标为红色后，不是红黑树，不符合性质4. 标为黑色后，不是红黑树，不符合性质5.第3节学习插入函数后，可以知道每插入一个红色结点，可以通过调整使之成为一棵红黑树。
13.1-3 定义松弛红黑树为满足红黑性质1,3,4,5的二叉查找树。换言之，根部可以是红色或是黑色。考虑一棵根是红色的松弛红黑树T。如果将T的根部标为黑色而其他都不变，则所得到的是否还是一棵红黑树？
13.1-4假设将一棵红黑树的每一个红结点“吸收”到它的黑色父结点中，来让红结点的子女变成黑色父结点的子女(忽略关键字的变化)。当一个黑结点的所有红色子女都被吸收后，其可能的度是多少？此结果树的叶子深度怎么样？
度为2时，是左右孩子结点已经都是黑色。度为3时，左或者右孩子结点是红色。 度为4时，左右孩子结点都是红色。 结果树叶子深度都相同。
以下13.1-5~7 都用到了红黑树一个特别的结构，那就是从根结点开始，一层黑一层红，颜色交替，构成了一棵拥有红色结点最多的红黑树。
13.1-5 证明：在一棵红黑树中，从某结点x到其后代叶结点的所有简单路径中，最长的一条是最短一条的至多两倍。
最短：此路径上全是黑色结点。最长：此路径上红黑结点交替出现(红色结点数目=黑色结点数目)，又因为不管到最长路径还是到最短路径，黑高(黑色结点数目)都相等。最长：最短=(红+黑)：黑=2:1:由此得出论点。
13.1-6 在一棵黑高度为k的红黑树中，内结点最多可能有多少个？最少可能有多少个？
根据引理13.1 至少包含2^k-1个内部结点。至多包含2^(2k)-1个内部结点。(最多就是红黑结点交替出现的情况)
13.1-7 请描述出一棵在n个关键字上构造出来的红黑树，使其中红的内部结点数与黑的内部结点数比值最大。这个比值是多少？具有最小可能比例的树又是怎么样？此比值是多少？
最小可能比值就是所有结点都是黑色，比值为0。 最大可能是红黑结点交替出现，并且最底层是全部是红色结点，比值是2:1.
旋转分为：左旋和右旋。
左旋：在某个结点x做左旋时，它的右孩子非空。 右旋：在某个结点x做右旋时，它的左孩子非空。
左旋代码如下：
struct Tree*root=NULL;
void LEFT_ROTATE(struct Tree*T,struct Tree*x)
{//左旋转：分三个步骤①②③来叙述旋转代码的。
 struct Tree*y=x-&//设置y结点。
 x-&right=y-&//本行代码以及下面的if结构表达的是“y的左孩子成为x的右孩子”。①
 if(y!=NULL&&y-&left!=NULL)
       y-&left-&parent=x;
 y-&parent=x-&//本行代码以及下面的if-else结构表达的过程是“y成为该子树新的根”。②
 if(x-&parent==NULL)
       root=y;
 else if(x==x-&parent-&left)
       x-&parent-&left=y;
 else x-&parent-&right=y;
 y-&left=x;//本行代码以及下面一行都表达了“x成为y的左孩子”。③
 x-&parent=y;
13.2-1 写出RIGHT-ROTATE的伪代码。
只需将书中的代码中的right变为left,而left变为right即可。
13.2-2 证明：在一棵有n个结点的二叉查找树中，刚好有n-1种可能的旋转。
因为n个结点有n-1条边，每条边都可以(左或右)旋转，所以有n-1种可能的旋转。
13.2-3设在图13-2的左边一棵树中，a,b,c分别为子树α,β,γ中的任意结点。如果将结点x左旋，则a,b,c深度如何变化？
α上升1层,β不变，γ下降1层。
13.2-4 证明：任何一棵含n个结点的二叉查找树，可以通过O(n)次旋转，转变为另一棵含n个结点的二叉查找树。
每次右(左)旋转，都会使最右(左)链上多一个结点，经过任意n-1次右(左)旋转,任意右(左)总会变成一个单链表。所以任意二叉查找树都能经过O(n)次旋转转换成任意二叉查找树。
13.2-5 如果能够使用一系列的RIGHT-ROTATE调用来把一个二叉查找树T1变为二叉查找树T2，则说T1可以右转成T2。请给出一个两棵树的例子，其中T1不能右转成T2.然后证明如果T1可以右转成T2，则它可以使用O(n^2)次RIGHT-ROTATE调用来右转。
第二问不太懂。
红黑树的插入函数只需要把第12章的二叉查找树稍微修改一下即可实现，但是由于插入时需要保持红黑树性质，所以我们引入RB_INSERT_FIXUP函数，这才是插入函数关键
代码如下：
void RB_INSERT_INSERT_FIXUP(struct Tree*T,struct Tree*z)
   while (z-&parent-&color==RED)
   {
    if (z-&parent==z-&parent-&parent-&left)
    {
     struct Tree*y=z-&parent-&parent-&//叔结点
     if (y-&color==RED)//情况一：叔结点为红色
     {//给p1,y,p2着色以保持性质5。并且解决了z的父结点和z都是红色结点问题
      z-&parent-&color=BLACK;
      y-&color=BLACK;
      z-&parent-&parent-&color=RED;
      z=z-&parent-&//把z的祖父结点当成新结点z进入下一次循环
     }
     else
     {
      if (z==z-&parent-&right)//情况二：检查z是否是一个右孩子且叔结点为黑色，前提是p1结点不是叶子结点
      {//使用一个左旋让情况2转变为情况3
       z=z-&
       LEFT_ROTATE(T,z);//由于进入if语句后可知旋转结点不可能是叶子结点，这样就不用判断z是否是叶子结点了。
      }
               z-&parent-&color=BLACK;//情况三：是z是一个左孩子且叔结点为黑色，改变z的父和祖父结点颜色并做一次右旋，以保持性质5
      z-&parent-&parent-&color=RED;
      RIGHT_ROTATE(T,z-&parent-&parent);//z的祖父结点不会是叶子结点(由13.3-4可知)，所以不用在右旋前做判断。
     }
    }
    else//下面else分支类似于上面,注意到else分支的情况2和情况3所做旋转正好是if分支情况的逆。
    {
     struct Tree*y=z-&parent-&parent-&
     if (y-&color==RED)
     {
      z-&parent-&color=BLACK;
      y-&color=BLACK;
      z-&parent-&parent-&color=RED;
      z=z-&parent-&
     }
     else
     {
      if (z==z-&parent-&left)
      {
       z=z-&
       RIGHT_ROTATE(T,z);
      }
               z-&parent-&color=BLACK;
      z-&parent-&parent-&color=RED;
      LEFT_ROTATE(T,z-&parent-&parent);
     }
    }
   }
   root-&color=BLACK;//最后给根结点着为黑色。
void RB_INSERT(struct Tree*T,struct Tree*z)
 struct Tree*y=
 struct Tree*x=
 while (x!=nil)
  y=x;
  if (z-&key&x-&key)
  {
   x=x-&
  }
  else x=x-&
 z-&parent=y;
 if (y==nil)
  root=z;
 else if(z-&key&y-&key)
  y-&left=z;
 else y-&right=z;
 z-&left=//给插入结点左右孩子赋值为空。
 z-&right=
 z-&color=RED;//给插入结点着为红色。
 RB_INSERT_INSERT_FIXUP(T,z);
13.3-1在RB_INSERT的第16行中，假设新插入的结点z是红的。注意如果将z着为黑色，则红黑树性质4就不会被破坏。那么我们为什么没有选择将z着为黑色呢？
如果z着为黑色，那么性质5会被破坏，红黑树调整起来会更复杂。
13.3-2在将关键字48,38,31,12,19,8插入一棵初始为空的红黑树中之后，结果树是什么样子？
13.3-3假设图13-5和图13-6中子树α，β，γ，δ和ε的黑高度都是k.标上各个节点的黑高度，以验证图中所示的各种转换能保持性质5.
各个结点的黑高如下图：
由图可以看出经过以上所有图中的子树黑高都是k+2.所以保持性质5.
13.3-4 Teach教授担心RB_INSERT_FIXUP可能将叶子结点设置为RED。这时当z为根时，第1行的测试就不会让循环结束。通过证明RB_INSERT-FIXUP永远不会将叶子结点设置为RED，来说明这位教授担心是没有必要的。
如果结点z是叶子结点的话，那么z.p必然是根节点，根据循环不变式b部分可知z.p是黑色的，那么循环自动结束，所以也就遍历不到z.p.p这个叶子结点了。特别要注意的是在case2时，我们把z=z.p让z上升1层，但是通过旋转又让z下降一层，这样z.p.p的地位不变，所以没有问题。
13.3-5 考虑用RB_INSERT插入n个结点而成的一棵红黑树。证明：如果n&1，则该树至少有一个红结点。
最坏情况是假设前n-1个插入结点后都为黑色，那么第n个结点插入后，由于开始设置为红色，满足红黑树性质，所以此结点颜色不会由于RB_INSERT_FIXUP调整而改变。
13.3-6说明如果红黑树的表示中不提供父指针的话，应当如何有效地实现RB_INSERT.

删除操作运行时间是O(lgn).并且比插入操作复杂。
代码如下：
void RB_DELETE_FIXUP(struct Tree*x)
struct Tree*w=NULL;//w是x的兄弟结点
while (x!=root&&x-&color==BLACK)//如果x是黑色并且不是根结点，才进行循环。
{//x是一个具有双重颜色的结点，调整的目的是把x的黑色属性向上移动。
if (x==x-&parent-&left)
w=x-&parent-&
if (w-&color==RED)//情况一：x的兄弟结点w是红色的。
{//改变w和x.p的颜色+一次旋转使其变为情况二，三，四。
w-&color=BLACK;
x-&parent-&color=RED;
LEFT_ROTATE(x-&parent);
w=x-&parent-&
if (w-&left-&color==BLACK&&w-&right-&color==BLACK)//情况二：x的兄弟结点w是黑色的，而且w的两个子节点都是黑色。
w-&color=RED;//从x和w上去掉一重黑色。x还是黑色，而w变为红色。
x=x-&//x结点向上移动成为新的待调整结点。
if (w-&right-&color==BLACK)//情况三：x的兄弟结点w是黑色的，w的左孩子是红色的，w的右孩子是黑色的。
{//交换w和w.left的颜色+旋转使其转变为情况四。
w-&left-&color=BLACK;
w-&color=RED;
RIGHT_ROTATE(w);
w=x-&parent-&
w-&color=x-&parent-&//以下是情况四：x的兄弟结点w是黑色的，且w的右孩子是红色的。
x-&parent-&color=BLACK;//置x.p和w.right为黑色+旋转使其去掉x的额外黑色。
w-&right-&color=BLACK;
LEFT_ROTATE(x-&parent);
x=//x成为根结点，结束循环。
else//以下和上面的if分支类似，不做累述。
w=x-&parent-&
if (w-&color==RED)
w-&color=BLACK;
x-&parent-&color=RED;
RIGHT_ROTATE(x-&parent);
w=x-&parent-&
if (w-&left-&color==BLACK&&w-&right-&color==BLACK)
w-&color=RED;
if (w-&left-&color==BLACK)
w-&right-&color=BLACK;
w-&color=RED;
LEFT_ROTATE(w);
w=x-&parent-&
w-&color=x-&parent-&
x-&parent-&color=BLACK;
w-&left-&color=BLACK;
RIGHT_ROTATE(x-&parent);
}x-&color=BLACK;
void RB_DELETE(struct Tree*z)
struct Tree*y=z,*x;//y为待删除或待移动结点
int y_original_color=y-&//保存y的原始颜色，为做最后的调整做准备。
if (z-&left==nil)
x=z-&//x指向y的唯一子结点或者是叶子结点，保存x的踪迹使其移动到y的原始位置上
RB_TRANSPLANT(z,z-&right);//把以z.right为根的子树替换以z为根的子树。
else if (z-&right==nil)
x=z-&//x指向y的唯一子结点或者是叶子结点，保存x的踪迹使其移动到y的原始位置上
RB_TRANSPLANT(z,z-&left);//把以z.left为根的子树替换以z为根的子树。
y=ITERATIVE_TREE_MINIMUM(z-&right);//找到z.right的后继。
y_original_color=y-&//y的新的原始结点被重置。
x=y-&//x指向y的唯一子结点或者是叶子结点，保存x的踪迹使其移动到y的原始位置上
if (y-&parent==z)
x-&parent=y;//由于z的父结点是要删除的结点，所以不能指向它，于是指向y
RB_TRANSPLANT(y,y-&right);//把以y.right为根的子树替换以y为根的子树。
y-&right=z-&
y-&right-&parent=y;
RB_TRANSPLANT(z,y);//把以y为根的子树替换以z为根的子树。
y-&left=z-&
y-&left-&parent=y;
y-&color=z-&//把已经删除的结点颜色赋值给y，保证了y以上的树结构红黑性质不变。
if(y_original_color==BLACK) //y的原始颜色为黑色，说明需要调整红黑颜色。
RB_DELETE_FIXUP(x);
既然删除代码也已经给出，那么下面是第13章红黑树涉及的所有函数代码如下：
#include &iostream&
#define BLACK 0
#define RED 1
#define Nil -1
#define LEN sizeof(struct Tree)
struct Tree
struct Tree*
struct Tree*
struct Tree*
struct Tree*root=NULL;
struct Tree*nil=NULL;
void LEFT_ROTATE(struct Tree*x)
{//左旋转：分三个步骤①②③来叙述旋转代码的。
struct Tree*y=x-&//设置y结点。
x-&right=y-&//本行代码以及下面的if结构表达的是“y的左孩子成为x的右孩子”。①
if(y-&left!=nil)
y-&left-&parent=x;
y-&parent=x-&//本行代码以及下面的if-else结构表达的过程是“y成为该子树新的根”。②
if(x-&parent==nil)
else if(x==x-&parent-&left)
x-&parent-&left=y;
else x-&parent-&right=y;
y-&left=x;//本行代码以及下面一行都表达了“x成为y的左孩子”。③
x-&parent=y;
void RIGHT_ROTATE(struct Tree*x)
{//右旋转：分三个步骤①②③来叙述旋转代码的。
struct Tree*y=x-&//设置y结点。
x-&left=y-&//本行代码以及下面的if结构表达的是“y的左孩子成为x的右孩子”。①
if(y-&right!=nil)
y-&right-&parent=x;
y-&parent=x-&//本行代码以及下面的if-else结构表达的过程是“y成为该子树新的根”。②
if(x-&parent==nil)
else if(x==x-&parent-&right)
x-&parent-&right=y;
else x-&parent-&left=y;
y-&right=x;//本行代码以及下面一行都表达了“x成为y的左孩子”。③
x-&parent=y;
void RB_INSERT_INSERT_FIXUP(struct Tree*z)
while (z-&parent-&color==RED)
if (z-&parent==z-&parent-&parent-&left)
struct Tree*y=z-&parent-&parent-&//叔结点
if (y-&color==RED)//情况一：叔结点为红色
{//给p1,y,p2着色以保持性质5。并且解决了z的父结点和z都是红色结点问题
z-&parent-&color=BLACK;
y-&color=BLACK;
z-&parent-&parent-&color=RED;
z=z-&parent-&//把z的祖父结点当成新结点z进入下一次循环
if (z==z-&parent-&right)//情况二：检查z是否是一个右孩子且叔结点为黑色，前提是p1结点不是叶子结点
{//使用一个左旋让情况2转变为情况3
LEFT_ROTATE(z);//由于进入if语句后可知旋转结点不可能是叶子结点，这样就不用判断z是否是叶子结点了。
z-&parent-&color=BLACK;//情况三：是z是一个左孩子且叔结点为黑色，改变z的父和祖父结点颜色并做一次右旋，以保持性质5
z-&parent-&parent-&color=RED;
RIGHT_ROTATE(z-&parent-&parent);//由于p2可能是叶子结点，所以最好还是用一个if判断
else//下面else分支类似于上面,注意到else分支的情况2和情况3所做旋转正好是if分支情况的逆。
struct Tree*y=z-&parent-&parent-&
if (y-&color==RED)
z-&parent-&color=BLACK;
y-&color=BLACK;
z-&parent-&parent-&color=RED;
z=z-&parent-&
if (z==z-&parent-&left)
RIGHT_ROTATE(z);
z-&parent-&color=BLACK;
z-&parent-&parent-&color=RED;
LEFT_ROTATE(z-&parent-&parent);
root-&color=BLACK;//最后给根结点着为黑色。
void RB_INSERT(struct Tree*z)
struct Tree*y=
struct Tree*x=
while (x!=nil)
if (z-&key&x-&key)
else x=x-&
z-&parent=y;
if (y==nil)
else if(z-&key&y-&key)
y-&left=z;
else y-&right=z;
z-&left=//给插入结点左右孩子赋值为空。
z-&color=RED;//给插入结点着为红色。
RB_INSERT_INSERT_FIXUP(z);
void RB_TRANSPLANT(struct Tree*u,struct Tree*v)
if (u-&parent==nil)
else if(u==u-&parent-&left)
u-&parent-&left=v;
else u-&parent-&right=v;
v-&parent=u-&
//非递归版本的查找二叉查找树的最小值
struct Tree*ITERATIVE_TREE_MINIMUM(struct Tree*x)
while (x-&left!=nil)
//非递归版本的二叉查找树查找函数
struct Tree*ITERATIVE_TREE_SEARCH(struct Tree*x,int k)
while (x!=nil&&k!=x-&key)
if (k&x-&key)
else x=x-&
void RB_DELETE_FIXUP(struct Tree*x)
struct Tree*w=NULL;//w是x的兄弟结点
while (x!=root&&x-&color==BLACK)//如果x是黑色并且不是根结点，才进行循环。
{//x是一个具有双重颜色的结点，调整的目的是把x的黑色属性向上移动。
if (x==x-&parent-&left)
w=x-&parent-&
if (w-&color==RED)//情况一：x的兄弟结点w是红色的。
{//改变w和x.p的颜色+一次旋转使其变为情况二，三，四。
w-&color=BLACK;
x-&parent-&color=RED;
LEFT_ROTATE(x-&parent);
w=x-&parent-&
if (w-&left-&color==BLACK&&w-&right-&color==BLACK)//情况二：x的兄弟结点w是黑色的，而且w的两个子节点都是黑色。
w-&color=RED;//从x和w上去掉一重黑色。x还是黑色，而w变为红色。
x=x-&//x结点向上移动成为新的待调整结点。
if (w-&right-&color==BLACK)//情况三：x的兄弟结点w是黑色的，w的左孩子是红色的，w的右孩子是黑色的。
{//交换w和w.left的颜色+旋转使其转变为情况四。
w-&left-&color=BLACK;
w-&color=RED;
RIGHT_ROTATE(w);
w=x-&parent-&
w-&color=x-&parent-&//以下是情况四：x的兄弟结点w是黑色的，且w的右孩子是红色的。
x-&parent-&color=BLACK;//置x.p和w.right为黑色+旋转使其去掉x的额外黑色。
w-&right-&color=BLACK;
LEFT_ROTATE(x-&parent);
x=//x成为根结点，结束循环。
else//以下和上面的if分支类似，不做累述。
w=x-&parent-&
if (w-&color==RED)
w-&color=BLACK;
x-&parent-&color=RED;
RIGHT_ROTATE(x-&parent);
w=x-&parent-&
if (w-&left-&color==BLACK&&w-&right-&color==BLACK)
w-&color=RED;
if (w-&left-&color==BLACK)
w-&right-&color=BLACK;
w-&color=RED;
LEFT_ROTATE(w);
w=x-&parent-&
w-&color=x-&parent-&
x-&parent-&color=BLACK;
w-&left-&color=BLACK;
RIGHT_ROTATE(x-&parent);
}x-&color=BLACK;
void RB_DELETE(struct Tree*z)
struct Tree*y=z,*x;//y为待删除或待移动结点
int y_original_color=y-&//保存y的原始颜色，为做最后的调整做准备。
if (z-&left==nil)
x=z-&//x指向y的唯一子结点或者是叶子结点，保存x的踪迹使其移动到y的原始位置上
RB_TRANSPLANT(z,z-&right);//把以z.right为根的子树替换以z为根的子树。
else if (z-&right==nil)
x=z-&//x指向y的唯一子结点或者是叶子结点，保存x的踪迹使其移动到y的原始位置上
RB_TRANSPLANT(z,z-&left);//把以z.left为根的子树替换以z为根的子树。
y=ITERATIVE_TREE_MINIMUM(z-&right);//找到z.right的后继。
y_original_color=y-&//y的新的原始结点被重置。
x=y-&//x指向y的唯一子结点或者是叶子结点，保存x的踪迹使其移动到y的原始位置上
if (y-&parent==z)
x-&parent=y;//由于z的父结点是要删除的结点，所以不能指向它，于是指向y
RB_TRANSPLANT(y,y-&right);//把以y.right为根的子树替换以y为根的子树。
y-&right=z-&
y-&right-&parent=y;
RB_TRANSPLANT(z,y);//把以y为根的子树替换以z为根的子树。
y-&left=z-&
y-&left-&parent=y;
y-&color=z-&//把已经删除的结点颜色赋值给y，保证了y以上的树结构红黑性质不变。
if(y_original_color==BLACK) //y的原始颜色为黑色，说明需要调整红黑颜色。
RB_DELETE_FIXUP(x);
//中序遍历
void InOderTraverse(struct Tree *p)
if (p!=nil)
InOderTraverse(p-&left);
cout&&p-&key&&& &&&p-&color&&& &&&
InOderTraverse(p-&right);
void main()
int array1[6] = {41, 38, 31, 12, 19, 8};
nil=new struct Tree[LEN];
nil-&key=Nnil-&color=BLACK;
struct Tree*ROOT=new struct Tree[LEN];
ROOT-&key=array1[i++];
RB_INSERT(ROOT);
root=ROOT;
while (i!=6)
struct Tree*z=new struct Tree[LEN];
z-&key=array1[i];
RB_INSERT(z);
InOderTraverse(root);
int array2[6] = {8, 12, 19, 31, 38, 41};
for(i = 0; i& 6; i++)
struct Tree*x=ITERATIVE_TREE_SEARCH(root,array2[i]);
RB_DELETE(x);
InOderTraverse(root);
13.4-1 在执行RB_DELETE-FIXUP之后，证明：树根一定是黑色的。
若x为根结点，则不进入循环，直接给根x着为黑色。
若x非根且x为红结点，则不进入循环，也就不对除x以外的任何结点给变颜色，所以根结点颜色也一样不变。
若x非根且x为黑结点，则进入循环，注意到书中第6行，x的父结点被设置为红色，此时如果x父结点为根，那么在case1完成后会进入case2，3，4。进入case2时，x的父结点为新的x结点并且为红色循环自动结束，并在最后给新x着为黑色。若进入case34，注意到代码第18行x父结点被着为黑色，若x父节点为根，那么这里已经将其染黑。若开始不进入case1直接case2，那么x的父结点被更新为新x结点，新x结点为红色的话，循环退出，并且最后把新x结点着为黑色。若开始直接进入case34，那么x父结点即使为根，也在第18行被染为黑色，并且case4过后循环退出。总之根一定是黑色。
13.4-2在RB_DELETE中，如果x和x.p都是红色的。证明：可以通过调用RB_DELETE_FIXUP(T,x)来恢复性质4.
x和x.p都为红色，那么不进入循环，直接最后把x着为黑色以恢复性质4.。
13.4-3在练习13.3-3中，将关键字41,38,31,12,19,8连续插入一棵初始的空树中，从而得到一棵红黑树。请给出从该树中连续删除关键字8,12,19,31,38,41后的红黑树。
用上面完整红黑树代码可以实现本题要求。
13.4-4在RB_DELETE_FIXUP代码的哪些行中，可能会检查或修改哨兵T.nil?
书中代码第1,5,4,9,12,13,19行。
13.4-5在图13-7的每种情况中，给出所示子树的根结点至每棵子树α，β，......,ξ之间的黑结点个数，并验证它们在转换之后保持不变。当一个结点的color属性为c或c'时，在计数中用记号count(c)或count(c')来表示。
图a与图b在书中已经给出答案。图c子树α，β，......,ξ转换前后黑结点个数都是count(c)+2。图d α与β黑结点数count(c)+2. γ与δ黑结点数count(c)+count(c')+1.其他子树黑结点1+count(c).
13.4-6 Skelton和Baron教授担心在RB_DELETE_FIXUP的情况1开始时，结点x.p可能不是黑色的。如果这两位教授是对的，则第5-6行就是错的。证明：x.p在情况1开始时必是黑色的，从而说明这两位教授没有必要担心。
若x.p不是黑色的，那么w结点必然不是红色的。也就不会执行5-6行代码。
13.4-7 假设用RB_INSERT将一个结点x插入一棵红黑树，紧接着又用RB_DELETE将它从树中删除。结果的红黑树与初始红黑树是否一样？证明你的答案。
不一样。可以用上面所给完整代码进行验证，这里就略过。
13-1 持久动态集合
13-2 红黑树的连接操作
13-3 AVL树
13-4 Treap树






参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：76871次
积分：1555
积分：1555
排名：第18153名
原创：72篇
评论：65条
(1)(5)(12)(10)(4)(2)(5)(9)(13)(12)(1)