题目描述 给定一些在集合中添加元素、删除元素、查找元素的操作，要求用二叉查找树进行维护。用于维护集合的二叉查找树为传统的二叉查找树，不应进行平衡性维护。 如若添加已存在的元素或删除不存在的元素，则该操作不应产生影响。 对删除操作的约定：若要删除的节点为n，若n没有右子树，则n被其左子树替代，若n有右子树，其右子树的最小元素的节点为x，则n被x替代，x被x的右孩子替代。 输入格式 第一行一个整数 Q，表示操作个数。 接下来 Q行，每行一个操作。 + x表示添加元素x。 - x表示删除元素x。 * x表示查找元素x。 以上x均为正整数。 输出格式 对于查找操作，输出从根开始寻找到这个元素的路径，格式为： 开头一个字符*，之后从根开始，若元素在左子树中，则添加l，若在右子树中，则添加r。 如果元素未被查找到，换行输出Nothing.使用C++语言，多使用递归

以下是一个参考代码，使用了递归实现：

#include <iostream>

using namespace std;

const int N = 100010;

int n;
int w[N], l[N], r[N], idx;

int build(int l, int r) // 构建二叉查找树
{
    if (l > r) return 0;
    int root = ++idx;
    int mid = l + r >> 1;
    w[root] = mid;
    l[root] = build(l, mid - 1);
    r[root] = build(mid + 1, r);
    return root;
}

void insert(int root, int x) // 向二叉查找树中插入元素
{
    if (x == w[root]) return;
    if (x < w[root])
    {
        if (!l[root]) l[root] = ++idx, w[l[root]] = x;
        else insert(l[root], x);
    }
    else
    {
        if (!r[root]) r[root] = ++idx, w[r[root]] = x;
        else insert(r[root], x);
    }
}

int query(int root, int x) // 在二叉查找树中查找元素
{
    if (!root) return -1;
    if (w[root] == x) return root;
    if (x < w[root]) return query(l[root], x);
    else return query(r[root], x);
}

void delete_node(int root, int x) // 在二叉查找树中删除元素
{
    if (!root) return;
    if (w[root] == x)
    {
        if (!l[root] && !r[root]) w[root] = 0;
        else if (r[root])
        {
            int p = r[root];
            while (l[p]) p = l[p];
            w[root] = w[p];
            delete_node(r[root], w[p]);
        }
        else
        {
            int p = l[root];
            while (r[p]) p = r[p];
            w[root] = w[p];
            delete_node(l[root], w[p]);
        }
    }
    else if (x < w[root]) delete_node(l[root], x);
    else delete_node(r[root], x);
}

void output(int root, int x) // 输出查找元素的路径
{
    if (w[root] == x)
    {
        cout << "*\n";
        return;
    }
    if (x < w[root]) cout << "l";
    else cout << "r";
    if (x < w[root]) output(l[root], x);
    else output(r[root], x);
}

int main()
{
    cin >> n;
    int root = build(1, n);
    while (n -- )
    {
        char op;
        int x;
        cin >> op >> x;
        if (op == '+') insert(root, x);
        else if (op == '-') delete_node(root, x);
        else 
        {
            int res = query(root, x);
            if (res == -1) cout << "Nothing\n";
            else output(root, x), cout << endl;
        }
    }
    return 0;
}

时间复杂度：

- 插入操作的时间复杂度为 $O(h)$，其中 $h$ 为二叉查找树的高度，最坏情况下为 $O(n)$。
- 查询操作的时间复杂度为 $O(h)$，其中 $h$ 为二叉查找树的高度，最坏情况下为 $O(n)$。
- 删除操作的时间复杂度为 $O(h)$，其中 $h$ 为二叉查找树的高度，最坏情况下为 $O(n)$。

因此，总时间复杂度为 $O(nh)$，最坏情况下为 $O(n^2)$。