c语言红黑树
㈠ 谁有数据结构与算法分析:C语言描述高清版或者课后习题的答案
书特点如下：
●专用一章来讨论算法设计技巧，包括贪婪算法、分治算法、动态规划、随机化算法以及回溯算法
●介绍了当前流行的论题和新的数据结构，如斐波那契堆、斜堆、二项队列、跳跃表和伸展树
●安排一章专门讨论摊还分析，考查书中介绍的一些高级数据结构
●新开辟一章讨论高级数据结构以及它们的实现，其中包括红黑树、自顶向下伸展树。treap树、k-d树、配对堆以及其他相关内容
●合并了堆排序平均情况分析的一些新结果
目录
出版者的话
专家指导委员会
译者序
前言
第1章 引论
第2章 算法分析
第3章 表、栈和队列
第4章 树
第5章 散列
第6章 优先队列（堆）
第7章 排序
第8章 不相交集ADT
第9章 图论算法
第10章 算法设计技巧
第11章 摊还分析
第12章 高级数据结构及其实现索引。
㈡ 两道编程算法题（两图一道），题目如下，可以给出算法思路或者源代码，源代码最好是C语言的
就会个第一题(因为第一题上已经给出了大致思路)
思路:用map容器(它的内部数据结构是一颗红黑树，查找和插入数据速度非常快)
map<int,st>a;//key(int)：设置为1~n的数;value(st):设置为key的前驱和后继；
这样一来就可以像链表快速插入数据，又可以像数组随机访问元素(key,就相当于数组的下标)
下面是代码和运行截图；
看代码前建议先了解一下map容器的具体用法;
#include<iostream>
#include<map>
#include<vector>
using namespace std;
struct st{//两个成员变量用来储存前驱和后继
int left;//0
int right;//1
st()
{
left=0;
right=0;
}
};
void input(map<int,st> &a)//输出
{
st t;
int s=0;
map<int,st>::iterator it;//迭代器(指针)
for(it=a.begin();it!=a.end();it++)//循环迭代
{
t=it->second;
if(t.left==0)//左边等于0,说明该数是第一个数
{
s=it->first;//记录key
break;
}
}
t=a[s];
cout<<s<<" ";
while(t.right!=0)//循环找当前数的右边的数(右边的为0，就说明该数是最后一个数)
{
cout<<t.right<<" ";
t=a[t.right];
}
}
int main()
{
st t,t_i,t_x,t_k,s;
map<int,st>a;
map<int,st>::iterator it;
int n,x,p,x_l,x_r;
cin>>n;
for(int i=1;i<=n;i++)//map容器赋初值(i,t)
//i:(key)下标;t:(value)结构体变量
{
a.insert(make_pair(i,t));
}
for(int i=2;i<=n;i++)
{
cin>>x>>p;
if(p==0)//x的左边插入i
{
t=a[x];
if(t.left==0)//x的左边没有数
{
t_x.left=i;
t_i.right=x;
a[x]=t_x;
a[i]=t_i;
}
else//x的左边有数
{
int x_left;
t_x=a[x];
x_left=t_x.left;
t_k=a[x_left];
t_i.right=x;
t_i.left=t_x.left;
t_k.right=i;
t_x.left=i;
a[x]=t_x;
a[i]=t_i;
a[x_left]=t_k;
}
}
else//x的右边插入i
{
t=a[x];
if(t.right==0)//x的右边没有数
{
t_x.right=i;
t_i.left=x;
a[x]=t_x;
a[i]=t_i;
}
else//x的左边有数
{
int x_right;
t_x=a[x];
x_right=t_x.right;
t_k=a[x_right];
t_i.left=x;
t_i.right=t_x.right;
t_k.left=i;
t_x.right=i;
a[x]=t_x;
a[i]=t_i;
a[x_right]=t_k;
}
}
}
for(it=a.begin();it!=a.end();it++)//循环迭代打印各个数之间的关系
{
cout<<it->first<<" ";
cout<<"左边:";
cout<<it->second.left<<" ";
cout<<"右边:";
cout<<it->second.right<<endl;
}
input(a);//打印序列
return 0;
}
/*
4
1 0
2 1
1 0
2 3 4 1
*/
