二叉查找树的建树优化
思路
按照题意建立二叉查找树，直接按先序遍历。
这是朴素的建树方式插入一个数 \(x\) 的操作：
-
如果树为空，直接新建一个节点，权值为 \(x\)。
-
如果树不为空，从根节点开始遍历，令当前遍历到的节点为 \(p\)，若 \(x\) 的权值比 \(p\) 小，则令 \(p\) 转移到 \(p\) 的左儿子，否则转移到 \(p\) 的右儿子。
-
重复操作 \(2\) 直到 \(p\) 表示一个空节点，将这个节点的权值赋为 \(x\)。
朴素建树代码
void insert(int x) {
if (!idt) {
t[++idt] = {0, 0, x};
return;
}
int p = 1;
while (p) {
if (x < t[p].val) {
if (!t[p].ls)
break;
p = t[p].ls;
} else {
if (!t[p].rs)
break;
p = t[p].rs;
}
}
if (x < t[p].val) {
t[p].ls = ++idt;
t[idt].val = x;
} else {
t[p].rs = ++idt;
t[idt].val = x;
}
}
上面代码的平均复杂度为 \(O(\log n)\)，但当 \(a_i\) 有单调性时，二叉查找树会退化成一条链，insert 的复杂度退化成 \(O(n)\)。
考虑优化 insert。
可以发现根本没必要从根节点开始遍历，因为 \(x\) 最终只可能插到这两个位置：
-
权值比 \(x\) 大的权值最小的节点的左儿子。
-
权值比 \(x\) 小的权值最大的节点的右儿子。
这两个东西都可以用 set 维护。
把 \(x\) 放到任意一个有空的位置即可。
注意，朴素遍历方式会优先放位置 \(1\)，因此在这题要优先放位置 \(1\)。
代码
#include <bits/stdc++.h>
using namespace std;
int n, idt, a[100005];
set<pair<int, int>> p;
set<pair<int, int>>::iterator it;
struct node {
int ls, rs, val;
} t[100005];
void insert(int x) {
if (!idt) {
t[++idt] = {0, 0, x};
p.insert({x, 1});
return;
}
it = p.lower_bound({x, 0});
if (it == p.end() || t[(*it).second].ls)
it--, t[(*it).second].rs = ++idt, t[idt].val = x;
else
t[(*it).second].ls = ++idt, t[idt].val = x;
p.insert({x, idt});
}
void dfs(int p) {
cout << t[p].val << ' ';
if (t[p].ls)
dfs(t[p].ls);
if (t[p].rs)
dfs(t[p].rs);
}
int main() {
cin >> n;
for (int i = 1, x; i <= n; i++) {
cin >> x;
insert(x);
}
dfs(1);
return 0;
}