C++ 跳转指针算法

2025年2月11日 | 阅读 12 分钟

跳跃指针算法是一种旨在优化树结构中祖先查询的高级方法。该算法提高了查找两个节点的最低公共祖先 (LCA) 等操作的效率。通过预处理树，它为每个节点分配一组“跳跃指针”，这些指针是对其特定距离祖先的引用。此预处理步骤涉及以允许快速遍历和查询响应的方式计算和存储这些指针。

方法 1：简单方法

实施

 
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
class Tree {
    vector<vector<int>> adj; // adjacency list of the tree
    vector<vector<int>> jump; // jump pointers
    vector<int> depth; // depth of each node
    int max_jump; // maximum number of jumps needed
public:
    Tree(int n) {
        adj.resize(n);
        depth.resize(n);
        max_jump = ceil(log2(n));
        jump.resize(n, vector<int>(max_jump + 1, -1));
    }
    // Function to add an edge between two nodes
    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    // Preprocessing step to compute jump pointers and depths
    void preprocess(int root) {
        depth[root] = 0;
        dfs(root, -1);
    }
    // Depth-first search to initialize jump pointers and depths
    void dfs(int node, int parent) {
        jump[node][0] = parent;
        for (int i = 1; i <= max_jump; ++i) {
            if (jump[node][i - 1] != -1)
                jump[node][i] = jump[jump[node][i - 1]][i - 1];
        }
        for (int neighbor : adj[node]) {
            if (neighbor != parent) {
                depth[neighbor] = depth[node] + 1;
                dfs(neighbor, node);
            }
        }
    }
    // Function to find the lowest common ancestor of nodes u and v
    int findLCA(int u, int v) {
        if (depth[u] < depth[v])
            swap(u, v);
        // Bring u and v to the same depth
        int diff = depth[u] - depth[v];
        for (int i = 0; i <= max_jump; ++i) {
            if ((diff >> i) & 1)
                u = jump[u][i];
        }
        if (u == v)
            return u;
        // Find the lowest common ancestor
        for (int i = max_jump; i >= 0; --i) {
            if (jump[u][i] != jump[v][i]) {
                u = jump[u][i];
                v = jump[v][i];
            }
        }
        return jump[u][0];
    }
};
int main() {
    int n = 9; // number of nodes in the tree
    Tree tree(n);
    // Add edges to the tree
    tree.addEdge(0, 1);
    tree.addEdge(0, 2);
    tree.addEdge(1, 3);
    tree.addEdge(1, 4);
    tree.addEdge(2, 5);
    tree.addEdge(2, 6);
    tree.addEdge(3, 7);
    tree.addEdge(3, 8);
    // Preprocess the tree to compute jump pointers and depths
    tree.preprocess(0); // Assuming node 0 is the root
    // Find the LCA of nodes 7 and 8
    int lca = tree.findLCA(7, 8);
    cout << "LCA of nodes 7 and 8 is: " << lca << endl;
    // You can add more tests here to find LCA of other nodes
    int lca1 = tree.findLCA(4, 5);
    cout << "LCA of nodes 4 and 5 is: " << lca1 << endl;
    int lca2 = tree.findLCA(6, 8);
    cout << "LCA of nodes 6 and 8 is: " << lca2 << endl;
    return 0;
}   

输出

 
LCA of nodes 7 and 8 is: 3
LCA of nodes 4 and 5 is: 0
LCA of nodes 6 and 8 is: 0

说明

树表示

树使用邻接列表表示，其中每个节点都有其连接节点（子节点）的列表。

初始化

初始化了几个数据结构

adj：它存储树的邻接列表。
depth：它存储每个节点到根的深度。
jump：一个二维数组，其中 jump[i][j] 表示节点 i 的第 2^j 个祖先。
max_jump：所需的最多跳跃次数，即节点数量以 2 为底的对数的上限。这决定了跳跃数组中的级别数。

添加边

通过在节点之间添加边来构建树，从而有效地构建邻接列表。

预处理

对树进行预处理以计算节点的跳跃指针和深度。这是通过从根开始的深度优先搜索 (DFS) 完成的。

在 DFS 期间

每个节点的直接父节点作为其跳跃指针的第一级存储。
使用动态规划计算更高级别的跳跃指针。如果已知 jump[i][j-1]，则 jump[i][j] 计算为 jump[jump[i][j-1]][j-1]。
每个节点的深度随着 DFS 的进行而计算。

最低公共祖先 (LCA) 查询

查找两个节点 u 和 v 的 LCA

首先，确保两个节点处于相同的深度。如果不是，则使用其跳跃指针将较深的节点向上移动，直到两个节点处于相同的深度。
如果在此步骤后节点相同，则找到 LCA。
如果不是，则使用尽可能高的跳跃指针同时向上移动两个节点，直到它们的父节点相同。这确保了节点收敛到它们的最低公共祖先。

输出

预处理后，代码可以高效地回答多个 LCA 查询。预计算的跳跃指针允许在对数时间内找到 LCA。

复杂度分析

时间复杂度

预处理：预处理步骤涉及深度优先搜索 (DFS) 以计算每个节点的深度并设置跳跃指针。

DFS 运行时间为 O(n)，其中 n 是树中节点的数量。
计算跳跃指针涉及为 n 个节点中的每个节点计算最多 O(log n) 个指针，导致此步骤的总时间为 O(n log n)。

查询：每个 LCA 查询都涉及调整两个节点的深度并使用跳跃指针查找公共祖先。

调整深度需要 O(log n) 时间，因为我们可能需要移动到最高的跳跃指针。
通过使用跳跃指针查找公共祖先也需要 O(log n) 时间。
因此，每个查询都可以在 O(log n) 时间内回答。

空间复杂度

树的存储：邻接列表需要 O(n) 空间，其中 n 是树中节点的数量。

深度数组：存储每个节点的深度需要 O(n) 空间。

跳跃指针：跳跃指针数组需要 O(n log n) 空间。每个节点最多有 O(log n) 个指针，导致总存储需求为 n * log n。

方法二：自底向上方法

跳跃指针算法用于高效地查找树中两个节点的最低公共祖先 (LCA)。自底向上方法从叶子开始构建跳跃指针，并向根移动。此方法预处理树以实现快速 LCA 查询。

实施

 
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
class Tree {
    vector<vector<int>> adj; // adjacency list of the tree
    vector<vector<int>> jump; // jump pointers
    vector<int> depth; // depth of each node
    int max_jump; // maximum number of jumps needed
public:
    Tree(int n) {
        adj.resize(n);
        depth.resize(n);
        max_jump = ceil(log2(n));
        jump.resize(n, vector<int>(max_jump + 1, -1));
    }
    // Function to add an edge between two nodes
    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    // Preprocessing step to compute jump pointers and depths
    void preprocess(int root) {
        depth[root] = 0;
        // Start from the leaves and move upwards
        dfs(root);
    }
    // Depth-first search to initialize jump pointers and depths
    void dfs(int node) {
        // Process children first
        for (int neighbor : adj[node]) {
            if (depth[neighbor] == -1) { // If not visited
                depth[neighbor] = depth[node] + 1;
                jump[neighbor][0] = node; // 2^0-th ancestor is the immediate parent
                // Build jump pointers for higher levels
                for (int j = 1; j <= max_jump; ++j) {
                    if (jump[neighbor][j - 1] != -1)
                        jump[neighbor][j] = jump[jump[neighbor][j - 1]][j - 1];
                }
                dfs(neighbor);
            }
        }
    }
    // Function to find the lowest common ancestor of nodes u and v
    int findLCA(int u, int v) {
        if (depth[u] < depth[v])
            swap(u, v);
        // Bring u and v to the same depth
        int diff = depth[u] - depth[v];
        for (int i = 0; i <= max_jump; ++i) {
            if ((diff >> i) & 1)
                u = jump[u][i];
        }
        if (u == v)
            return u;
        // Find the lowest common ancestor
        for (int i = max_jump; i >= 0; --i) {
            if (jump[u][i] != jump[v][i]) {
                u = jump[u][i];
                v = jump[v][i];
            }
        }
        return jump[u][0];
    }
};
int main() {
    int n = 9; // number of nodes in the tree
    Tree tree(n);
    // Add edges to the tree
    tree.addEdge(0, 1);
    tree.addEdge(0, 2);
    tree.addEdge(1, 3);
    tree.addEdge(1, 4);
    tree.addEdge(2, 5);
    tree.addEdge(2, 6);
    tree.addEdge(3, 7);
    tree.addEdge(3, 8);
    // Preprocess the tree to compute jump pointers and depths
    tree.preprocess(0); // Assuming node 0 is the root
    // Find the LCA of nodes 7 and 8
    int lca = tree.findLCA(7, 8);
    cout << "LCA of nodes 7 and 8 is: " << lca << endl;
    // You can add more tests here to find LCA of other nodes
    int lca1 = tree.findLCA(4, 5);
    cout << "LCA of nodes 4 and 5 is: " << lca1 << endl;
    int lca2 = tree.findLCA(6, 8);
    cout << "LCA of nodes 6 and 8 is: " << lca2 << endl;
    return 0;
}   

输出

 
LCA of nodes 7 and 8 is: -1
LCA of nodes 4 and 5 is: -1
LCA of nodes 6 and 8 is: -1

自底向上方法的解释

树表示

树表示为邻接列表，其中每个节点都有其连接节点（子节点和父节点）的列表。

初始化

初始化了几个数据结构

一个用于存储树结构的邻接列表。
一个深度数组，用于存储每个节点到根的深度。
一个跳跃指针表，它是一个二维数组，其中每个条目存储节点在不同级别的祖先。
根据树的高度所需的最多跳跃次数。

添加边

在节点之间添加边以形成树。这创建了定义树结构的邻接列表。

预处理（自底向上 DFS）

预处理步骤涉及从根开始的深度优先搜索 (DFS)

设置深度：计算每个节点的深度，从深度为 0 的根开始。每个子节点的深度是父节点深度加一。
初始化跳跃指针：对于每个节点，其直接父节点记录为其跳跃指针的第一级。
计算更高级别的跳跃指针：使用动态规划计算更高级别的跳跃指针。如果已知节点的第 2^j 个祖先，则可以通过查找第 2^j 个祖先的第 2^j 个祖先来计算第 2^(j+1) 个祖先。
此过程递归地为每个节点的子节点执行，然后才为其自身，确保跳跃指针是自底向上计算的。

查找 LCA

查找两个节点的 LCA

均衡深度：如果节点深度不同，则使用其跳跃指针将较深的节点向上移动，直到两个节点处于相同的深度。
同时攀爬：如果节点不相同，则使用尽可能高的跳跃指针同时向上移动两个节点，直到它们的直接祖先不同。继续此操作，直到节点收敛到它们的最低公共祖先。
最后一步将使两个节点都达到它们的 LCA。

复杂度分析

时间复杂度

预处理

深度计算：DFS 对整个树运行一次，每个节点只访问一次。这需要 O(n) 时间，其中 n 是树中节点的数量。

跳跃指针初始化：对于每个节点，我们计算最多 log(n) 个跳跃指针。由于有 n 个节点，因此这部分需要 O(n log n) 时间。

因此，预处理的总时间复杂度为 O(n log n)。

查询

均衡深度：为了使两个节点达到相同的深度，我们可能需要使用跳跃指针最多 log(n) 次。这需要 O(log n) 时间。

同时攀爬：在均衡深度后查找 LCA，我们使用跳跃指针最多 log(n) 次将两个节点向上移动，直到它们的父节点相同。这也需要 O(log n) 时间。

因此，每个查询的时间复杂度为 O(log n)。

空间复杂度

邻接列表：树的邻接列表表示需要 O(n) 空间。

深度数组：存储每个节点的深度需要 O(n) 空间。

跳跃指针：跳跃指针数组是一个 n 行 log(n) 列的二维数组，因此总空间需求为 O(n log n)。

方法三：稀疏表方法

稀疏表方法是一种用于预处理树结构以高效查找两个节点的最低公共祖先 (LCA) 的方法。它构建一个稀疏表（二维数组），其中每个条目 st[i][j] 表示节点 i 的第 2^j 个祖先。

实施

 
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
class Tree {
    vector<vector<int>> adj; // adjacency list of the tree
    vector<vector<int>> jump; // sparse table for jump pointers
    vector<int> depth; // depth of each node
    int max_jump; // maximum number of jumps needed
public:
    Tree(int n) {
        adj.resize(n);
        depth.resize(n, -1);
        max_jump = ceil(log2(n));
        jump.resize(n, vector<int>(max_jump + 1, -1));
    }
    // Function to add an edge between two nodes
    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    // Preprocessing step to compute jump pointers and depths
    void preprocess(int root) {
        depth[root] = 0;
        dfs(root, -1);
        // Build sparse table for higher jumps
        for (int j = 1; j <= max_jump; ++j) {
            for (int i = 0; i < adj.size(); ++i) {
                if (jump[i][j-1] != -1) {
                    jump[i][j] = jump[jump[i][j-1]][j-1];
                }
            }
        }
    }
// Depth-first search to initialize jump pointers and depths
    void dfs(int node, int parent) {
        jump[node][0] = parent; // 2^0-th ancestor is the immediate parent
        for (int neighbor : adj[node]) {
            if (neighbor != parent) { // Avoid going back to the parent
                depth[neighbor] = depth[node] + 1;
                dfs(neighbor, node);
            }
        }
    }
// Function to find the lowest common ancestor of nodes u and v
    int findLCA(int u, int v) {
        if (depth[u] < depth[v])
            swap(u, v);
        // Bring u and v to the same depth
        int diff = depth[u] - depth[v];
        for (int i = 0; i <= max_jump; ++i) {
            if ((diff >> i) & 1)
                u = jump[u][i];
        }
        if (u == v)
            return u;
        // Find the lowest common ancestor
        for (int i = max_jump; i >= 0; --i) {
            if (jump[u][i] != jump[v][i]) {
                u = jump[u][i];
                v = jump[v][i];
            }
        }
        return jump[u][0];
    }
};
int main() {
    int n = 9; // number of nodes in the tree
    Tree tree(n);
    // Add edges to the tree
    tree.addEdge(0, 1);
    tree.addEdge(0, 2);
    tree.addEdge(1, 3);
    tree.addEdge(1, 4);
    tree.addEdge(2, 5);
    tree.addEdge(2, 6);
    tree.addEdge(3, 7);
    tree.addEdge(3, 8);
    // Preprocess the tree to compute jump pointers and depths
    tree.preprocess(0); // Assuming node 0 is the root
    // Find the LCA of nodes 7 and 8
    int lca = tree.findLCA(7, 8);
    cout << "LCA of nodes 7 and 8 is: " << lca << endl;
    // You can add more tests here to find LCA of other nodes
    int lca1 = tree.findLCA(4, 5);
    cout << "LCA of nodes 4 and 5 is: " << lca1 << endl;
    int lca2 = tree.findLCA(6, 8);
    cout << "LCA of nodes 6 and 8 is: " << lca2 << endl;
    return 0;
}   

输出

 
LCA of nodes 7 and 8 is: 3
LCA of nodes 4 and 5 is: 0
LCA of nodes 6 and 8 is: 0

稀疏表方法的解释

树表示

树使用邻接列表 (adj) 表示。每个节点指向其直接子节点。

初始化

初始化了几个数据结构

depth：一个数组，用于存储树中每个节点的深度。
jump：一个二维向量，其中 jump[i][j] 将存储节点 i 的第 2^j 个祖先。
max_jump：小于或等于树深度的 2 的最大幂。

添加边

在节点之间添加边以使用邻接列表定义树结构。

预处理（深度计算）

使用 DFS 计算深度：从选定的根节点开始深度优先搜索 (DFS)。在此遍历期间
计算每个节点相对于根节点的深度。
根据 DFS 顺序设置每个节点的直接父节点 (jump[i][0])。

构建稀疏表

初始化：初始化稀疏表 jump[i][0] 以存储每个节点的直接父节点。
更高跳跃的动态规划：使用嵌套循环填充稀疏表更高级别。对于每个节点和 2 的每个幂，使用之前计算的祖先计算第 2^j 个祖先。

查询 LCA

均衡深度：查找两个节点 u 和 v 的 LCA

通过使用它们的跳跃指针向上移动 u 和 v，直到它们具有相同的深度来调整 u 和 v 的深度。

使用稀疏表：从 2 的最高幂向下到 0

同时向上移动 u 和 v，使用它们的跳跃指针，直到它们的直接祖先不同。这确保它们有效地到达它们的 LCA。

复杂度分析

时间复杂度

预处理

深度计算：深度优先搜索 (DFS) 对整个树运行一次，每个节点只访问一次。这需要 O(n) 时间，其中 n 是树中节点的数量。

稀疏表构建：构建稀疏表涉及填充一个大小为 n x log(n) 的二维数组，其中每个单元格都使用前几层的结果进行计算。这也需要 O(n log n) 时间。

因此，预处理的总时间复杂度为 O(n log n)。

查询

均衡深度：使用跳跃指针调整两个节点的深度以使其相同需要 O(log n) 时间。

查找 LCA：在均衡深度后使用稀疏表查找 LCA 也需要 O(log n) 时间。

因此，每个 LCA 查询的时间复杂度为 O(log n)。

空间复杂度

邻接列表：树的邻接列表表示需要 O(n) 空间。

深度数组：存储每个节点的深度需要 O(n) 空间。

稀疏表：稀疏表是一个大小为 n x log(n) 的二维数组，需要 O(n log n) 空间。

下一个主题DART 和 C++ 之间的区别

← 上一个下一个 →

C++ 跳转指针算法

方法 1：简单方法

实施

说明

复杂度分析

方法二：自底向上方法

实施

自底向上方法的解释

复杂度分析

方法三：稀疏表方法

实施

稀疏表方法的解释

复杂度分析

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C++ 教程

C++ 控制语句

C++ 函数

C++ 数组

C++ 类和对象

C++ 构造函数

C++ 继承

C++ 多态

C++ 抽象

C++ 命名空间

C++ 模板

C++ 字符串

C++ 指针

信号处理

C++ 异常

C++ 文件与流

C++ STL 教程

面试题

选择题

C++ 程序

C++ STL Stack

C++ STL Bitset

C++ STL Deque

C++ STL List

C++ STL Map

C++ STL Math

C++ STL priority_queue

C++ STL Queue

C++ STL Multiset

C++ STL Multimap

C++ STL Set

C++ STD Strings

C++ STL Vector

C++ 操纵符

C++ STL Algorithms

C++ Algorithm

C++ Iterators

C++ 杂项

C++ 跳转指针算法

方法 1：简单方法

实施

说明

复杂度分析

方法二：自底向上方法

实施

自底向上方法的解释

复杂度分析

方法三：稀疏表方法

实施

稀疏表方法的解释

复杂度分析

相关帖子

C++ 中的可变 lambda

C++ 2-SAT 问题

C++ Deducing_this 函数

C++ 中的乌拉姆数序列

在 C++ 中生成随机双精度数

C++ 中 Shuffle 和 Random_shuffle 的区别

C++ 4Sum - 查找和最接近的四元组

C++ 中如何计算二维数组中数字的方差