学步园

顺序统计树：

enum nodecolor {red,black};
struct os_node
{
    int key;
    os_node *left;
    os_node *right;
    os_node *p;
    nodecolor color;
    int size;
    os_node(int a,nodecolor c=red,int s=1)
    {
        key=a;
        color=c;
        size=s;
    }
};

static os_node *NIL=new os_node(0,black,0);

os_node* os_select(os_node *x,int i)
//寻找x为根顺序统计树中第i小关键字的结点指针,O(lgn)
{
    int r=x->left->size+1;
    if(i==r)
        return x;
    else if(i<r)
        return os_select(x->left,i);
    else
        return os_select(x->right,i-r);
}

int os_rank(os_node *x,os_node *z)
//给定x为根的顺序统计树中的结点z，返回对x进行中序遍历后z的位置,即z的秩,O(lgn)
{
    int r=z->left->size+1;
    os_node *y=z;
    while(y!=x)
    {
        if(y==y->p->right)
            r=r+y->p->left->size+1;
        y=y->p;
    }
    return r;
}

int os_key_rank(os_node *x,int k)
//给定树根x和关键字k，返回k的秩，
{
    if(x->key==k)
        return x->left->size+1;
    else if(x->key>k)
        return os_key_rank(x->left,k);
    else
        return x->left->key+1+os_key_rank(x->right,k);
}

区间树：

enum nodecolor {red,black};
class interval//区间
{
    int low;
    int high;
};

struct interval_node
{
    interval inter;
    int max;//以该结点为根的树中所有区间端点的最大值
    interval_node *left;
    interval_node *right;
    interval_node *p;
    nodecolor color;
    interval_node(int l,int h,nodecolor c=red)
    {
        inter.low=l;
        inter.high=h;
        color=c;
    }
};

static interval_node *NIL=new interval_node(0,0,black);

interval interval_search(interval_node *x,interval i)
//找出以x为根的区间树中覆盖区间i的那个结点
{
    interval_node *y=x;
    while(y!=NIL && (i.low>y->inter.high || i.high<y->inter.low))
    {
        if(y->left!=NIL && y->left->max>=i.low)
            y=y->left;
        else
            y=y->right;
    }
    return y;
}