三月七树

· · 算法·理论

主要是一个有点乐子的数据结构，并不是最优解法。

更新：三月七树也可以维护序列（可以替代线段树，单次 \log n，还可以支持序列插入删除等，加上这个的复杂度为 \sqrt m）。

省流：一种基于暴力重构的平衡树。

优点：常数小，好写好调好理解。

缺点：在特定数据下复杂度差。

约定 n 为总元素个数，m 为总操作次数，B 为块长。

平衡树的一般操作可见这里。

我们注意到普通的二叉搜索树各操作的复杂度为 O(h)，h 为树高，各种平衡树只是通过很多操作保证了 h≈\log_2 n，但这些操作大多很复杂。在这里，引入一种基于分块的方便的处理方式。我将其称为“三月七树”。

我们记录当前树高 h。在执行操作 1 时，h 有概率变大。当 h\ge B 时， 我们将整棵树进行一次 DFS 。由于二叉排序树的性质，进行中序遍历的结果一定是排好序（从小到大）的，我们按照这个顺序将其记录下来。随后，对这个序列进行建树。考虑到（可能是我不知道）二叉排序树并没有什么快速建树的方法，我们对这个序列（依照有点类似树状数组的方式）建树，具体如下：

对于第 i 个元素，令其位于从下往上第 k 层（钦定叶子节点为 0），k 为满足 2^x|i 的最大整数。然后，若 k\le \log_2 n，向第 k+1 层没有同时拥有左右子结点的节点连边。若该节点不存在，分两种情况：若下一个 k+1 层的节点理应小于 n，向这个节点连边。否则，向第 k+2 层节点连，若仍不存在，再次重复上述判断。

下面是 n=17 时建出来的树。编号为这个元素的排名。

（9 和 11 号节点画反了，但是不太影响总体）

通过这种方式重构三月七树的复杂度为 O(n) 的。以下为证明：

显然，对于某个确定的 i，k 是可以 O(1) 求出的。向 k+1 层连边的复杂度为 O(1)。在我们首次向 k+2 层连边后，不可能再次向 k+1 层连边，因为在这种情况下，k+2 层的节点排名一定在 k+1 层之前，那么向上的过程是单调的。复杂度为 n+\log_2 n=O(n)。

重构后 h=\log_2 n。

其他操作与普通二叉树极度相似，不再赘述，同时因此三月七树的期望单次操作复杂度为 O(\log n)。

以下为最坏复杂度分析。

最坏情况下，输入单调。因此会出现最左（右）链特别长的情况。这种情况下单次操作最坏为 O(h)=O(B)，如果一直这么做，每 B-\log_2 n 次会进行一次重构。复杂度为 O(\dfrac{nm}{B-\log_2 n} +mB)，前一项为重构复杂度。取 B=\dfrac{n}{\sqrt m}+\log_2 n（或还可以取 \sqrt m 等），带入进去得到最坏复杂度 \dfrac{nm}{B-\log_2 n} +mB=m\sqrt m+m\sqrt m+m\log_2 n=O(m(\sqrt m+\log n))。够不到普通平衡树的水平，但是也达到分块了（还能简单的实现插入删除）。有点鸡肋，但是似乎有点用。大概可以稳定通过 n,m\leq 2\times 10^5 的构造数据。

或许子树内重构可能比整棵树重构更优达到更好的复杂度？有兴趣的朋友可以研究研究。