0

授業で赤黒木のコードを教えてもらいました。ノードの作成に使用される構造体に親ポインターがありません。プロジェクトのほとんどが機能していますが、O(lg n) 時間でランクを計算する方法がわかりません。ランクとは、inorder-traversal を実行し、キーをインデックス 1 から始まる配列に保存する場合、指定されたキーが保存されるインデックスを意味します。これを行うと O(n) 時間になりますが、これは許可されていません。

CLRS を読んで、Augmenting Data Structures の章に、キーを指定してランクを返すコードがあります。これはまさに私が必要としているものですが、問題はコードが親ポインターを使用していることです。赤黒木の例では親ポインターを使用したことがなく、このコードには親ポインターが含まれていないため、ランクを機能させるためだけに指定されたコード全体を変更する必要はないと思います。親ポインターを使用せずにそれを行う方法があると信じています。

ノード構造体に存在する (フィールド?) は、キー (int)、左の子へのポインター、右の子へのポインター、サブツリー サイズ (int)、および色 (int) です。

すべてのコードは C で行われます。私が探しているのは、これが可能かどうか、およびソース コードの有無にかかわらずこれをどのように達成できるかです (適切な説明があれば完璧です)。

4

1 に答える 1

1

仮定: サブツリーのサイズには、サブツリーのルート ノードが含まれます。a で順序付けする値を呼び出します。

次に、このアルゴリズムは O(lgn) でランクを取得します。

1: let rank=subtree size(root of tree)
2: if you go left:
- adjust rank=rank - (subtree size(sts) of right child (rc) of root) - 1
- move to left child(lc) of root
3: if you go right:
- adjust rank=rank(prior)
- move to rc(root)
4: iterate 2-3 (replacing root with current node) until you are at the node with value a
5: if this node has a rc, adjust a final time
- rank = rank - (sts(rc))

終わり。

注: 通常の左から右、下から上への rb ツリーの順序付けを想定しています。

于 2011-12-01T02:12:39.060 に答える