本文共 6884 字，大约阅读时间需要 22 分钟。
为了解决这个问题，我们需要设计一个高效的数据结构来维护一些数，并支持多种操作。选择AVL树是合理的，因为它在插入、删除和其他操作方面的时间复杂度都是O(log n)，非常适合处理大量数据。
插入操作需要找到插入位置并调整树的平衡。AVL树的插入涉及到递归查找位置，然后插入节点，并根据需要进行旋转以保持树的平衡。
删除操作需要找到目标节点并删除它。删除后，需要调整树的高度和平衡，确保树仍然满足AVL树的性质。
查询排名需要找到比当前数小的最大数。可以通过遍历左子树找到最大值，或者使用递归函数统计比当前数小的节点数。
直接查找树中是否存在等于xxx的数，如果存在，返回该数。
前驱是指小于当前数的最大值。可以从左子树中找到最大值，如果没有，再向上查找父节点的左子树。
后继是指大于当前数的最小值。可以从右子树中找到最小值，如果没有，再向上查找父节点的右子树。
#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/