//Place your snippets for cpp here. Each snippet is defined under a snippet name and has a prefix, body and 
// description. The prefix is what is used to trigger the snippet and the body will be expanded and inserted. Possible variables are:
// $1, $2 for tab stops, $0 for the final cursor position, and ${1:label}, ${2:another} for placeholders. Placeholders with the 
// same ids are connected.
// prefix 的格式要求是 acm-[一级标题编号].[二级标题编号][该代码片段的英文简称]
// description 的格式要求是 "插入 [该代码片段的中文名]"

{
    "平衡树": {
        "prefix": "acm-2.7BalancedBST",
        "body": [
            "struct TreeNode {",
            "    int key;",
            "    TreeNode* left;",
            "    TreeNode* right;",
            "    int height; // 节点高度",
            "    int size;   // 子树大小",
            "    int count;  // 重复次数",
            "",
            "    TreeNode(int value) ",
            "        : key(value), height(1), size(1), count(1), left(nullptr), right(nullptr) {}",
            "};",
            "",
            "class BalancedBST {",
            "private:",
            "    TreeNode* root;",
            "",
            "    // 获取节点高度",
            "    int getHeight(TreeNode* node) const {",
            "        return node ? node->height : 0;",
            "    }",
            "",
            "    // 获取节点子树大小",
            "    int getSize(TreeNode* node) const {",
            "        return node ? node->size : 0;",
            "    }",
            "",
            "    // 更新节点高度和大小",
            "    void updateNodeInfo(TreeNode* node) const {",
            "        if (node) {",
            "            node->height = 1 + std::max(getHeight(node->left), getHeight(node->right));",
            "            node->size = node->count + getSize(node->left) + getSize(node->right);",
            "        }",
            "    }",
            "",
            "    // 获取平衡因子",
            "    int getBalanceFactor(TreeNode* node) const {",
            "        return node ? getHeight(node->left) - getHeight(node->right) : 0;",
            "    }",
            "",
            "    // 右旋",
            "    TreeNode* rightRotate(TreeNode* y) const {",
            "        TreeNode* x = y->left;",
            "        TreeNode* T2 = x->right;",
            "",
            "        x->right = y;",
            "        y->left = T2;",
            "",
            "        updateNodeInfo(y);",
            "        updateNodeInfo(x);",
            "",
            "        return x;",
            "    }",
            "",
            "    // 左旋",
            "    TreeNode* leftRotate(TreeNode* x) const {",
            "        TreeNode* y = x->right;",
            "        TreeNode* T2 = y->left;",
            "",
            "        y->left = x;",
            "        x->right = T2;",
            "",
            "        updateNodeInfo(x);",
            "        updateNodeInfo(y);",
            "",
            "        return y;",
            "    }",
            "",
            "    // 平衡节点",
            "    TreeNode* balanceNode(TreeNode* node) const {",
            "        if (!node) return nullptr;",
            "",
            "        updateNodeInfo(node);",
            "        int balance = getBalanceFactor(node);",
            "",
            "        // Left Left Case",
            "        if (balance > 1 && getBalanceFactor(node->left) >= 0)",
            "            return rightRotate(node);",
            "",
            "        // Right Right Case",
            "        if (balance < -1 && getBalanceFactor(node->right) <= 0)",
            "            return leftRotate(node);",
            "",
            "        // Left Right Case",
            "        if (balance > 1 && getBalanceFactor(node->left) < 0) {",
            "            node->left = leftRotate(node->left);",
            "            return rightRotate(node);",
            "        }",
            "",
            "        // Right Left Case",
            "        if (balance < -1 && getBalanceFactor(node->right) > 0) {",
            "            node->right = rightRotate(node->right);",
            "            return leftRotate(node);",
            "        }",
            "",
            "        return node;",
            "    }",
            "",
            "    // 递归插入",
            "    TreeNode* insertHelper(TreeNode* node, int value){",
            "        if (!node) {",
            "            return new TreeNode(value);",
            "        }",
            "",
            "        if (value < node->key) {",
            "            node->left = insertHelper(node->left, value);",
            "        } else if (value > node->key) {",
            "            node->right = insertHelper(node->right, value);",
            "        } else {",
            "            node->count++;",
            "            node->size++;",
            "            return node;",
            "        }",
            "",
            "        return balanceNode(node);",
            "    }",
            "",
            "    // 查找最小节点",
            "    TreeNode* findMinNode(TreeNode* node) const {",
            "        while (node && node->left) {",
            "            node = node->left;",
            "        }",
            "        return node;",
            "    }",
            "",
            "    // 递归删除",
            "    TreeNode* removeHelper(TreeNode* node, int value){",
            "        if (!node) return nullptr;",
            "",
            "        if (value < node->key) {",
            "            node->left = removeHelper(node->left, value);",
            "        } else if (value > node->key) {",
            "            node->right = removeHelper(node->right, value);",
            "        } else {",
            "            if (node->count > 1) {",
            "                node->count--;",
            "                node->size--;",
            "                return node;",
            "            }",
            "",
            "            if (!node->left || !node->right) {",
            "                TreeNode* temp = node->left ? node->left : node->right;",
            "                if (!temp) {",
            "                    delete node;",
            "                    return nullptr;",
            "                } else {",
            "                    *node = *temp;",
            "                    delete temp;",
            "                }",
            "            } else {",
            "                TreeNode* successor = findMinNode(node->right);",
            "                node->key = successor->key;",
            "                node->count = successor->count;",
            "                successor->count = 1;",
            "                node->right = removeHelper(node->right, successor->key);",
            "            }",
            "        }",
            "",
            "        return balanceNode(node);",
            "    }",
            "",
            "    // 递归查找",
            "    bool searchHelper(TreeNode* node, int value) const {",
            "        if (!node) return false;",
            "        if (value == node->key) return true;",
            "        if (value < node->key) return searchHelper(node->left, value);",
            "        return searchHelper(node->right, value);",
            "    }",
            "",
            "    // 递归中序遍历",
            "    void inorderHelper(TreeNode* node, std::vector<int>& result) const {",
            "        if (!node) return;",
            "        inorderHelper(node->left, result);",
            "        for (int i = 0; i < node->count; ++i) {",
            "            result.push_back(node->key);",
            "        }",
            "        inorderHelper(node->right, result);",
            "    }",
            "",
            "    // 递归查询排名",
            "    int rankHelper(TreeNode* node, int value) const {",
            "        if (!node) return 0;",
            "        ",
            "        if (value < node->key) {",
            "            return rankHelper(node->left, value);",
            "        } else if (value > node->key) {",
            "            return getSize(node->left) + node->count + rankHelper(node->right, value);",
            "        } else {",
            "            return getSize(node->left) + 1;",
            "        }",
            "    }",
            "",
            "    // 递归按排名查找",
            "    int selectHelper(TreeNode* node, int k) const {",
            "        if (!node) return -1;",
            "        ",
            "        int leftSize = getSize(node->left);",
            "        ",
            "        if (k <= leftSize) {",
            "            return selectHelper(node->left, k);",
            "        } else if (k <= leftSize + node->count) {",
            "            return node->key;",
            "        } else {",
            "            return selectHelper(node->right, k - leftSize - node->count);",
            "        }",
            "    }",
            "",
            "    // 递归释放所有节点",
            "    void clearHelper(TreeNode* node) {",
            "        if (!node) return;",
            "        clearHelper(node->left);",
            "        clearHelper(node->right);",
            "        delete node;",
            "    }",
            "",
            "public:",
            "    BalancedBST() : root(nullptr) {}",
            "",
            "    // 插入元素 - O(log n)",
            "    void insert(int value) {",
            "        root = insertHelper(root, value);",
            "    }",
            "",
            "    // 删除元素 - O(log n)",
            "    void remove(int value) {",
            "        root = removeHelper(root, value);",
            "    }",
            "",
            "    // 查找元素 - O(log n)",
            "    bool search(int value) const {",
            "        return searchHelper(root, value);",
            "    }",
            "",
            "    // 获取最小值 - O(log n)",
            "    int min() const {",
            "        TreeNode* node = findMinNode(root);",
            "        return node ? node->key : -1;",
            "    }",
            "",
            "    // 获取最大值 - O(log n)",
            "    int max() const {",
            "        TreeNode* node = root;",
            "        while (node && node->right) {",
            "            node = node->right;",
            "        }",
            "        return node ? node->key : -1;",
            "    }",
            "",
            "    // 中序遍历 - O(n)",
            "    std::vector<int> inorder() const {",
            "        std::vector<int> result;",
            "        inorderHelper(root, result);",
            "        return result;",
            "    }",
            "",
            "    // 查询排名 - O(log n)",
            "    int rank(int value) const {",
            "        return rankHelper(root, value);",
            "    }",
            "",
            "    // 按排名查找 - O(log n)",
            "    int select(int k) const {",
            "        return selectHelper(root, k);",
            "    }",
            "",
            "    // 清空整棵树",
            "    void clear() {",
            "        clearHelper(root);",
            "        root = nullptr;",
            "    }",
            "",
            "    // 获取树的大小 - O(1)",
            "    int size() const {",
            "        return getSize(root);",
            "    }",
            "",
            "    // 获取树的高度 - O(1)",
            "    int height() const {",
            "        return getHeight(root);",
            "    }",
            "};"
        ],
        "description": "插入 平衡树"
    }
}