0

Robert Sedgewick の Algorithms で説明されている Red Black Trees を調べてきました。赤黒ツリーに挿入するコードは次のとおりです。

public void put(Key key, Value val) {
    root = put(root, key, val);
    root.color = BLACK;
    assert check();
}

// insert the key-value pair in the subtree rooted at h
private Node put(Node h, Key key, Value val) { 
    if (h == null) return new Node(key, val, RED, 1);

    int cmp = key.compareTo(h.key);
    if      (cmp < 0) h.left  = put(h.left,  key, val); 
    else if (cmp > 0) h.right = put(h.right, key, val); 
    else              h.val   = val;

    // fix-up any right-leaning links
    if (isRed(h.right) && !isRed(h.left))      h = rotateLeft(h);
    if (isRed(h.left)  &&  isRed(h.left.left)) h = rotateRight(h);
    if (isRed(h.left)  &&  isRed(h.right))     flipColors(h);
    h.N = size(h.left) + size(h.right) + 1;

    return h;
}

これは、赤黒の修正を視覚化するための画像です。 赤黒可視化 挿入する項目が上位 3 ノードの中間にある場合を考えてみましょう。3 つの if ステートメントで指定されている 3 つの操作、つまり 、および を実行する必要がh=rotateLeft(h)ありh=rotateRight(h)ますflipcolors(h)。問題は、を割り当てるときh = rotateLeft(h)です。返されるノードは、2 つの連続する左の赤いリンクを持つ 3 つのノードの中間ノードへのポインターです。ただし、アルゴリズムは、返されたノードが、2 つの連続した左の赤いリンクを持つ 3 つのノードの最上位ノードであると想定しています。そのため、再びrotateRight(h)開始すると、最初と同じ位置になります。アルゴリズムを理解していない可能性があります。

ここにコードがありますrotateLeft(h)

private Node rotateLeft(Node h) {
    assert (h != null) && isRed(h.right);
    Node x = h.right;
    h.right = x.left;
    x.left = h;
    x.color = x.left.color;
    x.left.color = RED;
    x.N = h.N;
    h.N = size(h.left) + size(h.right) + 1;
    return x;
}

h=rotateLeft(h)2 つの連続した赤い左のリンクを持つ 3 つのノードの中間ノードの代わりにトップ ノードを与える方法を理解するのを手伝ってください。

4

1 に答える 1

1

アルゴリズムの仕組みがようやく理解できました。の後h=rotateLeft(h)、2 番目と 3 番目if statementsは に評価されfalseます。そしてh返されます。再帰を 1 レベル上げると、等値の左側h.left =hがh3 つのノードの最上位ノードで、2 つの連続した赤い左リンクがあることがわかります。次に、最初のifステートメントが false と評価され、2 番目のifステートメントが true と評価され、右回転を行い、次に色反転を行います。

間違っている場合は修正してください。

于 2013-10-31T09:52:58.763 に答える