# 11560: 【原1560】BST

### 题目描述

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

# Description

## Input Format

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

## Sample Input

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


## Sample Output

*rr
*rrr
*r
*
Nothing.


## 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;
}