3

赤黒木では、回転するとき、特定のノードの親が誰であるかを知る必要があります。ただし、ノードは右または左の子への参照しかありません。

ノードインスタンス変数に「親」を与えることを考えていましたが、この理由からそうする価値はないと思います。また、回転ごとに親参照を変更するのは複雑すぎるでしょう。

public class Node {
  private left;
  private right;
  private isRed;
  private parent; //I don't think this is good idea
}

したがって、私の解決策は、検索を使用して親を見つける findParent() メソッドを作成することです。ノードの親を見つける他の方法があるかどうか疑問に思っていますか?

私の解決策：

サンプルツリー:

    50
    / \
   25  75

ノード 25 の親を見つけたい場合は、次のようなものを渡します。

Node parent = findParent(Node25.value);

node50 を返します。

protected Node findParent(int val) {
        if(root == null) {
            return null;
        }
        Node current = root;
        Node parent = current;
        while(true) {
            if(current.val == val) { //found
                return parent;
            }
            if(current == null) { //not found
                return null;
            }
            parent = current;
            if(current.val > val) { //go left
                current = current.left;
            }
            else { //go right
                current = current.right; 
            }
        }
    }
4

5 に答える 5

3

ノードインスタンス変数に「親」を与えることを考えていましたが、この理由からそうする価値はないと思います

ノードに参照を持たせるには、ノードparentごとに 1 つの追加のポインター/参照が必要です。これを、特定のノードの親を知る必要があるときはいつでもツリーをトラバースする必要があることと比較してください。

これは、次の間のトレードオフです。

  1. 追加の参照を維持し、ノードを変更するたびに最新の状態に保つためのコスト。
  2. 特定のノードの親を見つけるためにツリーをトラバースする必要がある計算コストと複雑さ

これら 2 つのオプションのどちらを選択するかは、やや主観的なものだと思いますが、個人的には、単に参照を追跡することを選択しますparent。

参考までに、は、 、、およびを含むノードを参照java.util.TreeMapする赤黒ツリーとして実装されています。Entryleftrightparent

于 2010-07-27T19:15:46.097 に答える
2

ツリーをトラバースしてピボット ノードに到達するときに、前の親をキャッシュできます。または、複数レベルの「元に戻す」が必要な場合は、トラバースした各ノードをスタックにキャッシュできます。

このキャッシュはローテーション アルゴリズムに対してローカルな変数になるため、ツリー内にこれ以上のスペースや高価な追加のトラバーサルは必要ありません。

于 2010-07-27T19:27:44.977 に答える
1

親を検索するよりも、親を保存する方が間違いなく優れています。親参照の更新はそれほど複雑ではありません。

于 2010-07-27T19:15:06.253 に答える