c++ - 图问题 : Find whether two nodes share the same branch in O(1) time and O(1) storage per node

Question

假设我们有一个有向树(有向图)。所以，随着时间的推移，我们在主分支上构建，我们将主分支定义为从根(整个树中的第一个节点)开始的最长分支，并且在构建它的同时，我们可以随时构建新的分支通过将新节点附加到任意节点，但大多数情况下，我们建立在尖端(最长的分支上)。

图节点具有以下形式:

struct {
    int id;
    int prev_node_id; // this is what links nodes together
}

假设我们选择了两个随机节点 X 和 Y。问题是:这些节点是否共享一个分支？

每个节点都由一个 ID 定义(基本上是加密散列，这里由一个 int 简化)。这个问题的一个解决方案是我们简单地从一个节点开始返回图中，直到我们遇到另一个节点。这需要遍历分支中的所有节点，因此这是 O(N)，其中 N 是分支中的节点数，它可以非常非常长(数百万个节点)。是否有任何类型的数据可以构建到可以进行此操作 O(1) 的节点中，其中每个节点的数据大小也是 O(1)？

我的解决方案排名第一(不好，因为每个节点的存储空间为 O(N)):

我们向数据结构中添加一个任意长的素数:

struct {
    int id;
    int prev_node_id;
    ArbitraryPrecisionInt branch_index;
}

每当我们将节点附加到树的任何部分时，我们都会定义 branch_index成为:

branch_index_new = branch_index_old * new_prime_number;

新素数来自单例生成器。假设我们有几百万个节点，这并不昂贵。至少没有那么糟糕。

那么，节点 X 和 Y 共享同一个分支吗？

答案是肯定的，如果: X % Y == 0或 Y % X == 0 .

这里的问题是，这个产品的规模会增长得非常快。前 1000 个素数的乘积是巨大的。

我的解决方案二(有点糟糕，因为它的搜索时间为 O(log(N))，但每个节点的存储空间为 O(1)):

struct {
    int id;
    int prev_node_id;
    int branch_id;
}

branch_id基本上来自单例。我们从 0 开始，对于我们创建的每个新节点，我们有两种情况。

如果我们添加的节点在树的顶端(该节点不存在其他分支)，我们添加相同的值

如果该节点上已经存在分支，我们将数字加一(数字是从单例生成的，因此永远不会有重复)。

之后，我们创建一个数据库表，在其中写入每个新增量与每个值的高度(我们将高度定义为从根节点到该节点的长度)。

那么，节点 X 和 Y 共享同一个分支吗？为了回答这个问题，我们看看 X 的 branch_id ，然后我们查看数据库，我们找到创建分支的高度。我们去那里，找到 branch_id前一点。我们一直这样做，直到我们到达根目录(失败)或找到 branch_id Y的

这整个故事是我试图解决的区块链问题。真正问题的细节真的很复杂，没必要去细究。但是，如果您有兴趣，请随时与我聊天。我这么说是因为有人肯定会称这是一个 XY 问题。

有一个更好的方法吗？

Answer 1

澄清一下术语:当您向树添加叶子时，您希望能够选取任意两个节点并确定一个节点是否是另一个节点的祖先。

是的，你可以这样做。基本程序是:

每个节点都有两个标签——开始标签和结束标签。这些就像数字一样，标签之间存在总排序

当你向一个节点添加一个新的子节点时，你给它的开始和结束标签位于父节点的结束标签与其最后一个子节点的结束标签之间，或者如果你添加第一个子节点，则给它父节点的开始和结束标签.

每个节点的开始和结束标签将定义与其子树相对应的范围，以便您可以通过比较标签来测试一个节点是否在另一个节点的子树中。

当然，您不能只对这些标签使用数字，因为如果您继续将子项添加到最小的可用间隔中，您最终会用完位。

您可以使用字符串，因为总是可以在其他两个字符串之间生成一个字符串，但是存储是无限的，比较可能需要 O(1) 以上的时间。

因此，您需要某种神奇的标签类型，让您可以在任意一对标签之间添加任意数量的标签，并且仍然可以快速比较它们。

该问题称为订单维护问题: https://en.wikipedia.org/wiki/Order-maintenance_problem

我认为大多数情况下最实用的方法是本文中的简单算法: https://www.cs.cmu.edu/~sleator/papers/maintaining-order.pdf .那篇论文还提到订单维护是解决您问题的一种方法。

使用该算法，您可以在链表中使用数字，只要数字类型可以容纳 N2，并且添加新条目需要分摊 O(log N) 时间。

越来越复杂的结构可以给你更好的理论结果，一直到非分摊 O(1) 时间插入和 O(1) 时间比较，但这变得非常复杂。