有一个名为treap的数据结构:这是一个随机二进制搜索树,它也是随机生成的所谓"优先级"的堆.
这种结构存在一种变体,其中键是隐式的,它们不存储在树中,但我们将树中节点的有序索引视为此节点的键.我们需要在每个节点中存储子树的大小而不是密钥.这种技术使我们能够像某种数组一样思考treap,它在O(log N)时间内支持大量操作:子数组的插入,删除,恢复,间隔的变化等等.
我对这种结构有点了解,但没有那么多.我试图谷歌它,但我发现很多关于treap本身的文章,但没有关于这个"隐含的treap"/"索引列表".我甚至不知道它的名字,因为我的母语不是英语,我听过的讲座使用的是结构的本土术语,而不是英文原始术语.这个原生术语可以直接用英语翻译为"隐式键上的Treap"或"隐式键上的笛卡尔树".
任何人都能指出我关于这个结构的文章或告诉我它的原始名称吗？谢谢.
PS对不起,如果我的英语不够容易理解.
UPD:关于我正在寻找的结构的一些额外解释.
考虑使用随机选择的优先级和密钥的常用treap,它们是存储在树中的实际用户数据.然后让我们假设我们在每个节点中都存储了一些其他用户信息,而键只是搜索键.下一步是计算和维护每个节点中的子树大小:我们必须在每次合并/拆分/添加/删除后更新此参数,但它允许我们在O(log N)中查找树的第K个元素时间.
当我们在每个节点中有子树大小时,我们可以抛弃键并想象treap表示inorder遍历中的用户数据数组.可以从子树大小容易地计算每个元素的数组索引.现在我们可以添加/删除数组中间的元素或拆分此数组 - 所有这些都在O(log N)时间内完成.
我们也可以进行"多重"操作 - 例如,为我们的"数组"的所有元素添加一个常量值.为了实现这一点,我们必须延迟此操作,在每个节点中添加一个参数,该参数表示延迟常量,必须"稍后"添加到此节点的子阵列的所有元素,并将更改"推"到必要.向子阵列添加常量或绘制(标记)子阵列可以通过这种方式延迟,因为反转子阵列(此处节点中的延迟信息位"子阵列必须反转"),依此类推.
UPD2:这是代码片段 - 我发现的一小部分信息.不要注意西里尔语:)单词"снеявнымключом"的意思是直接翻译"with implicit key".