使用FHQTreap,AC但是疑惑

P3391 【模板】文艺平衡树

Bodhi @ 2022-12-18 23:57:12

Q1:请问为什么将这棵树中序遍历出来就是结果?

Q2:既然是用随机值维护索引,为什么还能维护二叉搜索树的性质呢(也就是说所谓的“维护二叉搜索树的性质”维护的是什么,是结点的值还是结点的索引)


by Tangent233 @ 2022-12-19 00:03:23

@Bodhi 1:因为它的下标满足bst 2:下标bst 索引满足堆,这两个是不同的概念


by Bodhi @ 2022-12-21 20:31:43

@Tangent233 大概明白了,谢谢


|