算法导论 数据扩张

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include<malloc.h>
//*********************************以下内容是插入源码****************************
#define N 10
#define K 100
typedef struct redblacknode RBN;
struct redblacknode {//红黑树的节点
    int key;
    char rb;
    RBN* father;
    RBN* left;
    RBN* right;
    int size;
};
void redblacktree(RBN* p, int key);//红黑树，能插入关键字
void happen_rand(int* p, int n);//生成随机数
void color(RBN* p);
void right_handed(RBN* p);//右旋
void left_handed(RBN* p);//左旋
RBN  sentry={-1,'b',&sentry,&sentry,&sentry };//哨兵，主要作用是节省空间，不然每一个叶节点都要开辟一个空结构体；详见算法导论10.2的介绍
RBN *uncle;//定义一个叔叔指针
RBN* NODE;//定义一个根节点指针
RBN* tmp,*tmptmp;

void happen_rand(int* p, int n) {
    int i;
    for (i = 0; i < N; i++) {
        p[i] = rand() % K;

    }
}

void redblacktree(RBN* p, int key) {//递归的方式把key插入到红黑树中
    if (key < p->key && p->left == &sentry) {//插入节点后需要用color函数调整颜***r />         p->left = (RBN*)malloc(sizeof(RBN));
        p->left->key = key;
        p->left->father = p;
        p->left->left = &sentry;
        p->left->right = &sentry;
        p->left->rb = 'r';
        color(p->left);
    }
    else if (key >= p->key && p->right == &sentry) {
        p->right = (RBN*)malloc(sizeof(RBN));
        p->right->key = key;
        p->right->father = p;
        p->right->left = &sentry;
        p->right->right = &sentry;
        p->right->rb = 'r';
        color(p->right);
    }
    else if (key < p->key && p->left != &sentry)
        redblacktree(p->left, key);
    else if (key >= p->key && p->right != &sentry)
        redblacktree(p->right, key);
    p->size++;
    while (p != NODE) {
        p = p->father;
        p->size--;
    }

}

void color(RBN* p) {//颜色调整分为6种状态，前两种不旋转直接调色，后四种要旋转，旋转后再调色，旋转有4种状态，每一种状态旋转后需要调色（176页）（/右旋）（\左旋）（<左旋+/右旋）（>右旋+\左旋）
    if (p->rb == 'b') { return; }
    if (p->father->rb == 'r') {
        if (p->father == p->father->father->left) {//父节点是左节点
            uncle = p->father->father->right;//叔节点是右节点
            if (uncle->rb == 'r') {//叔节点是红
                if (p->father->father->father != &sentry)p->father->father->rb = 'r';
                p->father->rb = 'b';
                uncle->rb = 'b';
                color(p->father->father);
            }
            else if (uncle->rb == 'b' || uncle == &sentry) {//叔节点是黑或者是无
                if (p == p->father->left) {//插入节点是左，进行右旋，变***r />                     right_handed(p->father);
                    p->father->rb = 'b';
                    p->father->right->rb = 'r';
                    color(p->father);
                }
                else if (p == p->father->right) {//插入节点是右，进行左旋,右旋,变***r />                     left_handed(p);
                    right_handed(p);
                    p->rb = 'b';
                    p->right->rb = 'r';
                    color(p);
                }

            }
        }
        else if (p->father == p->father->father->right) {//父节点是右节点
            uncle = p->father->father->left;//叔节点是左节点
            if (uncle->rb == 'r') {//叔节点是红
                if (p->father->father->father != &sentry)p->father->father->rb = 'r';
                p->father->rb = 'b';
                uncle->rb = 'b';
                color(p->father->father);
            }
            else if (uncle->rb == 'b' || uncle == &sentry) {//叔节点是黑或者是无
                if (p == p->father->right) {//插入节点是右，进行左旋，变***r />                     left_handed(p->father);
                    p->father->rb = 'b';
                    p->father->left->rb = 'r';
                    color(p->father);
                }
                else if (p == p->father->left) {//插入节点是左，进行右旋，左旋，左旋
                    right_handed(p);
                    left_handed(p);
                    p->rb = 'b';
                    p->left->rb = 'r';
                    color(p);
                }
            }
        }
    }

}

void left_handed(RBN* p) {
    int tmp;
    RBN* y = p;
    RBN* x = y->father;
    x->right = y->left;
    if (y->left != &sentry) y->left->father = x;
    y->father = x->father;
    if (x->father == &sentry) NODE = y;
    else if (x == x->father->left) x->father->left = y;
    else x->father->right = y;
    y->left = x;
    x->father = y;
    tmp = x->size;
    x->size = y->size;
    y->size = tmp;
}

void right_handed(RBN* p) {
    int tmp;
    RBN* x = p;
    RBN* y = x->father;
    y->left = x->right;
    if (x->right != &sentry) x->right->father = y;
    x->father = y->father;
    if (y->father == &sentry) NODE = x;
    else if (y == y->father->left) y->father->left = x;
    else y->father->right = x;
    x->right = y;
    y->father = x;
    tmp = x->size;
    x->size = y->size;
    y->size = tmp;
}
//*********************************以上内容是插入源码****************************

//;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

//*********************************以下内容是按层打印源码****************************
typedef struct queue SQ;//队列
struct queue {
    RBN array[N];
    RBN* head;
    RBN* tail;
};//申明队列结构体
int enqueue(SQ* p, RBN n);//入队
RBN* dequeue(SQ* p);//出队
int printf_tree_layer(RBN* p);//按层遍历打印二叉树
int  enqueue(SQ* p, RBN n) {
    *p->tail = n;
    p->tail++;
    if (p->tail == &p->array[N]) {
        p->tail = &p->array[0];
    }//尾部循环
    if (p->head == p->tail)//判断溢出
        return -1;

}
RBN* dequeue(SQ* p) {
    if (p->head == &p->array[N]) {
        p->head = &p->array[0];
    }//尾部循环
    if (p->head == p->tail) //判断溢出
    {
        RBN* p = NULL;
        return p;
    }
    return (p->head++);
}
SQ Q = { {0},&Q.array[0],&Q.array[0] };//Q队列初始化
int  k = 0;
int sumup = 1;//当前行的元素个数
int sumdown = 0;//下一行的元素个数
int printf_tree_layer(RBN* p) {
    if (p == &sentry) { printf("not number"); return; }
    if (0 == sumup) {//这里是关键，当前元素是0的时候换行，
        if (sumdown == 0) { printf("\n"); sumdown = 1; return; }//判断下一行是否为0
        printf("\n");
        sumup = sumdown;
        sumdown = 0;
    }
    printf("%d ", p->key);
    sumup--;//每次打印后当前元素个数减一
    if (&sentry != p->left) { enqueue(&Q, *p->left); sumdown++; }//每次生成子元素后下一行元素个数加一
    if (&sentry != p->right) { enqueue(&Q, *p->right); sumdown++; }//每次生成子元素后下一行元素个数加一
    RBN* T = dequeue(&Q);
    printf_tree_layer(T);


}
//*********************************以上内容是按层打印源码****************************

//;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;


//*********************************以下内容是删除源码****************************
RBN* y,*x;//记录将要被删除(或者是后继节点)的和替补的结构体的地址
char y_color;///记录将要被删除的结构体的颜***r /> void rb_transplant(RBN* father, RBN* son);//儿子移动到父亲的位置
RBN* rb_delete(RBN *p);//删除p节点
RBN*  address(RBN*p,int key);//通过关键字，找地址，
RBN* tree_minsum(RBN* p);//找到后继（该节点的右子树的最小元素）
RBN* cut_out_color_fixup(RBN* x);//删除后，保持平衡
RBN* cut_out_color_fixup(RBN* x) {
    RBN* w; //兄弟节点
    while (x != NODE && x->rb == 'b') {//y是黑色，x也是黑色，x就是双黑节点（被移动的节点是黑色，替补上去的也是黑色，叫做双黑非根节点）
        if (x == x->father->left) {
            w = x->father->right;//兄弟节点
            if (w->rb == 'r') {//四种状态，详见算法导论186页
                w->rb = 'b';
                x->father->rb = 'r';
                left_handed(w);
                w = x->father->right;
            }
            if (w->left->rb == 'b' && w->right->rb == 'b') {
                w->rb = 'r';
                x = x->father;
                continue;
            }
            else if (w->right->rb == 'b') {
                w->left->rb = 'b';
                w->rb = 'r';
                right_handed(w->left);
                w = x->father->right;
            }
            w->rb = x->father->rb;
            x->father->rb = 'b';
            w->right->rb = 'b';
            left_handed(w);
            x = NODE;

        }
        else {
            w = x->father->left;//兄弟节点
            if (w->rb == 'r') {
                w->rb = 'b';
                x->father->rb = 'r';
                right_handed(w);
                w = x->father->left;
            }
            if (w->left->rb == 'b' && w->right->rb == 'b') {
                w->rb = 'r';
                x = x->father;
                continue;
            }
            else if (w->left->rb == 'b') {
                w->right->rb = 'b';
                w->rb = 'r';
                left_handed(w->right);
                w = x->father->left;
            }
            w->rb = x->father->rb;
            x->father->rb = 'b';
            w->left->rb = 'b';
            right_handed(w);
            x = NODE;
        

        }
    }
    x->rb = 'b';
}
RBN* tree_minsum(RBN* p)

{
    while (p->left != &sentry) {
        p = p->left;
    }
    return p;
}
void rb_transplant(RBN* father, RBN* son) {
    son->size = father->size;
    if (father->father == &sentry) {
        NODE = son;
    }
    else if (father == father->father->left) {
        father->father->left = son;
    }
    else {
        father->father->right = son;

    }
    son->father = father->father;


}
RBN* address(RBN*p,int key) {
    if (key == p->key) return p;
    if (p == &sentry)return &sentry;
    if (key < p->key) 
        address(p->left, key);
    else
        address(p->right, key);

}
RBN* rb_delete(RBN* z) {
    y = z;
    y_color = y->rb;
    if (z->left == &sentry) {
        x = z->right;
        rb_transplant(z, z->right);
    }
    else if(z->right == &sentry) {
        x = z->left;
        rb_transplant(z, z->left);
    }
    else {
        y = tree_minsum(z->right);
        y_color = y->rb;
        x = y->right;
        if (y->father == z){//后继节点是z的右孩子
            x->father = y;
        }
        else { //将后继节点y取出,放到z的右孩子的父节点
            rb_transplant(y, y->right);
            y->right = z->right;
            y->right->father = y;
        }
        rb_transplant(z, y);
        y->left = z->left;
        y->left->father = y;
        y->rb = z->rb;//保持原有的平衡
    }
    x->size = y->size - 1;
    while (x != NODE) {
        x = x->father;
        x->size --;
    }
    
    if (y_color == 'b') {//y是红色，必然没有孩子，直接删除后，无需调整颜色，y是黑色，删除后需要调整颜***r />         cut_out_color_fixup(x);
    }
}

//*********************************以上内容是删除源码****************************

//;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

//*********************************以下内容是扩张源码****************************
int r=0,R=0;//记录当前点的秩
int size_result(RBN* p) {
    if (p == &sentry) return 0;
    if (p->left == &sentry && p->right == &sentry){
        p->size = 1;
        return 1;
    }
    else
        return p->size = size_result(p->left) + size_result(p->right)+1;

}
RBN* os_select(RBN*x, int i);//找到第i小关键字的结构体
int os_rank(RBN* x);//找到x的秩
RBN* os_select(RBN* x, int i) {
    if (x == &sentry)
        return &sentry;
    r = x->left->size + 1;
    if (r == i)
        return x;
    if (i < r)
        os_select(x->left, i);
    else
        os_select(x->right, i - r);

}
int os_rank(RBN* x) {
    RBN* X = NODE;
    int r = 0;
    while (x!=X) {
        if (x->key < X->key)
            X = X->left;
        else {
            r = r + 1 + X->left->size;
            X=X->right;
        }
    }
    r = r + 1 + x->left->size;
    return r;

}

//在对红黑树删除和插入时，会影响它的秩，该部分代码，直接修改插入和删除函数(x点的size减一，并且一直往上走，每个点减一，到跟停止)

//*********************************以上内容是扩张源码****************************
int I=1;//秩

int main() {
    int array[N] = { 0}, i;
    happen_rand(array, N);//数组随机化
    RBN node = { array[0],'b' ,&sentry,&sentry,&sentry };//根节点
    NODE = &node;
    for (i = 1; i < N; i++) {
        redblacktree(NODE, array[i]);//在红黑树中插入元素
    }
    printf_tree_layer(NODE);
    printf("\n");
    size_result(NODE);
    printf("%d\n",os_select(NODE,I)->key);
    for (int i = 0; i < N; i++) {


        RBN* tmp = address(NODE, array[i]);
        printf("%d %d\n", tmp->key,os_rank(tmp));//通过关键字找到秩
        printf("%d %d\n", os_select(NODE, os_rank(tmp))->key, os_rank(tmp));//通过秩找到关键字
    }
    for (i = 0; i < N; i++) {
        RBN* tmp = address(NODE,array[i] );
        rb_delete(tmp);//在红黑树中删除元素
        printf_tree_layer(NODE);
    }
    
}