我的提交

 
#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <stdlib.h>


//BST
typedef struct node {
    struct node *parent;
    struct node *left;
    struct node *right;
    int cnt;
    int size;
    int val;
} node;

typedef struct BST {
    node *root;
} BST;

//insert a newNode with a value of VAL into BST tree
void BST_insert(BST *T, int val) {
    //pos points the parent of NewNode
    node *pos = NULL;
    node *now = T->root;
    while (now != NULL) {
        now->size++;
        pos = now;
        if (val < now->val) {
            now = now->left;
        } else if (val > now->val) {
            now = now->right;
        } else {
            now->cnt++;
            return;
        }
    }
    //malloc memory for the NEWNODE
    node *newNode = (node *)malloc(sizeof(node));
    
    newNode->val = val;
    newNode->size = 1;
    newNode->cnt = 1;
    newNode->parent = pos;
    newNode->left = NULL;
    newNode->right = NULL;

    if (pos != NULL) {
        if (val < pos->val) {
            pos->left = newNode;
        } else {
            pos->right = newNode;
        }
    } else {
        T->root = newNode;
    }
}

//to print BST in preorder
//the non-recursive preorder dfs using stack
void BST_show_preorder(BST *T) {
    node *now = T->root;
    if (now == NULL) {
        puts("no element");
        return;
    }
    //the preorder of BST
    int *ans = (int *)malloc(now->size * sizeof(int));
    node **stack = (node **)malloc(now->size * sizeof(node *));
    int p = 0, q = 0;
    while (now != NULL || p != 0) {
        if (now != NULL) {
            ans[q++] = now->val;
            stack[p++] = now;
            now = now->left;
        } else {
            now = stack[--p]->right;
        }
    }
    for (int i = 0; i < q; i++) {
        if (i != q - 1) printf("%d ", ans[i]);
        else printf("%d\n", ans[i]);
    }
    free(ans);
    free(stack);
}

void BST_show_inorder(BST *T) {
    node *now = T->root;
    if (now == NULL) {
        puts("no element");
        return;
    }
    //the preorder of BST
    int *ans = (int *)malloc(now->size * sizeof(int));
    node **stack = (node **)malloc(now->size * sizeof(node *));
    int p = 0, q = 0;
    while (now != NULL || p != 0) {
        if (now != NULL) {
            stack[p++] = now;
            now = now->left;
        } else {
            now = stack[--p]->right;
            for (int j = 0; j < stack[p]->cnt; j++)
            ans[q++] = stack[p]->val;
        }
    }
    for (int i = 0; i < q; i++) {
        if (i != q - 1) printf("%d ", ans[i]);
        else printf("%d\n", ans[i]);
    }
    free(ans);
    free(stack);
}
//find the minimum of BST
node * BST_minimum(node *root) {
    node *now = root;
    if (now == NULL) {
        puts("no element");
        return NULL;
    }
    while (now->left != NULL) {
        now = now->left;
    }
    return now;
}

//find the maximum of BST
node * BST_maximum(node *root) {
    node *now = root;
    if (now == NULL) {
        puts("no element");
        return NULL;
    }
    while (now->right != NULL) {
        now = now->right;
    }
    return now;
}

node * BST_find(BST *T, int val) {
    node *x = T->root;
    while (x != NULL) {
        if (x->val == val) {
            return x;
        }
        if (val < x->val) {
            x = x->left;
        } else {
            x = x->right;
        }
    }
    return NULL;
}

node * BST_predecessor(node *root) {
    node *x = root;
    if (x->left) {
        return BST_maximum(x->left);
    }
    node *y = x->parent;
    while (y != NULL && x == y->left) {
        x = y;
        y = y->parent;
    }
    return y;
}
node * BST_successor(node *root) {
    node *x = root;
    if (x->right) {
        return BST_minimum(x->right);
    }
    node *y = x->parent;
    while (y != NULL && x == y->right) {
        x = y;
        y = y->parent;
    }
    return y;
}

node *BST_kth(BST *T, int rank) {
    node *x = T->root;
    while (x != NULL) {
        int l, r;
        if (x->left == NULL) l = 0, r = 1;
        else l = x->left->size + 1, r = x->left->size + x->cnt;
        if (rank < l) x = x->left;
        else if (rank > r) x = x->right, rank = rank - r;
        else return x;
    }
    return NULL;
}

int BST_GetRankOf(BST *T, int val) {
    node *x = T->root;
    int cnt = 0;
    while (x != NULL) {
        if (x->val < val) {
            if (x->left != NULL) {
                cnt += x->left->size + x->cnt;
            } else cnt += x->cnt;
            x = x->right;
        } else if (x->val > val) {
            x = x->left;
        } else {
            if (x->left != NULL) {
                cnt += x->left->size;
            }
            break;
        }
    }
    return cnt + 1;
}

void __TRANSPLANT(BST *T, node *u, node *v) {
    if (u->parent == NULL) {
        T->root = v;
    } else if (u == u->parent->left) {
        u->parent->left = v;
    } else u->parent->right = v;
    if (v != NULL) {
        v->parent = u->parent;
    }
}

void BST_delete(BST *T, int val) {
    node *x = T->root;
    while (x != NULL) {
        x->size--;
        if (x->val == val) break;
        if (val < x->val) x = x->left;
        else x = x->right;
    }
    x->cnt--;
    if (x->cnt > 0) return;
    if (x->left == NULL) {
        __TRANSPLANT(T, x, x->right);
    } else if (x->right == NULL) {
        __TRANSPLANT(T, x, x->left);
    } else {
        node *y = x->right;
        while (y->left != NULL) {
            y->size--;
            y = y->left;
        }
        if (y->parent != x) {
            __TRANSPLANT(T, y, y->right);
            y->right = x->right;
            y->right->parent = y;
        }
        __TRANSPLANT(T, x, y);
        y->left = x->left;
        y->left->parent = y;
        int tmp = y->cnt;
        if (y->left != NULL) {
            tmp += y->left->size;
        }
        if (y->right != NULL) {
            tmp += y->right->size;
        }
        y->size = tmp;
    }
    free(x);
}

node *BST_lower_bound(BST *T, int val) {
    node *x = T->root;
    node *y = NULL;
    while (x != NULL) {
        if (x->val < val) {
            x = x->right;
        } else {
            y = x;
            x = x->left;
        }
    }
    return y;
}

node *BST_r_lower_bound(BST *T, int val) {
    node *x = T->root;
    node *y = NULL;
    while (x != NULL) {
        if (x->val > val) {
            x = x->left;
        } else {
            y = x;
            x = x->right;
        }
    }
    return y;
}

int main() {

    //BST *T = (BST *)malloc(sizeof(BST));
    //T->root = NULL;

    //BST_insert(T, 15);
    //BST_insert(T, 6);
    //BST_insert(T, 18);
    //BST_insert(T, 3);
    //BST_insert(T, 7);
    //BST_insert(T, 17);
    //BST_insert(T, 20);
    //BST_insert(T, 2);
    //BST_insert(T, 4);
    //BST_insert(T, 13);
    //BST_insert(T, 9);

    //BST_show_preorder(T);
    //BST_show_inorder(T);
    ///*
    //printf("%p %p\n", T->root, NULL);
    //*/
    //printf("%d %d\n", BST_minimum(T->root)->val, BST_maximum(T->root)->val);
    //
    //printf("%d ", BST_find(T, 15)->val);
    //printf("%d ", BST_find(T, 6)->val);
    //printf("%d ", BST_find(T, 18)->val);
    //printf("%d ", BST_find(T, 3)->val);
    //printf("%d ", BST_find(T, 7)->val);
    //printf("%d ", BST_find(T, 17)->val);
    //printf("%d ", BST_find(T, 20)->val);
    //printf("%d ", BST_find(T, 2)->val);
    //printf("%d ", BST_find(T, 4)->val);
    //printf("%d ", BST_find(T, 13)->val);
    //printf("%d ", BST_find(T, 9)->val);
    //puts("");

    //printf("%d ", BST_successor(BST_find(T, 2))->val);
    //printf("%d ", BST_successor(BST_find(T, 3))->val);
    //printf("%d ", BST_successor(BST_find(T, 4))->val);
    //printf("%d ", BST_successor(BST_find(T, 6))->val);
    //printf("%d ", BST_successor(BST_find(T, 7))->val);
    //printf("%d ", BST_successor(BST_find(T, 9))->val);
    //printf("%d ", BST_successor(BST_find(T, 13))->val);
    //printf("%d ", BST_successor(BST_find(T, 15))->val);
    //printf("%d ", BST_successor(BST_find(T, 17))->val);
    //printf("%d ", BST_successor(BST_find(T, 18))->val);
    //puts("");

    //printf("%d ", BST_predecessor(BST_find(T, 3))->val);
    //printf("%d ", BST_predecessor(BST_find(T, 4))->val);
    //printf("%d ", BST_predecessor(BST_find(T, 6))->val);
    //printf("%d ", BST_predecessor(BST_find(T, 7))->val);
    //printf("%d ", BST_predecessor(BST_find(T, 9))->val);
    //printf("%d ", BST_predecessor(BST_find(T, 13))->val);
    //printf("%d ", BST_predecessor(BST_find(T, 15))->val);
    //printf("%d ", BST_predecessor(BST_find(T, 17))->val);
    //printf("%d ", BST_predecessor(BST_find(T, 18))->val);
    //printf("%d ", BST_predecessor(BST_find(T, 20))->val);
    //puts("");

    //printf("%d ", BST_kth(T, 1)->val);
    //printf("%d ", BST_kth(T, 2)->val);
    //printf("%d ", BST_kth(T, 3)->val);
    //printf("%d ", BST_kth(T, 4)->val);
    //printf("%d ", BST_kth(T, 5)->val);
    //printf("%d ", BST_kth(T, 6)->val);
    //printf("%d ", BST_kth(T, 7)->val);
    //printf("%d ", BST_kth(T, 8)->val);
    //printf("%d ", BST_kth(T, 9)->val);
    //printf("%d ", BST_kth(T, 10)->val);
    //printf("%d ", BST_kth(T, 11)->val);
    //puts("");

    //BST_insert(T, 3);
    //printf("%d ", BST_kth(T, 1)->val);
    //printf("%d ", BST_kth(T, 2)->val);
    //printf("%d ", BST_kth(T, 3)->val);
    //printf("%d ", BST_kth(T, 4)->val);
    //printf("%d ", BST_kth(T, 5)->val);
    //printf("%d ", BST_kth(T, 6)->val);
    //printf("%d ", BST_kth(T, 7)->val);
    //printf("%d ", BST_kth(T, 8)->val);
    //printf("%d ", BST_kth(T, 9)->val);
    //printf("%d ", BST_kth(T, 10)->val);
    //printf("%d ", BST_kth(T, 11)->val);
    //printf("%d ", BST_kth(T, 12)->val);
    //puts("");

    //printf("%d ", BST_GetRankOf(T, 2));
    //printf("%d ", BST_GetRankOf(T, 3));
    //printf("%d ", BST_GetRankOf(T, 4));
    //printf("%d ", BST_GetRankOf(T, 6));
    //printf("%d ", BST_GetRankOf(T, 7));
    //printf("%d ", BST_GetRankOf(T, 9));
    //printf("%d ", BST_GetRankOf(T, 13));
    //printf("%d ", BST_GetRankOf(T, 15));
    //printf("%d ", BST_GetRankOf(T, 17));
    //printf("%d ", BST_GetRankOf(T, 18));
    //printf("%d ", BST_GetRankOf(T, 20));
    //puts("");
    //
    //printf("@@%d\n", T->root->size);
    //BST_delete(T, 3);
    //printf("@@%d\n", T->root->size);
    //BST_show_inorder(T);
    //BST_delete(T, 3);
    //printf("@@%d\n", T->root->size);
    //BST_show_inorder(T);
    //BST_delete(T, 4);
    //printf("@@%d\n", T->root->size);
    //BST_show_inorder(T);
    //BST_delete(T, 2);
    //printf("@@%d\n", T->root->size);
    //BST_show_inorder(T);
    //BST_delete(T, 17);
    //printf("@@%d\n", T->root->size);
    //BST_show_inorder(T);
    //BST_delete(T, 9);
    //printf("@@%d\n", T->root->size);
    //BST_show_inorder(T);
    //BST_delete(T, 15);
    //printf("@@%d\n", T->root->size);
    //BST_show_inorder(T);
    //BST_delete(T, 18);
    //printf("@@%d\n", T->root->size);
    //BST_show_inorder(T);
    //BST_delete(T, 13);
    //printf("@@%d\n", T->root->size);
    //BST_show_inorder(T);
    //BST_show_preorder(T);
    //printf("%d %d %d\n", T->root->val, T->root->left->val, T->root->left->right->val);
    //node *x = T->root;
    //while (x != NULL) {
    //    x->size--;
    //    if (x->val == 7) break;
    //    if (7 < x->val) x = x->left;
    //    else x = x->right;
    //}
    //x->cnt--;
    //printf("%d %d\n", x->val, x->size);
    //printf("%p %p\n", x->left, x->right);
    //__TRANSPLANT(T, x, x->right);
    //printf("%d %d\n", T->root->val, T->root->size);
    //printf("%p %d %p\n", T->root->left, T->root->left->val, T->root->right);
    //printf("%p %p\n", T->root->left->left, T->root->left->right);
    //BST_show_inorder(T);
    //BST_delete(T, 20);
    //BST_show_inorder(T);
    //BST_delete(T, 6);
    //BST_show_inorder(T);
    BST *T = (BST *)malloc(sizeof(BST));
    T->root = NULL;
    int q;
    scanf("%d", &q);
    for (int i = 0; i < q; i++) {
        int op, x;
        scanf("%d %d", &op, &x);
        if (op == 1) {
            BST_insert(T, x);
        } else if (op == 2) {
            BST_delete(T, x);
        } else if (op == 3) {
            printf("%d\n", BST_GetRankOf(T, x));
        } else if (op == 4) {
            printf("%d\n", BST_kth(T, x)->val);
        } else if (op == 5) {
            node *u = BST_lower_bound(T, x);
            if (u == NULL) printf("%d\n", BST_maximum(T->root)->val);
            else printf("%d\n", BST_predecessor(u)->val);
        } else if (op == 6) {
            node *u = BST_r_lower_bound(T, x);
            if (u == NULL) printf("%d\n", BST_minimum(T->root)->val);
            else printf("%d\n", BST_successor(u)->val);
        }
    }
    //printf("%p\n", BST_kth(T, 19));
    //printf("%d @%d @%d\n", T->root->size, T->root->left->size, T->root->right->size);
    //printf("%d %d\n", T->root->left->left->size, T->root->left->right->size);
    //printf("%d %d %d\n", T->root->left->right->left->size, T->root->left->right->right->size, T->root->left->right->cnt);
    //node *x = T->root;
    //int rank = 19;
    //while (x != NULL) {
    //    printf("%d\n", x->val);
    //    int l, r;
    //    if (x->left == NULL) l = 0, r = 1;
    //    else l = x->left->size + 1, r = x->left->size + x->cnt;
    //    if (rank < l) x = x->left;
    //    else if (rank > r) x = x->right, rank = rank - r;
    //    else break;
    //}
    //BST_show_inorder(T);
    //BST_show_preorder(T);
    return 0; 
}