一种调试 线段树 / 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.val << endl; if (!x) return; output(tr.son, pre + " |"); output(tr.son, 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.val << endl; if (!x) return; pre += firstSon ? "|" : " "; output(tr.son, pre + " ", true); output(tr.son, pre + " ", false); if (firstSon) cout << pre << endl;}void output() { output(root, "", false);}效果见文末。
多叉树
多叉树就只能是 LCT 了吧，还有什么扭曲的树你必须要打印出来的？
虽然好像打印出来还是不方便调试……
我们加以改进，由于有了虚实链之分，我们在空节点不直接 return，而是输出一条边。然后把是否是第一个孩子，变成是否是最后一个孩子。
代码：
vector<int> edge;void output(int x, string pre, bool lastSon, bool real) { cout << pre << (!lastSon ? "+" : "\\") << "---"; if (x) cout << x << ": " << tr.val << endl; else cout << "null" << endl; pre += !lastSon ? (real ? "|" : "`") : " "; if (x && (tr.son || tr.son || edge.size())) { pushdown(x); output(tr.son, pre + " ", false, true); output(tr.son, pre + " ", edge.empty(), false); for (int y : edge) output(y, pre + " ", y == edge.back(), false); } if (!lastSon) cout << pre << endl;}void output(int n) { for (int i = 1; i <= n; ++i) edge.clear(); for (int i = 1; i <= n; ++i) if (isRoot(i)) edge.fa].emplace_back(i); cout << "==== LCT forest ====" << endl; for (int i = 1; i <= n; ++i) if (!tr.fa) output(i, "", true, false); cout << "====================" << endl;}效果见文末。
代码
二叉树void output(int x, string pre, bool firstSon) { cout << pre << (firstSon ? "+" : "\\") << "---" << x << ": " << tr.val << endl; if (!x) return; pre += firstSon ? "|" : " "; output(tr.son, pre + " ", true); output(tr.son, pre + " ", false); if (firstSon) cout << pre << endl;}void output() { output(root, "", false);}多叉树 LCTvector<int> edge;void output(int x, string pre, bool lastSon, bool real) { cout << pre << (!lastSon ? "+" : "\\") << "---"; if (x) cout << x << ": " << tr.val << endl; else cout << "null" << endl; pre += !lastSon ? (real ? "|" : "`") : " "; if (x && (tr.son || tr.son || edge.size())) { pushdown(x); output(tr.son, pre + " ", false, true); output(tr.son, pre + " ", edge.empty(), false); for (int y : edge) output(y, pre + " ", y == edge.back(), false); } if (!lastSon) cout << pre << endl;}void output(int n) { for (int i = 1; i <= n; ++i) edge.clear(); for (int i = 1; i <= n; ++i) if (isRoot(i)) edge.fa].emplace_back(i); cout << "==== LCT forest ====" << endl; for (int i = 1; i <= n; ++i) if (!tr.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 +---: 0 \---: 1 +---: 0 \---: 1\---: 6 +---: 0 \---: 6 +---: 0 \---: 6\---: 10 +---: 0 \---: 10 +---: 4 \---: 6\---: 12 +---: 2 | +---: 0 | \---: 2 | \---: 10 +---: 4 \---: 6\---: 15 +---: 5 | +---: 3 (with lazy = 3) | | +---: 0 | | \---: 0 | | | \---: 2 | \---: 10 +---: 4 \---: 6\---: 15 +---: 5 | +---: 3 (with lazy = 3) | | +---: 0 | | \---: 0 | | | \---: 2 | \---: 10 +---: 4 \---: 6\---: 19 +---: 5 | +---: 3 (with lazy = 3) | | +---: 0 | | \---: 0 | | | \---: 2 | \---: 14 +---: 6 \---: 8\---: 19 +---: 5 | +---: 3 (with lazy = 3) | | +---: 0 | | \---: 0 | | | \---: 2 | \---: 14 +---: 6 \---: 8\---: 24 (with lazy = 1) +---: 5 | +---: 3 (with lazy = 3) | | +---: 0 | | \---: 0 | | | \---: 2 | \---: 14 +---: 6 \---: 8\---: 24 (with lazy = 1) +---: 5 | +---: 3 (with lazy = 3) | | +---: 0 | | \---: 0 | | | \---: 2 | \---: 14 +---: 6 \---: 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====================
页:
[1]