区间翻转后不满足左小右大，为什么能用此方法

BlankAo @ 2021-09-02 07:21:02

by BlankAo @ 2021-09-02 07:24:16

换言之，为什么 r+1 的儿子还是区间 [l,r] 间的数字

by Echidna @ 2021-09-02 07:27:36

@BlankAo 因为你交换左右儿子并且打标记的是 r+1 的左儿子。

by BlankAo @ 2021-09-02 07:29:18

@某学oi的蒟蒻 但是在进行若干次翻转操作后， r+1 可能不满足左儿子小的性质？

by DPair @ 2021-09-02 07:31:21

文艺平衡树利用的是二叉搜索树先序遍历为原树这个性质

你发现你区间翻转后先序遍历刚好就是这段区间翻转了

和什么左小右大没什么关系，真要说的话你可以看成下标左小右大

by Echidna @ 2021-09-02 07:31:54

@BlankAo 这棵平衡树它是按照节点在序列中的位置来排序的啊，不是按照节点的在序列中的值来排序的，所以不存在 r+1 不满足左儿子小的性质的情况。

by Echidna @ 2021-09-02 07:32:23

@DPair 中序遍历吧……

by DPair @ 2021-09-02 07:34:12

@某学oi的蒟蒻 等下，确定不是先序遍历？

by DPair @ 2021-09-02 07:34:35

不是左中右吗？

by Echidna @ 2021-09-02 07:34:49

@DPair 确信

by Echidna @ 2021-09-02 07:35:08

@DPair 这不就是中序遍历吗？/yiw