凸包_百度百科
凸包（Convex Hull）是一个计算几何（图形学）中的概念。在一个V中，对于给定集合X，所有包含X的的S被称为X的凸包。X的凸包可以用X内所有点(X1，...Xn)的来构造.在二维中，凸包可想象为一条刚好包著所有点的橡皮圈。用不严谨的话来讲，给定二维平面上的点集，凸包就是将最外层的点连接起来构成的凸多边型，它能包含点集中所有的点。
⒈对于一个集合D，D中任意有限个点的线性组合的全体称为D的凸包。
⒉对于一个集合D，所有包含D的凸集之交称为D的凸包。
可以证明，上述两种定义是等价的
1 　点集Q的凸包（convex hull）是指一个最小凸多边形，满足Q中的点或者在多边形边上或者在其内。右图中由红色表示的多边形就是点集Q={p0,p1,...p12}的凸包。
2 　一组平面上的点，求一个包含所有点的最小的，这就是凸包问题了。这可以形象地想成这样：在地上放置一些不可移动的木桩，用一根绳子把他们尽量紧地圈起来，并且为凸边形，这就是凸包了。
凸包最常用的凸包算法是Graham扫描法和Jarvis步进法
Graham's Scan法
这个算法是由数学大师葛立恒（Graham）发明的，他曾经是美国数学学会（AMS）主席、AT&T首席科学家以及国际杂技师协会（IJA）主席。
给定平面上的二维点集，求解其凸包。
⒈ 在所有点中选取y坐标最小的一点H，当作基点。如果存在多个点的y坐标都为最小值，则选取x坐标最小的一点。坐标相同的点应排除。然后按照其它各点p和基点构成的向量&H,p&；与x轴的夹角进行排序，夹角由大至小进行顺时针扫描，反之则进行逆时针扫描。实现中无需求得夹角，只需根据余弦定理求出夹角的余弦值即可。以下图为例，基点为H，根据由小至大排序后依次为H，K，C，D，L，F，G，E，I，B，A，J。下面进行逆时针扫描。
⒉ 线段&H,K&；一定在凸包上，接着加入C。假设线段&K,C&；也在凸包上，因为就H，K，C三点而言，它们的凸包就是由此三点所组成。但是接下来加入D时会发现，线段&K,D&；才会在凸包上，所以将线段&K,C&；排除，C点不可能是凸包。
⒊ 即当加入一点时，必须考虑到前面的线段是否会出现在凸包上。从基点开始，凸包上每条相临的的旋转方向应该一致，并与扫描的方向相反。如果发现新加的点使得新线段与上线段的旋转方向发生变化，则可判定上一点必然不在凸包上。实现时可用向量进行判断，设新加入的点为pn + 1，上一点为pn，再上一点为pn - 1。顺时针扫描时，如果向量&pn - 1,pn&；与&pn,pn + 1&；的叉积为正（逆时针扫描判断是否为负），则将上一点删除。删除过程需要回溯，将之前所有叉积符号相反的点都删除，然后将新点加入凸包。
在上图中，加入K点时，由于线段&H,C&要旋转到&H,K&的角度，为顺时针旋转，所以C点不在凸包上，应该删除，保留K点。接着加入D点，由于线段&K,D&要旋转到&H,K&的角度，为逆时针旋转，故D点保留。按照上述步骤进行扫描，直到点集中所有的点都遍历完成，即得到凸包。
这个算法可以直接在原数据上进行运算，因此空间复杂度为O⑴。但如果将凸包的结果存储到另一数组中，则可能在代码级别进行优化。由于在扫描凸包前要进行排序，因此时间复杂度至少为快速排序的O(nlgn）。后面的扫描过程复杂度为O(n），因此整个算法的复杂度为O(nlgn）。
Jarvis步进法。
对于一个有三个或以上点的点集Q，过程如下：
计算点集最右边的点为凸包的顶点的起点，如上图的P3点。
For i = 0 To 总顶点数
计算有向向量P3-&Pi
If 其余顶点全部在有向向量P3-&Pi的左侧或右侧，则Pi点为凸包的下一顶点
Pi点加入凸包列表
此过程执行后，点按极角自动顺时针或逆时针排序，只需要按任意两点的次序就可以了。而左侧或右侧的判断可以用前述的矢量点积性质实现。
先构造一个中心点，然后将它与各点连接起来，按递增的方法，求出凸包上部；再按斜率递减的方法，求出凸包下部。
从最左边的点开始，按递增的方法，求出凸包上部；再按斜率递减的方法，求出凸包下部。水平法较中心法减少了斜率无限大的可能，减少了代码的。
选择最左、最右、最上、最下的点，它们必组成一个凸（或三角形）。这个四边形内的点必定不在凸包上。然后将其余的点按最接近的边分成四部分，再进行快包法(QuickHull)。[1]
#include&stdio.h&
#include&math.h&
#include&stdlib.h&
typedefstruct
POINTresult[102];//保存凸包上的点，相当于所说的栈S
POINTa[102];
doubleDistance(POINTp1,POINTp2)//两点间的距离
returnsqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
doubleMultiply(POINTp1,POINTp2,POINTp3)//叉积
return((p2.x-p1.x)*(p3.y-p1.y)-(p2.y-p1.y)*(p3.x-p1.x));
intCompare(constvoid*p1,constvoid*p2)//根据p0-&p1的极值和p0-&p2的极值进行比较，如果极值相同则用距离长度比较
POINT*p3,*p4;
p3=(POINT*)p1;
p4=(POINT*)p2;
m=Multiply(a[0],*p3,*p4);
if(m&0)return1;
elseif(m==0&&(Distance(a[0],*p3)&Distance(a[0],*p4)))
elsereturn-1;
//寻找凸包的过程，p0,p1,p2..的寻找过程在下面main中进行了
voidTubao()
result[0].x=a[0].x;
result[0].y=a[0].y;
result[1].x=a[1].x;
result[1].y=a[1].y;
result[2].x=a[2].x;
result[2].y=a[2].y;
for(i=3;i&=n;i++)
while(Multiply(result[top-1],result[top],a[i])&=0&&top&2)
result[top+1].x=a[i].x;
result[top+1].y=a[i].y;
doublepx,py,len,
while(scanf(&%d&,&n)!=EOF,n)
for(i=0;i&n;i++)
scanf(&%lf%lf&,&a[i].x,&a[i].y);
printf(&0.00/n&);
elseif(n==2)
printf(&%.2lf/n&,Distance(a[0],a[1]));
//这里的目的好像是找出y坐标最小的点，之后把他定义为P0
for(i=0;i&n;i++)
if(py==-1||a[i].y&py)
px=a[i].x;
py=a[i].y;
elseif(a[i].y==py&&a[i].x&px)
px=a[i].x;
py=a[i].y;
//swap(a[0],a[p])
temp=a[0].x;
a[0].x=a[p].x;
temp=a[0].y;
a[0].y=a[p].y;
//用叉乘来实现排序的比较
qsort(&a[1],n-1,sizeof(double)*2,Compare);
a[n].x=a[0].x;
a[n].y=a[0].y;
//调用tubao（）
for(i=0;i&i++)
len=len+Distance(result[i],result[i+1]);
printf(&%.2lf/n&,len);
#include&iostream&//求点集合的凸包的gram算法。n是顶点个数，x,y是顶点坐标。
#include&fstream&//order是按照顶点和左下脚的角度的排序后数组。
#include&deque&//tu即是逆时针的凸包上的顶点。
#include&math.h&
//使用条件：1。点可以任意给，可重复。
//2。三个以及以上的点。
ifstreamfin(&input.txt&);//3。已经考虑了边上有点的情况。
#defineNN1000
#definepi3.1415827
typedefstructCseg
doublex,y,
doublex[NN],y[NN];
deque&Cseg&
deque&int&
deque&Cseg&::iteratorp1;
deque&int&::iteratorp,q;
voidgram();
voidmakeorder(ints);
doubledist(doublex1,doubleyy1,doublex2,doubleyy2);
doublecross(doublex1,doubleyy1,doublex2,doubleyy2);
voidout();
for(inti=0;i&tu.size();i++)
cout&&order[tu].x&&&&&&order[tu].y&&
cout&&tu.size()&&&EdgesPolydgon&&&
for(inti=0;i&n;i++)
fin&&x&&y;
voidgram()
for(inti=1;i&n;i++)
if(y[mm]&y+1e-9)
elseif(fabs(y[mm]-y)&1e-9&&x[mm]&x+1e-9)
makeorder(mm);
seg1.x=x[mm];
seg1.y=y[mm];
tu.clear();
tu.push_back(0);
tu.push_back(1);
tu.push_back(2);
for(inti=3;i&order.size();i++)
p=tu.end();
seg1.x=order.x;
seg1.y=order.y;
if(cross(order[*p].x-order[*q].x,order[*p].y-order[*q].y,order.x-order[*q].x,order.y-order[*q].y)&1e-9)
tu.push_back(i);
tu.pop_back();
voidmakeorder(ints)
order.clear();
for(inti=0;i&n;i++)
tg=atan2(y-y[s],x-x[s]);
p1=order.begin();
while(p1!=order.end())
if(fabs(tg-p1-&tg)&1e-9)
if(dist(x[s],y[s],x,y)&dist(x[s],y[s],p1-&x,p1-&y)+1e-9)
elseif(tg&p1-&tg)
order.insert(p1,seg1);
if(p1==order.end())
order.insert(p1,seg1);
seg1.x=x[s];
seg1.y=y[s];
order.insert(order.begin(),seg1);
doublecross(doublex1,doubleyy1,doublex2,doubleyy2)
return(x1*yy2-x2*yy1);
doubledist(doublex1,doubleyy1,doublex2,doubleyy2)
returnpow((x1-x2)*(x1-x2)+(yy1-yy2)*(yy1-yy2),0.5);
代码三 (Pascal)
&&zero=1e-6;
&&maxn=1000;
&&maxnum=;
&&ans,temp:
&&x,y:array[0..maxn]&of&
&&zz,num:array[0..maxn]of&
procedure&swap(var&ii,jj:extended);
&&&&&&t:=ii:=jj:=t;
procedure&
&&&&&&readln(n);
&&&&&&&for&i:=1&to&n&do&readln(x[i],y[i]);
function&ok(x,midx,y,midy:extended):
if&&abs(x-midx)&=zero&then
&&&&if&abs(midy-y)&=zero&then&exit(0);
&&&&if&midy&y&then&exit(1)
&&&&else&exit(2);
&&&&&if&x&midx&then&exit(1)
&&&&&else&exit&(2);
procedure&qsort(head,tail:longint);
&&midx,midy:
&&&&&&midx:=x[(head+tail)div&2];
&&&&&&midy:=y[(head+tail)div&2];
&&&&&&repeat
&&&&&&&&while&ok(x[i],midx,y[i],midy)=1&do&inc(i);
&&&&&&&&while&ok(x[j],midx,y[j],midy)=2&do&dec(j);
&&&&&&&&if&i&=j&then
&&&&&&&&&&&&begin
&&&&&&&&&&&&&&swap(x[i],x[j]);
&&&&&&&&&&&&&&swap(y[i],y[j]);
&&&&&&&&&&&&&&inc(i);
&&&&&&&&&&&&&&dec(j);
&&&&&&&&&&&&
&&&&&until&i&j;
&&&&&&if&i&tail&then&qsort(i,tail);
&&&&&&if&j&head&then&qsort(head,j);
function&Plot(x1,y1,x2,y2:extended):
&&&&&Plot:=x1*y2-x2*y1;
function&check(first,last,new:longint):
ax,ay,bx,by:
&&ax:=x[last]-x[first];ay:=y[last]-y[first];
&&bx:=x[new]-x[first];by:=y[new]-y[first];
&&if&Plot(ax,ay,bx,by)&=0&then&exit(true)
&&&else&exit(false);
procedure&T
&zz[1]:=1;tail:=1;
&for&i:=2&to&n&do
&&&&&&while(zz[tail]&&1)and&check(zz[tail-1],zz[tail],i)&do&dec(tail);
&&&&&&inc(tail);
&&&&&&zz[tail]:=i;
&&inc(tot,tail-1);
&&for&i:=1&to&tail-1&do
&&&num[i]:=zz[i];
&&zz[1]:=n;tail:=1;
&&for&i:=n-1&downto&1&do
&&&&while&(zz[tail]&&n)&and&check(zz[tail-1],zz[tail],i)&do&dec(tail);
&&&&inc(tail);
&&&&zz[tail]:=i;
&&for&i:=1&to&tail-1&do
&&num[tot+i]:=zz[i];
&&inc(tot,tail-1);
function&dist(a,b:longint):
&&&&&dist:=sqrt((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]));
procedure&
&&&&qsort(1,n);
&&&&ans:=0;
&&&for&i:=1&to&tot-1&do
&&&&&&&&ans:=ans+dist(num[i],num[i+1]);
&&ans:=ans+dist(num[tot],num[1]）;
&&ans:=ans+temp*pi*2;
&&writeln(ans:0:1);
．平行处理实验室[引用日期]当前位置： &
求翻译：w r b l z n l n t m y s m x x z j z t m d s d q x y z l是什么意思？
w r b l z n l n t m y s m x x z j z t m d s d q x y z l
问题补充：
正在翻译，请等待...
正在翻译，请等待...
w r b l z n l n t m y s m x x z j z t m d s x y z l d q
我来回答：
参考资料：
* 验证码：
登录后回答可以获得积分奖励，并可以查看和管理所有的回答。 |
我要翻译和提问
请输入您需要翻译的文本！B-tree_百度百科
B-tree（多路搜索树，并不是二叉的）是一种常见的数据结构。使用B-tree结构可以显著减少定位记录时所经历的中间过程，从而加快存取速度。按照翻译，B 通常认为是Balance的简称。这个数据结构一般用于数据库的索引，综合效率较高。
B-tree中，每个结点包含：
1、本结点所含的个数；
2、指向的；
3、关键字；
4、指向子结点的指针；
对于一棵m阶B-tree，每个结点至多可以拥有m个子结点。各结点的关键字和可以拥有的子结点数都有限制，规定m阶B-tree中，根结点至少有2个子结点，除非根结点为，相应的，根结点中关键字的个数为1~m-1；非根结点至少有[m/2]（[]，向上取整）个子结点，相应的，关键字个数为[m/2]-1~m-1。
B-tree有以下特性：
1、关键字集合分布在整棵树中；
2、任何一个出现且只出现在一个结点中；
3、搜索有可能在非结束；
4、其搜索性能等价于在关键字全集内做一次；
5、自动层次控制；
由于限制了除根结点以外的非叶子结点，至少含有M/2个儿子，确保了结点的至少利用率，其最低搜索性能为：
B-tree最低搜索性能
其中，M为设定的非最多子树个数，N为总数；
所以B-树的性能总是等价于（与M值无关），也就没有B树平衡的问题；
由于M/2的限制，在插入结点时，如果结点已满，需要将结点分裂为两个各占M/2的结点；删除结点时，需将两个不足M/2的兄弟结点合并。
鉴于B-tree具有良好的定位特性，其常被用于对检索时间要求苛刻的场合，例如：
1、B-tree索引是数据库中存取和查找文件(称为记录或键值)的一种方法。
2、硬盘中的结点也是B-tree结构的。与内存相比，硬盘必须花成倍的时间来存取一个，这是因为硬盘的机械部件读写数据的速度远远赶不上纯电子媒体的内存。与一个结点两个分支的二元树相比，B-tree利用多个分支（称为子树）的结点，减少获取记录时所经历的结点数，从而达到节省的目的。
/* btrees.h */
* 平衡多路树的一种重要方案。
* 在 1970 年由 R. Bayer 和 E. McCreight 发明。
#define M 1
/* B 树的阶，即非根中键的最小数目。
* 有些人把阶定义为非根节点中子树的最大数目。
typedef struct btnode { /* B-Tree 节点 */
/* 节点中键的数目 */
typekey k[2*M]; /* 键 */
char *v[2*M]; /* 值 */
struct btnode *p[2*M+1]; /* 指向子树的 */
* 每个键的左子树中的所有的键都小于这个键，
* 每个键的右子树中的所有的键都大于等于这个键。
* 中的每个键都没有子树。
/* 当 M 等于 1 时也称为 2-3 树
* +----+----+
* | k0 | k1 |
* +-+----+----+---
* | p0 | p1 | p2 |
* +----+----+----+
extern int btree_ /* 查找时找到的键在中的位置 */
extern char * InsV /* 与要插的键相对应的值 */
extern btree search(typekey, btree);
extern btree insert(typekey,btree);
extern btree delete(typekey,btree);
extern int height(btree);
extern int count(btree);
extern double payload(btree);
extern btree deltree(btree);
/* end of btrees.h */
/*******************************************************/
/* btrees.c */
#include &&
#include &stdio.h&
#include &btrees.h&
btree search(typekey, btree);
btree insert(typekey,btree);
btree delete(typekey,btree);
int height(btree);
int count(btree);
double payload(btree);
btree deltree(btree);
static void InternalInsert(typekey, btree);
static void InsInNode(btree, int);
static void SplitNode(btree, int);
static btree NewRoot(btree);
static void InternalDelete(typekey, btree);
static void JoinNode(btree, int);
static void MoveLeftNode(btree t, int);
static void MoveRightNode(btree t, int);
static void DelFromNode(btree t, int);
static btree FreeRoot(btree);
static btree delall(btree);
static void Error(int,typekey);
int btree_ /* 查找时找到的键在中的位置 */
char * InsValue = NULL; /* 与要插的键相对应的值 */
/* 节点增减标志 */
static int btree_level = 0; /* 多路树的高度 */
static int btree_count = 0; /* 多路树的键总数 */
static int node_sum = 0; /* 多路树的节点总数 */
/* 当前访问的节点所处的高度 */
static btree NewT /* 在分割的时候指向新建的节点 */
static typekey InsK /* 要插入的键 */
btree search(typekey key, btree t)
int i,j,m;
level=btree_level-1;
while (level &= 0){
for(i=0, j=t-&d-1; i&j; m=(j+i)/2, (key & t-&k[m])?(i=m+1):(j=m));
if (key == t-&k [ i ]){
btree_disp =
if (key & t-&k [ i ]) /* i == t-&d-1 时有可能出现 */
t = t-&p[ i ];
return NULL;
btree insert(typekey key, btree t)
level=btree_
InternalInsert(key, t);
if (flag == 1) /* 根节点满之后，它被分割成两个半满节点 */
t=NewRoot(t); /* 树的高度增加 */
void InternalInsert(typekey key, btree t)
int i,j,m;
if (level & 0){ /* 到达了树的底部: 指出要做的插入 */
NewTree = NULL; /* 这个键没有对应的子树 */
InsKey = /* 导致底层的增加键值+空子树对 */
btree_count++;
flag = 1; /* 指示上层节点把返回的键插入其中 */
for(i=0, j=t-&d-1; i&j; m=(j+i)/2, (key & t-&k[m])?(i=m+1):(j=m));
if (key == t-&k[ i ]) {
Error(1,key); /* 键已经在树中 */
if (key & t-&k[ i ]) /* i == t-&d-1 时有可能出现 */
InternalInsert(key, t-&p[ i ]);
if (flag == 0)
/* 有新键要插入到当前节点中 */
if (t-&d & 2*M) {/* 当前节点未满 */
InsInNode(t, i); /* 把键值+子树对插入当前节点中 */
flag = 0; /* 指示上层节点没有需要插入的键值+子树，插入过程结束 */
else /* 当前节点已满，则分割这个页面并把键值+子树对插入当前节点中 */
SplitNode(t, i); /* 继续指示上层节点把返回的键值+子树插入其中 */
* 把一个键和对应的右子树插入一个节点中
void InsInNode(btree t, int d)
/* 把所有大于要插入的键值的键和对应的右子树右移 */
for(i = t-&d; i & i--){
t-&k[ i ] = t-&k[i-1];
t-&v[ i ] = t-&v[i-1];
t-&p[i+1] = t-&p[ i ];
/* 和右子树 */
t-&k[ i ] = InsK
t-&p[i+1] = NewT
t-&v[ i ] = InsV
* 前件是要插入一个键和对应的右子树，并且本节点已经满
* 导致分割这个节点，和对应的右子树，
* 并向上层返回一个要插入键和对应的右子树
void SplitNode(btree t, int d)
typekey temp_k;
char *temp_v;
/* 建立新节点 */
temp = (btree)malloc(sizeof(node));
* +---+--------+-----+-----+--------+-----+
* | 0 | ...... | M | M+1 | ...... |2*M-1|
* +---+--------+-----+-----+--------+-----+
* |&- M+1 -&|&- M-1 -&|
if (d & M) { /* 要插入当前节点的右半部分 */
/* 把从 2*M-1 到 M+1 的 M-1 个键值+子树对转移到新节点中,
* 并且为要插入的键值+子树空出位置 */
for(i=2*M-1,j=M-1; i&=d; i--,j--) {
temp-&k[j] = t-&k[ i ];
temp-&v[j] = t-&v[ i ];
temp-&p[j+1] = t-&p[i+1];
for(i=d-1,j=d-M-2; j&=0; i--,j--) {
temp-&k[j] = t-&k[ i ];
temp-&v[j] = t-&v[ i ];
temp-&p[j+1] = t-&p[i+1];
/* 把的最右子树转移成新节点的最左子树 */
temp-&p[0] = t-&p[M+1];
/* 在新节点中和右子树 */
temp-&k[d-M-1] = InsK
temp-&p[d-M] = NewT
temp-&v[d-M-1] = InsV
/* 设置要插入上层节点的键和值 */
InsKey = t-&k[M];
InsValue = t-&v[M];
else { /* d &= M */
/* 把从 2*M-1 到 M 的 M 个键值+子树对转移到新节点中 */
for(i=2*M-1,j=M-1; j&=0; i--,j--) {
temp-&k[j] = t-&k[ i ];
temp-&v[j] = t-&v[ i ];
temp-&p[j+1] = t-&p[i+1];
if (d == M) /* 要插入当前节点的正中间 */
/* 把要插入的子树作为新节点的最左子树 */
temp-&p[0] = NewT
/* 直接把要插入的键和值返回给上层节点 */
else { /* (d&M) 要插入当前节点的左半部分 */
/* 把当前的最右子树转移成新节点的最左子树 */
temp-&p[0] = t-&p[M];
/* 保存要插入上层节点的键和值 */
temp_k = t-&k[M-1];
temp_v = t-&v[M-1];
/* 把所有大于要插入的键值的键和对应的右子树右移 */
for(i=M-1; i&d; i--) {
t-&k[ i ] = t-&k[i-1];
t-&v[ i ] = t-&v[i-1];
t-&p[i+1] = t-&p[ i ];
/* 在节点中和右子树 */
t-&k[d] = InsK
t-&p[d+1] = NewT
t-&v[d] = InsV
/* 设置要插入上层节点的键和值 */
InsKey = temp_k;
InsValue = temp_v;
temp-&d = M;
node_sum++;
btree delete(typekey key, btree t)
level=btree_
InternalDelete(key, t);
if (t-&d == 0)
/* 根节点的子节点合并导致根节点键的数目随之减少，
* 当根节点中没有键的时候，只有它的最左子树可能非空 */
t=FreeRoot(t);
void InternalDelete(typekey key, btree t)
int i,j,m;
btree l,r;
if (level & 0) {
Error(0,key); /* 在整个树中未找到要删除的键 */
for(i=0, j=t-&d-1; i&j; m=(j+i)/2, (key & t-&k[m])?(i=m+1):(j=m));
if (key == t-&k[ i ]) { /* 找到要删除的键 */
if (t-&v[ i ] != NULL)
free(t-&v[ i ]); /* 释放这个节点包含的值 */
if (level == 0) { /* 有子树为空则这个键位于 */
DelFromNode(t,i);
btree_count--;
/* 指示上层节点本子树的键数量减少 */
} else { /* 这个键位于节点 */
lvl = level-1;
/* 找到前驱节点 */
r = t-&p[ i ];
while (lvl & 0) {
r = r-&p[r-&d];
t-&k[ i ]=r-&k[r-&d-1];
t-&v[ i ]=r-&v[r-&d-1];
r-&v[r-&d-1]=NULL;
key = r-&k[r-&d-1];
else if (key & t-&k[ i ]) /* i == t-&d-1 时有可能出现 */
InternalDelete(key,t-&p[ i ]);
/* 调整平衡 */
if (flag == 0)
if (t-&p[ i ]-&d & M) {
if (i == t-&d) /* 在最右子树中发生了删除 */
i--; /* 调整最右键的左右子树平衡 */
l = t-&p [ i ];
r = t-&p[i+1];
if (r-&d & M)
MoveLeftNode(t,i);
else if(l-&d & M)
MoveRightNode(t,i);
JoinNode(t,i);
/* 继续指示上层节点本子树的键数量减少 */
/* 指示上层节点本子树的键数量没有减少，删除过程结束 */
* 合并一个节点的某个键对应的两个子树
void JoinNode(btree t, int d)
btree l,r;
l = t-&p[d];
r = t-&p[d+1];
/* 把这个键下移到它的左子树 */
l-&k[l-&d] = t-&k[d];
l-&v[l-&d] = t-&v[d];
/* 把右子树中的所有键值和子树转移到左子树 */
for (j=r-&d-1,i=l-&d+r-&d; j &= 0 ; j--,i--) {
l-&k[ i ] = r-&k[j];
l-&v[ i ] = r-&v[j];
l-&p[ i ] = r-&p[j];
l-&p[l-&d+r-&d+1] = r-&p[r-&d];
l-&d += r-&d+1;
/* 释放右子树的节点 */
/* 把这个键右边的键和对应的右子树左移 */
for (i=d; i & t-&d-1; i++) {
t-&k[ i ] = t-&k[i+1];
t-&v[ i ] = t-&v[i+1];
t-&p[i+1] = t-&p[i+2];
node_sum--;
* 从一个键的右子树向左子树转移一些键，使两个子树平衡
void MoveLeftNode(btree t, int d)
btree l,r;
/* 应转移的键的数目 */
l = t-&p[d];
r = t-&p[d+1];
m = (r-&d - l-&d)/2;
/* 把这个键下移到它的左子树 */
l-&k[l-&d] = t-&k[d];
l-&v[l-&d] = t-&v[d];
/* 把右子树的最左子树转移成左子树的最右子树
* 从右子树向左子树移动 m-1 个键+子树对 */
for (j=m-2,i=l-&d+m-1; j &= 0; j--,i--) {
l-&k[ i ] = r-&k[j];
l-&v[ i ] = r-&v[j];
l-&p[ i ] = r-&p[j];
l-&p[l-&d+m] = r-&p[m-1];
/* 把右子树的最左键提升到这个键的位置上 */
t-&k[d] = r-&k[m-1];
t-&v[d] = r-&v[m-1];
/* 把右子树中的所有键值和子树左移 m 个位置 */
r-&p[0] = r-&p[m];
for (i=0; i&r-&d-m; i++) {
r-&k[ i ] = r-&k[i+m];
r-&v[ i ] = r-&v[i+m];
r-&p[ i ] = r-&p[i+m];
r-&p[r-&d-m] = r-&p[r-&d];
* 从一个键的左子树向右子树转移一些键，使两个子树平衡
void MoveRightNode(btree t, int d)
btree l,r;
/* 应转移的键的数目 */
l = t-&p[d];
r = t-&p[d+1];
m = (l-&d - r-&d)/2;
/* 把右子树中的所有键值和子树右移 m 个位置 */
r-&p[r-&d+m]=r-&p[r-&d];
for (i=r-&d-1; i&=0; i--) {
r-&k[i+m] = r-&k[ i ];
r-&v[i+m] = r-&v[ i ];
r-&p[i+m] = r-&p[ i ];
/* 把这个键下移到它的右子树 */
r-&k[m-1] = t-&k[d];
r-&v[m-1] = t-&v[d];
/* 把左子树的最右子树转移成右子树的最左子树 */
r-&p[m-1] = l-&p[l-&d];
/* 从左子树向右子树移动 m-1 个键+子树对 */
for (i=l-&d-1,j=m-2; j&=0; j--,i--) {
r-&k[j] = l-&k[ i ];
r-&v[j] = l-&v[ i ];
r-&p[j] = l-&p[ i ];
/* 把左子树的最右键提升到这个键的位置上 */
t-&k[d] = l-&k[ i ];
t-&v[d] = l-&v[ i ];
* 把一个键和对应的右子树从一个节点中删除
void DelFromNode(btree t, int d)
/* 把所有大于要删除的键值的键左移 */
for(i=d; i & t-&d-1; i++) {
t-&k[ i ] = t-&k[i+1];
t-&v[ i ] = t-&v[i+1];
* 建立有两个子树和一个键的根节点
btree NewRoot(btree t)
temp = (btree)malloc(sizeof(node));
temp-&d = 1;
temp-&p[0] =
temp-&p[1] = NewT
temp-&k[0] = InsK
temp-&v[0] = InsV
btree_level++;
node_sum++;
return(temp);
* 释放根节点，并返回它的最左子树
btree FreeRoot(btree t)
temp = t-&p[0];
btree_level--;
node_sum--;
void Error(int f,typekey key)
printf(&Btrees error: Insert %d!\n&,key);
printf(&Btrees error: delete %d!\n&,key);
int height(btree t)
return btree_
int count(btree t)
return btree_
double payload(btree t)
if (node_sum==0)
return (double)btree_count/(node_sum*(2*M));
btree deltree (btree t)
level=btree_
btree_level = 0;
return delall(t);
btree delall(btree t)
if (level &= 0) {
for (i=0; i & t-&d; i++)
if (t-&v[ i ] != NULL)
free(t-&v[ i ]);
if (level & 0)
for (i=0; i&= t-& i++)
t-&p[ i ]=delall(t-&p[ i ]);
return NULL;
/* end of btrees.c */
另外还有一种与此类似的树结构叫B+树，像 Berkerly DB , sqlite , mysql 数据库都使用了B+树算法处理索引。
B+和B-（即B）是因为每个结点上的不同。一个多一个，一个少一个。
对于B+树，其结点结构与B-tree相同，不同的是各结点的关键字和可以拥有的子结点数。如m阶B+树中，每个结点至多可以拥有m个子结点。非根结点至少有[m/2]个子结点，而关键字个数比B-tree多一个，为[m/2]~m。
这两种处理索引的数据结构的不同之处：
1。B树中同一键值不会出现多次，并且它有可能出现在叶结点，也有可能出现在结点中。而B+树的键一定会出现在叶结点中，并且有可能在非叶结点中也有可能重复出现，以维持B+树的平衡。
2。因为B树键位置不定，且在整个树结构中只出现一次，虽然可以节省存储空间，但使得在插入、删除操作复杂度明显增加。B+树相比来说是一种较好的折中。
3。B树的查询效率与键在树中的位置有关，最大与B+树相同(在叶结点的时候)，最小时间复杂度为1(在根结点的时候)。而B+树的时间复杂度对某建成的树是固定的。}