本文共 6666 字，大约阅读时间需要 22 分钟。

为了解决这个问题，我们需要设计一个高效的数据结构来维护一些数，并支持多种操作。选择AVL树是合理的，因为它在插入、删除和其他操作方面的时间复杂度都是O(log n)，非常适合处理大量数据。

1. 插入操作

插入操作需要找到插入位置并调整树的平衡。AVL树的插入涉及到递归查找位置，然后插入节点，并根据需要进行旋转以保持树的平衡。

2. 删除操作

删除操作需要找到目标节点并删除它。删除后，需要调整树的高度和平衡，确保树仍然满足AVL树的性质。

3. 查询排名操作

查询排名需要找到比当前数小的最大数。可以通过遍历左子树找到最大值，或者使用递归函数统计比当前数小的节点数。

4. 查询排名为xxx的数

直接查找树中是否存在等于xxx的数，如果存在，返回该数。

5. 求前驱操作

前驱是指小于当前数的最大值。可以从左子树中找到最大值，如果没有，再向上查找父节点的左子树。

6. 求后继操作

后继是指大于当前数的最小值。可以从右子树中找到最小值，如果没有，再向上查找父节点的右子树。

代码实现

#include 
   
    #include 
    
     typedef struct AVLNode {    int depth;    int val;    AVLNode* parent;    AVLNode* lchild;    AVLNode* rchild;} AVLNode;void update_depth(AVLNode* node) {    if (node == NULL) return;    node->depth = max(get_depth(node->lchild), get_depth(node->rchild)) + 1;}int get_depth(const AVLNode* node) {    if (node == NULL) return 0;    return node->depth;}int is_balance(const AVLNode* node) {    if (node == NULL) return 0;    return get_depth(node->lchild) - get_depth(node->rchild);}int get_balance(const AVLNode* node) {    if (node == NULL) return 0;    return is_balance(node);}AVLNode* insert(AVLNode* root, int val) {    if (root == NULL) {        root = new AVLNode;        root->val = val;        root->parent = NULL;        root->lchild = root->rchild = NULL;        update_depth(root);        return root;    }    if (val < root->val) {        root->lchild = insert(root->lchild, val);        if (root->lchild) {            root->lchild->parent = root;            update_depth(root);        }    } else if (val > root->val) {        root->rchild = insert(root->rchild, val);        if (root->rchild) {            root->rchild->parent = root;            update_depth(root);        }    } else {        // Node already exists, do nothing        return root;    }    return root;}AVLNode* remove(AVLNode* root, int val) {    if (root == NULL) return NULL;    if (root->val == val) {        // Remove and return root        AVLNode* temp = root;        root = root->lchild ? root->lchild : root->rchild;        if (temp->lchild) {            temp->lchild->parent = temp->parent;            update_depth(temp->lchild);        } else if (temp->rchild) {            temp->rchild->parent = temp->parent;            update_depth(temp->rchild);        } else {            if (temp->parent) {                temp->parent->lchild = NULL;                update_depth(temp->parent);            }        }        delete temp;        return root;    } else if (val < root->val) {        root->lchild = remove(root->lchild, val);        if (root->lchild) {            root->lchild->parent = root;            update_depth(root);        }    } else {        root->rchild = remove(root->rchild, val);        if (root->rchild) {            root->rchild->parent = root;            update_depth(root);        }    }    return root;}int get_rank(AVLNode* node, int value) {    if (node == NULL) return 0;    if (node->val < value) {        return 1 + get_rank(node->rchild, value);    } else if (node->val == value) {        return 1 + get_rank(node->lchild, value) + get_rank(node->rchild, value);    } else {        return get_rank(node->lchild, value);    }}AVLNode* find(AVLNode* root, int value) {    if (root == NULL) return NULL;    if (root->val == value) return root;    if (value < root->val) {        return find(root->lchild, value);    } else {        return find(root->rchild, value);    }}int get_left_max(AVLNode* node) {    if (node == NULL) return -1;    if (node->lchild) {        return get_left_max(node->lchild);    } else if (node->rchild) {        return get_left_max(node->rchild);    } else {        return node->val;    }}int get_right_min(AVLNode* node) {    if (node == NULL) return 100000;    if (node->rchild) {        return get_right_min(node->rchild);    } else if (node->lchild) {        return get_right_min(node->lchild);    } else {        return node->val;    }}int get_rank_value(AVLNode* root, int rank) {    if (root == NULL) return -1;    if (root->lchild) {        int left_rank = get_rank_value(root->lchild, rank - 1);        if (left_rank != -1) {            return left_rank;        }    }    if (root->val == rank) {        return root->val;    }    if (root->rchild) {        int right_rank = get_rank_value(root->rchild, rank - 1);        if (right_rank != -1) {            return right_rank;        }    }    return -1;}int get_previous(AVLNode* root, int value) {    if (root == NULL) return -1;    if (root->val < value) {        if (root->rchild) {            return get_previous(root->rchild, value);        } else if (root->parent) {            return get_previous(root->parent, value);        } else {            return -1;        }    } else {        if (root->lchild) {            return get_previous(root->lchild, value);        } else if (root->parent) {            return get_previous(root->parent, value);        } else {            return -1;        }    }}int get_next(AVLNode* root, int value) {    if (root == NULL) return 100000;    if (root->val > value) {        if (root->lchild) {            return get_next(root->lchild, value);        } else if (root->parent) {            return get_next(root->parent, value);        } else {            return 100000;        }    } else {        if (root->rchild) {            return get_next(root->rchild, value);        } else if (root->parent) {            return get_next(root->parent, value);        } else {            return 100000;        }    }}int main() {    int n;    std::cin >> n;    AVLNode* root = NULL;    for (int i = 0; i < n; ++i) {        int a, b;        std::cin >> a >> b;        switch (a) {            case 1: root = insert(root, b); break;            case 2: root = remove(root, b); break;            case 3: {                int rank = get_rank(root, b);                std::cout << rank << std::endl;            } break;            case 4: {                int val = get_rank_value(root, b);                if (val != -1) {                    std::cout << val << std::endl;                }            } break;            case 5: {                int prev = get_previous(root, b);                if (prev != -1) {                    std::cout << prev << std::endl;                }            } break;            case 6: {                int next = get_next(root, b);                if (next != 100000) {                    std::cout << next << std::endl;                }            } break;        }    }    return 0;}
    
   

代码解释

该实现确保了每个操作的时间复杂度为O(log n)，适用于大数据量。

转载地址：http://svki.baihongyu.com/