0

私は注文統計量を増やした赤黒の木を持っています。

それはほとんどの場合機能します。しかし、ノードの場所をソート順に返す高速関数 (O(lg n)) を実装する必要があります。私の教科書のOSランク関数のように。ただし、1 つのひねりがあります。2 つのノードのスコアが同じ場合、戻り値は同じになるはずです。これが os-rank 関数です (ルートがツリーのルートである特定のノード x に対する疑似コードで)。

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

編集：スティッキーのおかげで、答えの最後の段落。

tl; dr：最後の段落にスキップ

これは私が問題を抱えているのと同じ問題です。（はいDSも）。これまでのところ、5つを除くすべての実行が正しいです。私はいくつかのことをテストしました。1つは非常に単純なものです。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を検索します（39、47、41の方が高いため、4を返す必要があります）。

  1. r = 1 + 1 =2//右側+1
  2. r = 2 //私たちは正しい子なので、何も起こりません
  3. r = r + 1 + 1 = 4 //私たちは左の子であり、親のキーはより大きく、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行目では、ノード30を38と比較したため、「y.Score == y.Parent.Score」という句は誤りでした。したがって、その行を次のように変更すると、次のようになります。

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 に答える