更简单的优化二叉搜索树方法

· · 算法·理论

省流

注意到对于二叉搜索树的优化，平衡树是一个显而易见的优化方式，但是平衡树还是太难写了，于是我们决定制造另一种优化方式。

朴素二叉搜索树的缺点

链太长了，容易导致退化，形成长度为 n 的链时时间复杂度为 O(n^2)。

如何修改这个缺点

注意到链太长是因为值域过大，而节点过于有序，所以时间复杂度变多。

定义值域为 W，n 次操作。

所以先建一个底层有 K 个节点的完全二叉树，时间复杂度为 O(K) ,这样每个叶子节点有的值域就是 \frac{W}{K}。

那么吃满一个叶子结点的时间复杂度为 O(\frac{W^2}{K^2}) , 需要 \frac{W}{K} 次操作。

那么总时间复杂度为

O(\frac{W^2}{K^2}\times \frac{n}{\frac{W}{K}}+K+n\log K )=O(\frac{Wn}{K}+K+n\log K)

因此当 K 取到 \sqrt{Wn} 时时间复杂度最低。

所以时间复杂度为 O(\sqrt{Wn}+N\log\sqrt{Wn }).

继续优化，考虑上面的满层二叉树的叶子结点的作用仅仅是区分大小，那么考虑不建这个树，直接在插入时判断应该插到哪儿。

时间复杂度优化为 O(\sqrt{Wn}) 。

恭喜你，发明了值域分块。

继续优化，学习线段树，考虑到多次分块可能更优，但值域 4W 个节点开不下，那么考虑动态开点线段树，使得复杂度就是 O(n\log W) 。

在 W\le n 时有用？

后记：没 P 用开个桶就行了。