Skip to content

11560: 【原1560】BST

题目

题目描述

author: try-skycn 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1560

Description

给定一些在集合中添加元素、删除元素、查找元素的操作，要求用二叉查找树进行维护。用于维护集合的二叉查找树为传统的二叉查找树，不应进行平衡性维护。

如若添加已存在的元素或删除不存在的元素，则该操作不应产生影响。

对删除操作的约定：若要删除的节点为n，若n没有右子树，则n被其左子树替代，若n有右子树，其右子树的最小元素的节点为x，则n被x替代，x被x的右孩子替代。

Input Format

第一行一个整数\(Q\)，表示操作个数。

接下来\(Q\)行，每行一个操作。

  • + x表示添加元素x。
  • - x表示删除元素x。
  • * x表示查找元素x。

以上x均为正整数。

Output Format

对于查找操作，输出从根开始寻找到这个元素的路径，格式为：

开头一个字符*，之后从根开始，若元素在左子树中，则添加l，若在右子树中，则添加r。

如果元素未被查找到，输出Nothing.

Sample Input

10
+ 1
+ 2
+ 3
+ 4
* 3
* 4
* 2
* 1
- 1
* 1

Sample Output

*rr
*rrr
*r
*
Nothing.

Limits

对于\(100\%\)的数据，有\(x<2^{30}\)。

对于\(40\%\)的数据，有\(Q\leq100\)。

对于\(70\%\)的数据，有\(Q\leq10^4\)。

对于\(100\%\)的数据，有\(Q\leq10^5\)。

ligongzzz's solution 

#include "iostream"
#include "cstdio"
#include "cstring"
#include "cmath"
using namespace std;

char ans[100009] = { 0 };

class bst {
public:
    class node {
    public:
        int val = 0;
        node* lchild = nullptr, * rchild = nullptr;
        node* parent = nullptr;
    };
    node* root = nullptr;

    void find(const int& val) {
        memset(ans, 0, sizeof(ans));
        int length = 0;
        ans[length++] = '*';
        for (auto p = root; p;) {
            if (p->val == val) {
                printf("%s\n", ans);
                return;
            }
            else if (val < p->val) {
                ans[length++] = 'l';
                p = p->lchild;
            }
            else {
                ans[length++] = 'r';
                p = p->rchild;
            }
        }
        printf("Nothing.\n");
    }

    void insert(const int& val) {
        if (!root) {
            root = new node;
            root->val = val;
            return;
        }
        //寻找
        auto p = root;
        for (; p;) {
            if (p->val == val)
                return;
            if (val < p->val) {
                if (p->lchild)
                    p = p->lchild;
                else {
                    p->lchild = new node;
                    p->lchild->parent = p;
                    p = p->lchild;
                    break;
                }
            }
            else {
                if (p->rchild)
                    p = p->rchild;
                else {
                    p->rchild = new node;
                    p->rchild->parent = p;
                    p = p->rchild;
                    break;
                }
            }
        }
        //增加
        p->val = val;
    }

    void erase(const int& val) {
        auto p = root;
        for (; p;) {
            if (p->val == val) {
                //如果是叶子结点则直接删除
                if (!p->lchild && !p->rchild) {
                    if (p == root)
                        root = nullptr;
                    else if (p->parent->lchild == p)
                        p->parent->lchild = nullptr;
                    else
                        p->parent->rchild = nullptr;
                    delete p;
                }
                //如果只有左孩子
                else if (p->lchild && !p->rchild) {
                    if (p == root) {
                        root = p->lchild;
                        p->lchild->parent = nullptr;
                    }
                    else if (p->parent->lchild == p) {
                        p->parent->lchild = p->lchild;
                        p->lchild->parent = p->parent;
                    }
                    else {
                        p->parent->rchild = p->lchild;
                        p->lchild->parent = p->parent;
                    }
                    delete p;
                }
                //如果有右孩子
                else if (p->rchild) {
                    auto q = p->rchild;
                    for (; q->lchild; q = q->lchild);
                    p->val = q->val;
                    if (q->parent->lchild == q)
                        q->parent->lchild = q->rchild;
                    else
                        q->parent->rchild = q->rchild;
                    if (q->rchild)
                        q->rchild->parent = q->parent;
                    delete q;
                }
                return;
            }
            else if (val < p->val)
                p = p->lchild;
            else
                p = p->rchild;
        }
    }
};

bst my_bst;

int main() {
    int n;
    scanf("%d", &n);

    for (int i = 0; i < n; ++i) {
        char op;
        int temp;
        scanf("\n%c %d", &op, &temp);
        if (op == '+') {
            my_bst.insert(temp);
        }
        else if (op == '-') {
            my_bst.erase(temp);
        }
        else {
            my_bst.find(temp);
        }
    }

    return 0;
}

q4x3's solution 

/**
 * 我恨二叉搜索树
 * 会恨一辈子的
 **/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>

struct node {
    int data;
    node *left, *right;
    node(int dt):data(dt), left(nullptr), right(nullptr) {}
};

void find(node* rt, int key, char* ans) {
    if(rt == nullptr) {
        strcpy(ans, "Nothing.");
        return;
    }
    if(rt->data == key) {
        return;
    } else if(rt->data < key) {
        strcat(ans, "r");
        find(rt->right, key, ans);
    } else {
        strcat(ans, "l");
        find(rt->left, key, ans);
    }
}

void insert(node* &rt, int p) {
    if(rt == nullptr) {
        rt = new node(p);
    } else if(rt->data < p) {
        insert(rt->right, p);
    } else if(rt->data > p) {
        insert(rt->left, p);
    }
}

void dele(node* &rt) {
    rt->left = rt->left->right;
}

void del(node* &rt, int key) {
    if(rt == nullptr) return;
    if(rt->data < key) {
        del(rt->right, key);
        return;
    } else if(rt->data > key) {
        del(rt->left, key);
        return;
    }
    if(rt->right == nullptr) {
        rt = rt->left;
    } else {
        node* tmp = rt->right;
        if(tmp->left == nullptr) {
            rt->right->left = rt->left;
            rt = rt->right;
            return;
        }
        while(tmp->left->left) tmp = tmp->left;
        rt->data = tmp->left->data;
        dele(tmp);
    }
}

node *root;
char op[3], ans[100233];
int x, Q;

int main() {
    freopen("a.in", "r", stdin);
    freopen("b.out", "w", stdout);
    scanf("%d", &Q);
    for(int i = 1;i <= Q;++ i) {
        scanf("%s", op);
        scanf("%d", &x);
        if(op[0] == '+') {
            insert(root, x);
        } else if(op[0] == '-') {
            del(root, x);
        } else {
            strcpy(ans, "*");
            find(root, x, ans);
            printf("%s\n", ans);
        }
    }
}

victrid's solution 

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
struct node {
    long long value;
    node* left;
    node* right;
};
class BST {
public:
    node* __root;
    node* query(node* root, long long& to_query) {
        if (root == nullptr)
            return nullptr;
        if (root->value == to_query)
            return root;
        if (root->value > to_query) {
            return query(root->left, to_query);
        }
        if (root->value < to_query) {
            return query(root->right, to_query);
        }
        return nullptr;
    }
    node* queriy(node* root, long long& to_query, char*& buffer) {
        if (root == nullptr)
            return nullptr;
        if (root->value == to_query)
            return root;
        if (root->value > to_query) {
            sprintf(buffer, "l");
            buffer++;
            return queriy(root->left, to_query, buffer);
        }
        if (root->value < to_query) {
            sprintf(buffer, "r");
            buffer++;
            return queriy(root->right, to_query, buffer);
        }
        return nullptr;
    }
    int insert(node*& root, long long& to_insert) {
        if (root == nullptr) {
            root = new node{to_insert, nullptr, nullptr};
            return 0;
        }
        if (root->value < to_insert)
            insert(root->right, to_insert);
        else if (root->value > to_insert)
            insert(root->left, to_insert);
        else
            return 0;
        return 0;
    }
    node* erasemin(node*& root) {
        if (root == nullptr)
            return nullptr;
        node* to_erase;
        if (root->left == nullptr) {
            to_erase = root;
            root     = root->right;
        } else {
            return erasemin(root->left);
        }
        return to_erase;
    }

    int erase(node*& root, long long& to_delete) {
        if (root == nullptr)
            return -1;
        if (root->value < to_delete)
            erase(root->right, to_delete);
        else if (root->value > to_delete)
            erase(root->left, to_delete);
        else if (root->value == to_delete) {
            node* rr = root;
            if (root->right == nullptr && root->left == nullptr) {
                root = nullptr;
            } else if (root->right == nullptr) {
                root = root->left;
            } else {
                node*& pp   = root->right;
                node* bl    = root->left;
                root        = erasemin(root->right);
                root->right = pp;
                root->left  = bl;
            }
            delete rr;
        }
        return 0;
    }
    BST() : __root(nullptr){};
};

int main() {
    int n;
    long long op;
    char ch;
    char buffer[10000];
    BST b;
    scanf("%d", &n);
    while (n--) {
        scanf("\n%c %lld", &ch, &op);
        switch (ch) {
        case '+':
            b.insert(b.__root, op);
            break;
        case '-':
            b.erase(b.__root, op);
            break;
        case '*':
            char* buf = buffer;
            sprintf(buf, "*");
            buf++;
            void* j = b.queriy(b.__root, op, buf);
            sprintf(buf, "\n");
            buf++;
            *buf = '\0';
            if (j == nullptr) {
                printf("Nothing.\n");
            } else {
                printf("%s", buffer);
            }
            break;
        }
    }
    return 0;
}