首页 > 其他分享 >一种调试 线段树 / Treap / Splay / 左偏树 / LCT 等树形结构的技巧

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

时间：2025-01-09 13:11:07浏览次数：1  
标签：--- LCT 19 Splay +--- null 左偏

前言

如果我们需要观察程序运行过程中，某一个变量、某一个序列的变化情况，你可以在修改的地方打断点 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
====================

标签：---,LCT,19,Splay,+---,null,左偏
From： https://www.cnblogs.com/XuYueming/p/18656288

相关文章

  • 基于SpringBoot的Cosplay论坛的设计与实现
    引言  随着互联网技术的飞速发展，网络社区已成为人们交流思想、分享兴趣的重要平台。Cosplay文化作为一种流行的文化现象，将动漫、游戏、电影等作品中的角色通过扮演的方式呈现出来，吸引了大量爱好者的参与。然而，现有的Cosplay社区往往存在功能单一、交流不便等问题，无法满足......
  • ov5640_lcd_display学习笔记
    最近学习了正点原子fpgaov5640摄像头显示例程，特此记录一下。系统框架与接口FPGA要操控的外围器件为ov5640摄像头、LCD和DDR3，接口方面也并不算复杂，用到的接口为sccb、dvp以及RGB888。sccb接口用来配置摄像头寄存器参数，并且iic兼容sccb,所以配置寄存器直接调用iic的驱动模块即......
  • Splay初步
    更好的阅读体验？前言前置知识：二叉搜索树其实Splay的实现蛮多的，如果真的要能懂的话建议自己画图理解。加油。基础操作准备操作我们先把节点要维护的先定义出来。子树大小节点的权值左儿子右儿子父亲sizevalch[0]ch[1]fastructnode{intsize,val,......
  • 说说你对css中font-display的理解，它有什么作用？
    font-display是一个CSS属性，用于控制在字体加载期间和失败时文本的显示方式。这个属性主要用于@font-face规则，以改善网页的字体加载性能和用户体验。font-display的作用主要体现在以下几个方面：控制字体加载时的行为：在字体文件还未加载完成时，font-display可以控制文本的显......
  • [学习笔记] splay
    前置：二叉查找树在二叉查找树上做许多操作都十分方便。然而递归树的层数意味着时间复杂度为树高级别。当树是链状时，时间复杂度会退化。各类平衡树的存在大都为了使二叉查找树“平衡”，即高度不会超过\(\logn\)（\(n\)为树的结点个数）。如此以来，在二叉查找树上的操作就有了时间复杂......
  • WSL2 ubuntu18.04 使用xfce4时Xlaunch黑屏问题以及解决，X server already running on d
    显示xfce4启动成功却没有画面显示在Ubuntu终端输入startxfce4启动X服务时，显示：/usr/bin/startxfce4:Xserveralreadyrunningondisplay10.255.255.254:0，且Xlaunch黑屏无输入。如图所示：分析原因：出现Xserveralreadyrunningondisplay10.255.255.254:0说明X服务......
  • vue3 wspt 插件的使用 wsplayer无插件开发包封装
    基于大华插件：H5播放器开发套件（wsplayer无插件开发包）V1.2.9使用方法npmiwsptwspt使用说明1.找到node_modules目录中wspt文件夹，将static文件夹、jquery.min.js、palyer.css、PlayerControl.js、WSPlayer.js文件复制到项目public目录下。public|--jquery.min.js......
  • 常用的 journalctl 命令总结
    copyfrom  https://zhuanlan.zhihu.com/p/722001166 journalctl是一个用于查看由systemd收集的系统和服务日志的工具。1.查看所有日志journalctl2.实时查看日志（类似于tail-f）journalctl-f3.按服务查看日志查看特定服务的日志journalctl-u<服务名>例如，查看nginx......
  • 了解 CSS 中 display: flex 弹性盒子布局结合 flex-wrap 的应用
    功能描述display:flex将元素设置为弹性盒子布局模式，可以更轻松地设计灵活的响应式布局结构，而无需使用浮动或定位。因此，子元素的float、clear和vertical-align属性也将失效。默认情况下，flex布局项目都排在一条线上。flex-wrap属性定义一条轴线轴线排不下时如何换行。代......
  • 说说display:flex和display:inline-flex有什么区别？
    在CSS中，display属性用于设置元素的显示类型。display:flex和display:inline-flex都是用于创建弹性盒子（flexbox）容器的值，但它们之间存在一些关键差异。块级与内联级行为：display:flex：将元素设置为块级弹性盒子。这意味着，该元素将像块级元素一样表现，独占一行，且其宽度默认填充......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99