Go...

当前位置: 首页>>世界杯冠军魔咒

一种调试 线段树 / Treap / Splay / 左偏树 / LCT 等树形结构的技巧

前言

如果我们需要观察程序运行过程中,某一个变量、某一个序列的变化情况,你可以在修改的地方打断点 debug,或者直接在需要的地方输出就行了。

但是对于一些树形结构,我们不好将其直观地呈现出来,常常只是输出每一个结点的值,但是这就丢失了结点之间的连边情况。有时候不得不手动画图。

所以我们经常累死。

于是,为了让我们活着,我想到了一种轻量级的,在终端直观呈现树形结构的方法。

正文

经典例子

回顾如下场景:

Windows 下命令行中,我们使用 tree 来观察目录结构。

比如,在某一目录下,使用 tree /A /F 的输出如下:

/* by yours.tools - online tools website : yours.tools/zh/formatpy.html */

+---.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 等平衡树。

我们考虑一种最简单的递归过程,仅在参数中传递输出的前缀。简单码出以下代码:

/* by yours.tools - online tools website : yours.tools/zh/formatpy.html */

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 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 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

====================

本文作者:XuYueming,转载请注明原文链接:https://www.cnblogs.com/XuYueming/p/18656288。

若未作特殊说明,本作品采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可。