Skip to content

1146: BST

题目

题目描述

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

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

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

输入格式

第一行一个整数$Q$,表示操作个数。

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

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

以上x均为正整数。

输出格式

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

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

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

样例输入

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

样例输出

*rr
*rrr
*r
*
Nothing.

数据范围

对于100%的数据,有$x<2^{30}$。

对于40%的数据,有$Q\leq100$。

对于70%的数据,有$Q\leq10^4$。

对于100%的数据,有$Q\leq10^5$。

Oops! 本题目还没有解答!

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

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

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