我参照了OI wiki的代码,但是有2个疑问
1.在查找一个数的排名时,假如输入了一个比当前平衡树中所有数都大的数,那么最后一次会停留在最大值的结点上,然后再次往右走来到空结的,此时是否需要将这个最大值结点执行一次splay操作呢?
2.查找一个数的前驱元素时,OI WIKI的代码是这样做的: \
- 将这个数插入平衡树中
- 由于splay操作,这个数一定在根结点,查找根结点左子树中最右的元素,得到答案
- 将这个最右元素splay到根
- 删除原先插入的数
我的疑问是,既然删除操作本质上也是先将这个数splay到根,那么,第三步将最右元素splay到根是否有必要?毕竟接下来又要将这个数splay到根...那还不如直接就删除合并呢
求大佬解惑...