Skip to content

14364: 【原4364】Chika and BST

题目

题目描述

author: Li Zitong 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4364

Description

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

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

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

Input Format

第一行一个整数 Q (1 <= Q <= 100000),表示操作个数。

接下来 Q 行,每行一个操作。

0 x表示添加元素x (1 <= x <= 200000, 且为整数)。

1 x表示删除所有小于等于x的元素 (1 <= x <= 200000, 且为整数)。

2 表示按照先序遍历顺序输出当前二叉查找树中的所有元素。

保证 2 操作不超过 30 个。

Output Format

对于每次 2 操作,输出一行整数,用空格分隔,表示按照先序遍历输出的当前二叉查找树中的所有元素。

若当前二叉查找树为空,则应单独输出一行字符串 Empty 。

Sample Input 1

9
0 4
0 2
0 3
0 5
2
1 2
2
1 4
2

Sample Output 1

4 2 3 5
4 3 5
5

Sample Input 2

7
0 2
0 3
0 4
1 6
2
0 10
2

Sample Output 2

Empty
10

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!