Skip to content

1185: BST

题目

题目描述

实现二叉查找树,支持插入,查找,删除,查找第 i 小的元素,删除大于 a 且小于 b 的所有元素:

输入格式

第 1 行: 一个数, n, 表示总操作个数。 接下来 n 行: 每行首先一个单词, 表示操作的名称, 这一行接下来的格式每种操作不同:

  • "insert": 插入, 接下来一个整数, x, 表示被插入的元素
  • "find": 查找, 接下来一个整数, x, 表示被查找的元素
  • "delete": 删除, 接下来一个整数, x, 表示被删除的元素(若树中有重复删除任意一个)
  • "find_ith": 查找第 i 小的元素, 接下来一个整数, i
  • "delete_interval": 删除大于 a 且小于 b 的所有元素, 接下来两个整数, a, b

输出格式

其中对于 "find" 操作,输出 Y/N,表示是否查找到询问的元素。 对于 "find_ith" 操作,输出第 i 小的元素值,若不存在输出 N。 注意: 对于数列 1, 2, 2, 3, 我们认为第 1 小的元素是 1, 第 2 小的元素是 2, 第 3 小的元素还是 2, 第 4 小的元素是 3

样例输入

20 insert 1863 insert 1513 delete 1863 find 1863 insert 291 delete_interval 1697 2739 insert -4249 insert -4105 find_ith 3 insert 8169 delete 1513 insert 7225 find_ith 4 delete -4105 delete 8169 insert 7543 find 7543 delete 7543 delete -4249 find_ith 1

样例输出

N 291 7225 Y 291

数据范围

保证任意时刻树中元素不超过 5000 个,操作数小于300000

Oops! 本题目还没有解答!

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

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

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