#17936. Splay树
Splay树
题目背景
这一天,出题人 five_rice_water 在出题的时候看到了这样一个神奇的数据结构,并且想要用这个东西出一道题为难一下大家。
题目背景
Splay 的定义如下。
splay tree,中文名伸展树。
其是一种自平衡二叉排序树,通过其特有的splay操作,可以使得整棵树在维持二叉排序树性质的情况下,又不至于退化为链。
splay树支持对数据进行查询、插入、删除等操作,且各操作的时间复杂度摊还后皆是 ,是一种相对高效的数据结构。
Splay树并不在乎二叉排序树是否时刻平衡,而是通过在每次操作时进行微调来使得树趋于平衡。
每当我们对二叉排序树进行一次操作(查询、插入、删除等)时,我们就将操作的节点通过旋转操作挪到根节点上,并且使得整棵树依旧满足二叉排序树的性质,这一系列过程我们称之为splay操作。
splay操作不单单是将操作节点挪到根节点,还将从原根节点到操作节点路径上的所有节点都进行了一次优化,使得其深度缩减,通过这一方法来使得二叉排序树不至于退化为链。
此时 five_rice_water 突发奇想,希望你能根据以上定义,解决一下这个问题:
- 给你两个整数 , 输出 的值。
输入格式
一行两个整数 。
输出格式
一行一个整数 。
2 3
5
数据范围
对于 的数据,保证