📄 _ab_tree.c
字号:
v->son[2]=w ;
v->p=2;v->k[1]=u->k[1];
u->same[1] = v;
v->same[1] = u;
w->index=2;
minimum=u;
u->son[2] = w;
w->son[1] = u;
}
else {
u=new ab_tree_node(0,0,2,v,1);
v->son[1]=w;
w->same[1] = v;
v->same[1] = w;
v->son[2]=u;u->k[1]=key; u->inf=inf;
v->p=2;v->k[1]=w->k[1];
w->index=1;
maximum=u;
w->son[2] = u;
u->son[1] = w;
}
w->father=v;
return u;
};
if ((w!=maximum) && (cmp(key,w->k[1])>0)) w=w->son[2];
ab_tree_node* u;
int index1 = w->index;
v = w->father;
if (cmp(key,w->k[1])<0)
{ u = expand(v,index1-1); // new son u left of w
/*
v
/ | \
(u) w
*/
u->k[1] = key;
u->inf = inf;
u->son[2] = w;
u->son[1] = w->son[1];
w->son[1] = u;
u->same[1] = v;
v->k[index1] = key;
v->same[index1] = u ;
if (minimum == w)
minimum=u;
else
u->son[1]->son[2] = u;
}
else
{ u = expand(v,index1); // new son u right of w
/*
v
/ | \
w (u)
*/
u->k[1] = key;
u->inf = inf;
u->son[1] = w;
u->son[2] = w->son[2];
w->son[2] = u;
if (maximum == w)
{
maximum=u;
v->k[index1] = w->k[1];
w->same[1] = v;
v->same[index1] = w ;
}
else
{
v->k[index1+1] = key;
u->same[1] = v;
v->same[index1+1] = u ;
u->son[2]->son[1] = u;
}
}
if (v->p > b) split_node(v);
return u;
}
else { clear_inf(w->inf);
w->inf = inf;
return w;
}
};
ab_tree_node* ab_tree::locate(GenPtr key) const
{
/* searching for an element key in a (a,b)-tree ;
we search down the tree starting at the root r until we reache
a leave. In each node v we use the sequence k[1](v),..k[v->p-1](v)
in order to guide the search to the proper subtree.In the the
function we assume that k[0](v)<key<k[v->p](v) for every
element key in U
locate returns a pointer to a leave*/
register ab_tree_node* v = root;
register int i;
if (v == nil) return nil;
while (v->p) /* while v is not a leave*/
{ for(i=1; i < v->p && cmp(key,v->k[i]) > 0; i++); // s.n.
v=v->son[i];
};
return (cmp(key,v->k[1]) <= 0) ? v : nil;
};
ab_tree_node* ab_tree::locate_pred(GenPtr key) const
{ ab_tree_node* v = locate(key);
if (v==0) return maximum;
if (cmp(key,v->k[1])==0) return v;
return v->son[1];
}
ab_tree_node* ab_tree::lookup(GenPtr k) const
{ ab_tree_node* p = locate(k);
if (p && cmp(k,key(p))!=0 ) p = 0;
return p;
}
void ab_tree::fuse(ab_tree_node* v,ab_tree_node* y)
{
/* fuse v and y, i.e. make all sons of y to sons of v and move all
keys from y to v and delete node y; also move one key (the key
between the pointers to y and v) from z to v; (note that this will
shrink z, i.e. decrease the arity of z by one)
*/
ab_tree_node* z=v->father;
GenPtr hilf=z->k[v->index] ; /* before k[v->p] was not used {=0}*/
/*
we only must copy the pointer of son and the node-keys
from y to v
*/
/* change same-pointer of y and z */
v->k[v->p]=hilf;
v->same[v->p]=z->same[v->index];
v->same[v->p]->same[1] = v;
for(int i=1;i<y->p;i++) { v->k[v->p+i]=y->k[i];
v->same[v->p+i]=y->same[i];
v->same[v->p+i]->same[1]=v;
v->son[v->p+i]=y->son[i];
v->son[v->p+i]->index=v->p+i;
v->son[v->p+i]->father=v;
};
v->son[v->p+y->p]=y->son[y->p]; /* copy of the last son from y*/
v->son[v->p+y->p]->index=v->p+y->p;
v->son[v->p+y->p]->father=v;
v->p=v->p+y->p;
for(i=v->index;i<z->p;i++) { z->k[i]=z->k[i+1];
z->same[i] = z->same[i+1];
z->son[i+1]=z->son[i+2];
if (z->son[i+1]!=0){z->son[i+1]->index=i+1;
z->son[i+1]->father=z;};
};
z->p--;
z->k[z->p]=0;
z->same[z->p]=0;
delete y;
};
void ab_tree::share(ab_tree_node* v,ab_tree_node* y,int direct)
{
/* we assume that y is the right brother of v;
take the leftmost son away from y and make it an additional(right-
most) son of v; also move one key( the key between the pointers
to v and y) from z down to v and replace it by the leftmost
key of y;
the other case is equivalent
let z be the father of v
*/
ab_tree_node* z=v->father;
if (direct==1) {
v->son[v->p+1]=y->son[1];
v->son[v->p+1]->index=v->p+1;
v->son[v->p+1]->father=v;
v->k[v->p]=z->k[v->index];
v->same[v->p]=z->same[v->index];
v->same[v->p]->same[1] = v;
z->k[v->index]=y->k[1];
z->same[v->index]=y->same[1];
z->same[v->index]->same[1]=z;
v->p++;
for(int i=1;i<(y->p)-1;i++)
{ y->son[i]=y->son[i+1];
y->son[i]->index=i;
y->k[i]=y->k[i+1];
y->same[i]=y->same[i+1];
};
y->p--; // decrease number of children
y->son[y->p]=y->son[y->p+1];
y->son[y->p]->index=y->p;
y->son[y->p+1]=0;
y->k[y->p]=0;
y->same[y->p] = 0;
}
else { // y is at the left side of v
for(int i=v->p;i>=1;i--)
{ v->son[i+1]=v->son[i];
v->son[i+1]->index=i+1;
v->k[i+1]=v->k[i];
v->same[i+1]=v->same[i];
};
v->son[1]=y->son[y->p];
v->son[1]->index=1;
v->son[1]->father=v;
y->son[y->p]=0;
v->p++;
y->p--;
v->k[1]=z->k[y->index];
v->same[1]=z->same[y->index];
v->same[1]->same[1] = v;
z->k[y->index]=y->k[y->p];
z->same[y->index]=y->same[y->p];
z->same[y->index]->same[1] = z;
y->k[y->p]=0;
y->same[y->p]=0;
};
}
void ab_tree::del_item(ab_tree_node* w)
{
/*
we must delete leave w with father v
we shrink v by deleting leave w and one of the keys in the
adjacent to the pointer to w
(if w is the i-th son of v then we delete k[i](v) if i<v->p
k[i-1](v) if i=v->p ).
m.w. if i=v->p we overwrite the inner node
in which key w->k[1] is stored with k[i-1](v)
and then delete k[i-1](v)
*/
if (w==nil) error_handler(1,"ab_tree: nil item in del_item");
count--;
if (maximum==minimum)
{ maximum=minimum=root=0;
height=-1;
clear_key(w->k[1]);
clear_inf(w->inf);
delete w;
return;
}
/* here w==root==> last leave will be deleted*/
ab_tree_node* succ = w->son[2];
ab_tree_node* pred = w->son[1];
if (pred) pred->son[2] = succ;
else minimum = succ;
if (succ) succ->son[1] = pred;
else maximum = pred;
ab_tree_node* v = w->father;
v->son[w->index]=0;
if (w->index==v->p) {
if (succ)
{ //overwrite copies in inner node u
ab_tree_node* u = w->same[1];
int pos=1;
while(u->same[pos]!=w) pos++;
u->k[pos]=pred->k[1];
u->same[pos]=pred;
pred->same[1] = u;
}
else
v->same[v->p-1]->same[1]=0;
v->k[v->p-1]=0;
v->same[v->p-1]=0;
}
else { v->k[w->index]=0 ;
v->same[w->index]=0;
for(int i=w->index;i<(v->p)-1;i++)
{ v->k[i]=v->k[i+1];
v->same[i]=v->same[i+1];
v->son[i]=v->son[i+1];
v->son[i]->father=v;
v->son[i]->index=i;
};
v->son[v->p-1]=v->son[v->p];
v->son[v->p]=0;
v->k[v->p-1]=0;
v->same[v->p-1]=0;
v->son[v->p-1]->father=v;
v->son[v->p-1]->index=v->p-1;
};
clear_key(w->k[1]);
clear_inf(w->inf);
delete w;
(v->p)--;
if ((v==root) && (v->p==1)) {
if (v->son[1]==0)
{v->son[1]=v->son[2];
v->son[2]=0; };
root=v->son[1];
delete v;
root->index=0;
root->father=0;
root->p=0;
root->height=0;
height=0;
minimum=maximum=root;
return;
};
if (v->p >= a) return;
/* otherwise v needs to be rebalanced by either fusing or sharing
let y be any brother of v*/
ab_tree_node* z;
ab_tree_node* y;
int dir;
if (v->index==1) {
z=v->father;
y=z->son[v->index+1] ;
dir=1; // y is the right son of v
}
else {
z=v->father;
y=z->son[v->index-1] ;
dir =0; // y is the left son of v
};
while ((v->p==a-1) && (y->p==a))
{
if (dir==1) fuse(v,y);
else fuse(y,v);
if (z==root) {
if (z->p==1) {
if (dir==1){
root=v;
v->father=0;
v->index=0; }
else {
root=y;
y->father=0;
y->index=0; };
height--;
delete z;
};
return;
};
v=z; // continue recursion
if (v->index==1) {z=v->father;
y=z->son[v->index+1] ;
dir=1; // y is the right son of v
}
else { z=v->father;
y=z->son[v->index-1];
dir=0;
};
};
/* we have either v->p>=a and rebalancing is completed or
v->p = a-1 and y->p > a and rebalancing is completed by sharing;*/
if (v->p==a-1)
{ /*
it is important to which side y is in order to v
==> dir is an information about in the function share
*/
share(v,y,dir);
};
return;
}
ab_tree& ab_tree::conc(ab_tree& s2)
{
if ((a!=s2.a)||(b!=s2.b))
error_handler(1,"ab_tree: incompatible trees in concatenate operation");
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -