0

我有一个订单统计增强红黑树。

它在大多数情况下都有效。但我需要实现一个快速函数（O（lg n）），它主要按排序顺序返回节点的位置。就像我教科书中的 OS-rank 函数一样。但有一个转折：如果两个节点具有相同的分数，则返回值应该相同。这是 os-rank 函数（在伪代码中，对于给定的节点 x，其中 root 是树的根）。

OS-Rank(x)
r=x.left.size+1
y=x
while y!=root
  if y==y.p.right
    r+=y.p.left.size+1
y=y.p
return r

但是：我需要的是，如果 A 有键 1 而节点 B 有键 1，则函数对两者都返回 1。等等。我尝试过这样的事情。

rank(x)
start with value r=1
check that x.right is not Nil
  case x.right has the same key as x
    add x.right.#nodeswithkeyhigher(x.key) to r
  other cases: add x.right.size to r
y=x
while y != root
  if y.parent.left == y
    case y.parent.right.key>x.key
      add y.parent.right to r
    other cases
      add y.parent.right.#nodeswithkeyhigher(x.key) to r
  y=y.parent
return r

你猜怎么着：一个测试用例失败了。我想知道这是否是一种正确的做事方式，或者我是否犯了一些我没有看到的错误（否则错误出现在 Node.#nodeswithkeyhigher(key) 函数中）。

4

1 回答 1

0

编辑：答案的最后一段，感谢 Sticky。

tl;dr：跳到最后几段

这与我遇到的问题相同。（是的，DS 也是如此）。到目前为止，除了 5 之外的所有运行都是正确的。我已经测试了几件事，其中一件非常简单：只需在 OSRank 中交换左右即可。在某些情况下，它给出了正确的答案，但在更难的情况下，它有点偏离。哦，我还补充说，如果 y.score == y.parent.score 我只添加 y.parent 的正确大小，否则我添加正确的大小 + 1。

public int OSRank(Node x)
    {
        int r = x.Right.Size + 1;
        Node y = x;
        while (y != root)
        {
            if (y == y.Parent.Left)
            {
                if (y.Score == y.Parent.Score)
                    r = r + y.Parent.Right.Size;
                else
                    r = r + y.Parent.Right.Size + 1;
            }
            y = y.Parent;
        }
        return r;
    }

让我们首先在第 340 页的树上测试这个方法（图 14.1）。我们将搜索 38 的排名（应该返回 4，因为 39、47 和 41 更高）：

  1. r = 1 + 1 = 2 //右侧 + 1
  2. r = 2 //什么都没有发生，因为我们是一个正确的孩子
  3. r = r + 1 + 1 = 4 //我们是左孩子，我们父母的key更大并且parent.Right.size = 1
  4. r = 4 //什么都没有发生，因为我们是正确的孩子

所以在这种情况下，结果是正确的。但是，如果我们在树中添加另一个键为 38 的节点会怎样。这稍微重塑了我们的树，节点 26 的右侧部分现在看起来像：

（我还不允许添加图片，所以请看这里：http://i47.tinypic.com/358ynhh.png）

如果我们使用相同的算法，我们会得到以下结果（选择红色的）：

  1. r = 0 + 1 = 1 //没有右边
  2. r = 1 //我们是正确的孩子
  3. r = 1 //我们是正确的孩子
  4. r = 1 + 3 + 1 = 5 //3来自节点41的大小。
  5. r = 5 //我们是正确的孩子

虽然我们在这里预计排名第 4。当我输入这个时，我注意到我们检查了 y.Score == y.Parent.Score，但我完全忘记了 y 的变化。因此，在第 4 行中，子句“y.Score == y.Parent.Score”是错误的，因为我们将节点 30 与 38 进行了比较。因此，如果我们将该行更改为：

if (x.Score == y.Parent.Score)

该算法输出秩 4，这是正确的。这意味着我们消除了另一个问题。但是还有更多，我也没有弄清楚：

  • Y.Parent.Right 包含重复键的情况。从技术上讲，如果我们有 3 个具有相同密钥的节点，它们应该算作 1。
  • Y.Parent.Right 包含等于 x.Key 的键（您想要排名的节点）的情况。那会使我们倒退几个等级，这是错误的。

我想你可以保留另一个整数来保存分数更高的节点数量。插入后，如果该节点的子树不包含具有相同分数的节点，则可以爬树并调整值。但是我现在不知道这是如何完成的（并且有效地）。

编辑：首先找到具有相同分数 x 的 x 的最终后继者。然后以正常方式计算排名。上面的代码有效。

于 2012-06-28T09:03:54.373 回答