一种调试 线段树 / Treap / Splay / 左偏树 / LCT 等树形结构的技巧
前言
如果我们需要观察程序运行过程中，某一个变量、某一个序列的变化情况，你可以在修改的地方打断点 debug，或者直接在需要的地方输出就行了。
但是对于一些树形结构，我们不好将其直观地呈现出来，常常只是输出每一个结点的值，但是这就丢失了结点之间的连边情况。有时候不得不手动画图。
所以我们经常累死。
于是，为了让我们活着，我想到了一种轻量级的，在终端直观呈现树形结构的方法。
正文
经典例子
回顾如下场景：
- Windows 下命令行中，我们使用
tree
来观察目录结构。
比如，在某一目录下，使用
tree /A /F
的输出如下：
+---.vscode
| launch.json
|
+---blog-prettier
| LICENSE
| README.md
|
+---web server
| | checkstatues.log
| | client.html
| | data.txt
| | gen-key.py
| | main_service.log
| | script-obfsed.js
| | test.html
| |
| \---fetch-new-url
| | README.md
| |
| \---docs
| test
|
\---test
a.html
b.html
index.html
script.js
style.css
这种经典的方法显然可以运用到我们的调试中。
分析
二叉树
我们不妨来考虑简单的二叉树，例如线段树、Treap、Splay 等平衡树。
我们考虑一种最简单的递归过程，仅在参数中传递输出的前缀。简单码出以下代码：
void output(int x, string pre) {
cout << pre << "-" << x << ": " << tr[x].val << endl;
if (!x) return;
output(tr[x].son[1], pre + " |");
output(tr[x].son[0], pre + " |");
}
void output() {
output(root, ">");
}
这里先输出再
return
是为了让输出的二叉树更好看，不然遇到一个孩子不知道是左儿子还是右儿子。
将右儿子作为第一个儿子输出，是为了符合二叉查找树。
可能的输出：一棵不断插入的 Splay
>-1: 1
> |-0: 0
> |-0: 0
>-2: 1
> |-1: 1
> | |-0: 0
> | |-0: 0
> |-0: 0
>-3: 4
> |-0: 0
> |-1: 1
> | |-0: 0
> | |-2: 1
> | | |-0: 0
> | | |-0: 0
>-4: 5
> |-0: 0
> |-3: 4
> | |-0: 0
> | |-1: 1
> | | |-0: 0
> | | |-2: 1
> | | | |-0: 0
> | | | |-0: 0
>-5: 1
> |-3: 4
> | |-4: 5
> | | |-0: 0
> | | |-0: 0
> | |-2: 1
> | | |-1: 1
> | | | |-0: 0
> | | | |-0: 0
> | | |-0: 0
> |-0: 0
>-6: 4
> |-3: 4
> | |-4: 5
> | | |-0: 0
> | | |-0: 0
> | |-0: 0
> |-5: 1
> | |-1: 1
> | | |-0: 0
> | | |-2: 1
> | | | |-0: 0
> | | | |-0: 0
> | |-0: 0
这对于考场上调试来说已经足够了，仅需将头逆时针旋转
\(45^\circ\)
就能看到一棵完美的二叉树了。你可以在每个结点之后输出更多的信息。
但是，我们怎样达到更完美的效果呢，比如第二个孩子之前不输出树杈、第二个孩子后输出空行（多个第二个孩子仅输出一个空行）等等。
我们仅需多记录是否是第一个孩子即可。
void output(int x, string pre, bool firstSon) {
cout << pre << (firstSon ? "+" : "\\") << "---" << x << ": " << tr[x].val << endl;
if (!x) return;
pre += firstSon ? "|" : " ";
output(tr[x].son[1], pre + " ", true);
output(tr[x].son[0], pre + " ", false);
if (firstSon) cout << pre << endl;
}
void output() {
output(root, "", false);
}
效果见文末。
多叉树
多叉树就只能是 LCT 了吧，还有什么扭曲的树你必须要打印出来的？
虽然好像打印出来还是不方便调试……
我们加以改进，由于有了虚实链之分，我们在空节点不直接
return
，而是输出一条边。然后把是否是第一个孩子，变成是否是最后一个孩子。
代码：
vector<int> edge[N];
void output(int x, string pre, bool lastSon, bool real) {
cout << pre << (!lastSon ? "+" : "\\") << "---";
if (x) cout << x << ": " << tr[x].val << endl;
else cout << "null" << endl;
pre += !lastSon ? (real ? "|" : "`") : " ";
if (x && (tr[x].son[0] || tr[x].son[1] || edge[x].size())) {
pushdown(x);
output(tr[x].son[1], pre + " ", false, true);
output(tr[x].son[0], pre + " ", edge[x].empty(), false);
for (int y : edge[x])
output(y, pre + " ", y == edge[x].back(), false);
}
if (!lastSon) cout << pre << endl;
}
void output(int n) {
for (int i = 1; i <= n; ++i)
edge[i].clear();
for (int i = 1; i <= n; ++i)
if (isRoot(i))
edge[tr[i].fa].emplace_back(i);
cout << "==== LCT forest ====" << endl;
for (int i = 1; i <= n; ++i)
if (!tr[i].fa)
output(i, "", true, false);
cout << "====================" << endl;
}
效果见文末。
代码
二叉树
void output(int x, string pre, bool firstSon) {
cout << pre << (firstSon ? "+" : "\\") << "---" << x << ": " << tr[x].val << endl;
if (!x) return;
pre += firstSon ? "|" : " ";
output(tr[x].son[1], pre + " ", true);
output(tr[x].son[0], pre + " ", false);
if (firstSon) cout << pre << endl;
}
void output() {
output(root, "", false);
}
多叉树 LCT
vector<int> edge[N];
void output(int x, string pre, bool lastSon, bool real) {
cout << pre << (!lastSon ? "+" : "\\") << "---";
if (x) cout << x << ": " << tr[x].val << endl;
else cout << "null" << endl;
pre += !lastSon ? (real ? "|" : "`") : " ";
if (x && (tr[x].son[0] || tr[x].son[1] || edge[x].size())) {
pushdown(x);
output(tr[x].son[1], pre + " ", false, true);
output(tr[x].son[0], pre + " ", edge[x].empty(), false);
for (int y : edge[x])
output(y, pre + " ", y == edge[x].back(), false);
}
if (!lastSon) cout << pre << endl;
}
void output(int n) {
for (int i = 1; i <= n; ++i)
edge[i].clear();
for (int i = 1; i <= n; ++i)
if (isRoot(i))
edge[tr[i].fa].emplace_back(i);
cout << "==== LCT forest ====" << endl;
for (int i = 1; i <= n; ++i)
if (!tr[i].fa)
output(i, "", true, false);
cout << "====================" << endl;
}
输出效果
可能的输出：一棵不断插入的 Splay
\---1: 1
+---0: 0
\---0: 0
\---2: 1
+---1: 1
| +---0: 0
| \---0: 0
|
\---0: 0
\---3: 4
+---0: 0
\---1: 1
+---0: 0
\---2: 1
+---0: 0
\---0: 0
\---4: 5
+---0: 0
\---3: 4
+---0: 0
\---1: 1
+---0: 0
\---2: 1
+---0: 0
\---0: 0
\---5: 1
+---3: 4
| +---4: 5
| | +---0: 0
| | \---0: 0
| |
| \---2: 1
| +---1: 1
| | +---0: 0
| | \---0: 0
| |
| \---0: 0
|
\---0: 0
\---6: 4
+---3: 4
| +---4: 5
| | +---0: 0
| | \---0: 0
| |
| \---0: 0
|
\---5: 1
+---1: 1
| +---0: 0
| \---2: 1
| +---0: 0
| \---0: 0
|
\---0: 0
可能的输出：一棵带有左右边界的不断插入的 Treap
\---2: inf
+---0: 0
\---1: -inf
+---3: 1
| +---0: 0
| \---0: 0
|
\---0: 0
\---2: inf
+---0: 0
\---1: -inf
+---3: 1
| +---0: 0
| \---0: 0
|
\---0: 0
\---2: inf
+---0: 0
\---1: -inf
+---3: 1
| +---4: 4
| | +---0: 0
| | \---0: 0
| |
| \---0: 0
|
\---0: 0
\---2: inf
+---0: 0
\---1: -inf
+---3: 1
| +---5: 5
| | +---0: 0
| | \---4: 4
| | +---0: 0
| | \---0: 0
| |
| \---0: 0
|
\---0: 0
\---2: inf
+---0: 0
\---1: -inf
+---3: 1
| +---5: 5
| | +---0: 0
| | \---4: 4
| | +---0: 0
| | \---0: 0
| |
| \---0: 0
|
\---0: 0
\---2: inf
+---0: 0
\---1: -inf
+---3: 1
| +---5: 5
| | +---0: 0
| | \---4: 4
| | +---0: 0
| | \---0: 0
| |
| \---0: 0
|
\---0: 0
可能的输出：一棵不断插入的无旋 Treap
\---1: 1
+---0: 0
\---0: 0
\---1: 1
+---0: 0
\---2: 1
+---0: 0
\---0: 0
\---3: 4
+---0: 0
\---1: 1
+---0: 0
\---2: 1
+---0: 0
\---0: 0
\---3: 4
+---4: 5
| +---0: 0
| \---0: 0
|
\---1: 1
+---0: 0
\---2: 1
+---0: 0
\---0: 0
\---5: 1
+---3: 4
| +---4: 5
| | +---0: 0
| | \---0: 0
| |
| \---1: 1
| +---0: 0
| \---2: 1
| +---0: 0
| \---0: 0
|
\---0: 0
\---5: 1
+---6: 4
| +---3: 4
| | +---4: 5
| | | +---0: 0
| | | \---0: 0
| | |
| | \---0: 0
| |
| \---1: 1
| +---0: 0
| \---2: 1
| +---0: 0
| \---0: 0
|
\---0: 0
可能的输出：一棵动态开点线段树
\---[1, 5]: 1
+---[1, 3]: 0
\---[4, 5]: 1
+---[4, 4]: 0
\---[5, 5]: 1
\---[1, 5]: 6
+---[1, 3]: 0
\---[4, 5]: 6
+---[4, 4]: 0
\---[5, 5]: 6
\---[1, 5]: 10
+---[1, 3]: 0
\---[4, 5]: 10
+---[4, 4]: 4
\---[5, 5]: 6
\---[1, 5]: 12
+---[1, 3]: 2
| +---[1, 2]: 0
| \---[3, 3]: 2
|
\---[4, 5]: 10
+---[4, 4]: 4
\---[5, 5]: 6
\---[1, 5]: 15
+---[1, 3]: 5
| +---[1, 2]: 3 (with lazy = 3)
| | +---[1, 1]: 0
| | \---[2, 2]: 0
| |
| \---[3, 3]: 2
|
\---[4, 5]: 10
+---[4, 4]: 4
\---[5, 5]: 6
\---[1, 5]: 15
+---[1, 3]: 5
| +---[1, 2]: 3 (with lazy = 3)
| | +---[1, 1]: 0
| | \---[2, 2]: 0
| |
| \---[3, 3]: 2
|
\---[4, 5]: 10
+---[4, 4]: 4
\---[5, 5]: 6
\---[1, 5]: 19
+---[1, 3]: 5
| +---[1, 2]: 3 (with lazy = 3)
| | +---[1, 1]: 0
| | \---[2, 2]: 0
| |
| \---[3, 3]: 2
|
\---[4, 5]: 14
+---[4, 4]: 6
\---[5, 5]: 8
\---[1, 5]: 19
+---[1, 3]: 5
| +---[1, 2]: 3 (with lazy = 3)
| | +---[1, 1]: 0
| | \---[2, 2]: 0
| |
| \---[3, 3]: 2
|
\---[4, 5]: 14
+---[4, 4]: 6
\---[5, 5]: 8
\---[1, 5]: 24 (with lazy = 1)
+---[1, 3]: 5
| +---[1, 2]: 3 (with lazy = 3)
| | +---[1, 1]: 0
| | \---[2, 2]: 0
| |
| \---[3, 3]: 2
|
\---[4, 5]: 14
+---[4, 4]: 6
\---[5, 5]: 8
\---[1, 5]: 24 (with lazy = 1)
+---[1, 3]: 5
| +---[1, 2]: 3 (with lazy = 3)
| | +---[1, 1]: 0
| | \---[2, 2]: 0
| |
| \---[3, 3]: 2
|
\---[4, 5]: 14
+---[4, 4]: 6
\---[5, 5]: 8
可能的输出：一棵树状数组
这玩意你还要调试？
可能的输出：左偏树森林
==== 左偏树 1 ====
\---5: <4, 2>
+---3: <4, 3>
| +---4: <5, 2>
| | +---0: <0, 0>
| | \---7: <9, 4>
| | +---0: <0, 0>
| | \---0: <0, 0>
| |
| \---0: <0, 0>
|
\---0: <0, 0>
==== 左偏树 2 ====
\---1: <3, 3>
+---6: <8, 4>
| +---0: <0, 0>
| \---2: <9, 3>
| +---0: <0, 0>
| \---0: <0, 0>
|
\---0: <0, 0>
==== 左偏树 1 ====
\---5: <4, 2>
+---3: <4, 3>
| +---4: <5, 2>
| | +---0: <0, 0>
| | \---7: <9, 4>
| | +---0: <0, 0>
| | \---0: <0, 0>
| |
| \---0: <0, 0>
|
\---1: <5, 3>
+---6: <8, 4>
| +---0: <0, 0>
| \---2: <9, 3>
| +---0: <0, 0>
| \---0: <0, 0>
|
\---0: <0, 0>
==== 左偏树 1 ====
\---3: <4, 3>
+---4: <5, 2>
| +---0: <0, 0>
| \---7: <9, 4>
| +---0: <0, 0>
| \---0: <0, 0>
|
\---1: <5, 3>
+---6: <8, 4>
| +---0: <0, 0>
| \---2: <9, 3>
| +---0: <0, 0>
| \---0: <0, 0>
|
\---0: <0, 0>
==== 左偏树 1 ====
\---4: <5, 2>
+---1: <5, 3>
| +---6: <10, 4>
| | +---0: <0, 0>
| | \---2: <9, 3>
| | +---0: <0, 0>
| | \---0: <0, 0>
| |
| \---7: <11, 4>
| +---0: <0, 0>
| \---0: <0, 0>
|
\---0: <0, 0>
==== 左偏树 1 ====
\---1: <5, 3>
+---6: <10, 4>
| +---0: <0, 0>
| \---2: <9, 3>
| +---0: <0, 0>
| \---0: <0, 0>
|
\---7: <11, 4>
+---0: <0, 0>
\---0: <0, 0>
==== 左偏树 1 ====
\---6: <10, 4>
+---2: <11, 3>
| +---0: <0, 0>
| \---7: <11, 4>
| +---0: <0, 0>
| \---0: <0, 0>
|
\---0: <0, 0>
==== 左偏树 1 ====
\---2: <11, 3>
+---0: <0, 0>
\---7: <11, 4>
+---0: <0, 0>
\---0: <0, 0>
==== 左偏树 1 ====
\---7: <11, 4>
+---0: <0, 0>
\---0: <0, 0>
==== 左偏树 1 ====
\---0: <0, 0>
可能的输出：Link Cut Tree
==== LCT forest ====
\---1: 114
\---2: 514
\---3: 19
\---4: 19
\---5: 810
====================
link 1 and 2 success
==== LCT forest ====
\---2: 514
+---null
|
+---null
`
\---1: 114
\---3: 19
\---4: 19
\---5: 810
====================
cut 1 and 2 success
==== LCT forest ====
\---1: 114
\---2: 514
\---3: 19
\---4: 19
\---5: 810
====================
link 1 and 2 success
==== LCT forest ====
\---2: 514
+---null
|
+---null
`
\---1: 114
\---3: 19
\---4: 19
\---5: 810
====================
link 2 and 3 success
==== LCT forest ====
\---3: 19
+---null
|
+---null
`
\---2: 514
+---null
|
+---null
`
\---1: 114
\---4: 19
\---5: 810
====================
cut 1 and 3 failed
==== LCT forest ====
\---1: 114
+---2: 514
| +---3: 19
| |
| \---null
|
\---null
\---4: 19
\---5: 810
====================
link 1 and 3 failed
==== LCT forest ====
\---1: 114
+---3: 19
| +---null
| |
| \---2: 514
|
\---null
\---4: 19
\---5: 810
====================
link 4 and 5 success
==== LCT forest ====
\---1: 114
+---3: 19
| +---null
| |
| \---2: 514
|
\---null
\---5: 810
+---null
|
+---null
`
\---4: 19
====================
link 2 and 5 success
==== LCT forest ====
\---5: 810
+---null
|
+---null
`
+---2: 514
` +---1: 114
` |
` +---null
` `
` \---3: 19
`
\---4: 19
====================
modify value 5 to 233333 success
==== LCT forest ====
\---5: 233333
+---null
|
+---null
`
+---2: 514
` +---1: 114
` |
` +---null
` `
` \---3: 19
`
\---4: 19
====================
access 3 success
==== LCT forest ====
\---5: 233333
+---2: 514
| +---3: 19
| |
| +---null
| `
| \---1: 114
|
+---null
`
\---4: 19
====================
split 2 ~ 4 success
==== LCT forest ====
\---4: 19
+---null
|
\---5: 233333
+---null
|
\---2: 514
+---null
|
+---null
`
+---1: 114
`
\---3: 19
====================
split 2 ~ 5 success
==== LCT forest ====
\---5: 233333
+---null
|
+---2: 514
` +---null
` |
` +---null
` `
` +---1: 114
` `
` \---3: 19
`
\---4: 19
====================