9858: 二叉搜索树 —— 3. 二叉排序树
[Creator : ]
Description
你需要写一种数据结构,来维护一些数,其中需要提供以下操作:
- 插入数值 x。
- 删除数值 x。
- 输出数值 x 的前驱,前驱定义为现有所有数中小于 x 的最大的数。
- 输出数值 x 的后继,后继定义为现有所有数中大于 x 的最小的数。
题目保证:
- 操作 1 插入的数值各不相同。
- 操作 2 删除的数值一定存在。
- 操作 3 和 4 的结果一定存在。
Input
第一行包含整数 n,表示共有 n 个操作命令。
接下来 n 行,每行包含两个整数 opt 和 x,表示操作序号和操作数值。
Output
对于操作 3,4,每行输出一个操作结果。
Constraints
$1≤n≤2,000$
$−10000≤x≤10000$
$−10000≤x≤10000$
Sample 1 Input
6
1 1
1 3
1 5
3 4
2 3
4 2
Sample 1 Output
3
5