1

需要定义一个 seek(u,v) 函数，其中 u 是树中的新节点（我要开始搜索的节点），v 是新节点下面的后代数，这个函数会返回 index键值最高的。这棵树没有一个 BST，可以有许多子节点。例子：

input:
5             // tree with 5 nodes
1 3 5 2 7     // the nodes' keys
1 2           // 1 and 2 are linked
2 3           // 2 and 3 are linked
1 4           // 1 and 4 are linked
3 5           // 3 and 5 are linked
4             // # of seek() requests
2 3           // index 2 of tree, which would be key 5, 3 descendants from index 3 
4 1           // index 4 of tree, but only return highest from index 4 to 4 (it would 
              // return itself)
3 2           // index 3, next 2 descendants
3 2           // same

output:
5             // Returned index 5 because the 7 is the highest key from array[3 'til 5]
4             // Returned index 4 because the range is one, plus 4's children are null
5             // Returned index 5 because the 7 is the highest key from array[4 'til 5]
5             // Same as prior line

我正在考虑将新根放入新的红黑树中，但找不到有效保存每个节点的后继或前驱信息的方法。还考虑放入一个数组，但由于不平衡和未排序树的性质，它不能保证我的树会被排序，而且因为它不是 BST，所以我不能执行无序树遍历。关于如何从特定范围获得最高键的任何建议？

4

1 回答 1

1

我不太明白你的意思：“新节点下的后代数量”。正如你所说的那样，它意味着存在某种强加的树行走，或者至少是你必须访问节点的顺序。在这种情况下，最好更彻底地解释你的意思。

在其余答案中，我假设您的意思是与您的距离。

从纯算法的角度来看，由于您不能对树进行任何假设，因此您必须访问图的所有相关顶点（即距离 u <= v 的顶点）以获得结果。这意味着任何部分树遍历（例如深度优先或广度优先）都应该足够且必要（因为您必须访问 u 以下的所有相关节点），因为我们访问节点的顺序无关紧要。

如果可以的话，使用递归函数 seek'(u,v) 会更简单，它返回定义如下的一对 (index, key)：

  • 如果 v > 1，您将 seek'(u,v) 定义为在配对 (u, key(u)) 中最大化其第二个分量的配对，并将 seek(w,v-1) 定义为 u 的 w 儿子。
  • 否则 (v = 1) 你将 seek'(u,v) 定义为 (u, key(u))

然后你有 seek(u,v) = first(seek'(u,v))。

我所说的所有内容都假定您已经从输入构建了一个树，或者您可以轻松地从其索引中获取节点及其子节点的键。

于 2012-10-26T15:25:13.923 回答