1

問題は、祖先行列を前提として、どのように二分木を作成するかです。http://www.ritambhara.in/build-binary-tree-from-ancestor-matrics/でクールな解決策を見つけました。問題は、マトリックスから行と列を削除することです。どうすればいいですか？誰かがこれの擬似コードを提案できますか？または、より良いアルゴリズムはありますか？

4

3 に答える 3

2

行と列を実際に削除する必要はありません。追加の配列で削除済みのフラグを立てるか、すべてゼロにすることができます。これは実質的に同じだと思います（実際には、削除されたことを知る必要があるため、選択しないでください）。再びステップ4.cで-したがって、ノードに削除済みのフラグを立てるだけで十分です）。

このページからの擬似コードの変更は次のとおりです。

4.b.

used[temp] = true;
for (i = 0 to N) 
    Sum[i] -= matrix[i][temp]; (aka decrement sum if temp is a predecessor of i)
    matrix[i][temp] = 0;

4.c. Sum [i]==0およびused[i]==falseであるすべての行を探します。

于 2012-10-17T08:31:14.157 に答える
2

これは、DoanldKnuthがアルゴリズムXを実装するために使用したDancingLinksを思い出させます。これは 基本的に循環二重リンクリストの構造です。個別のSum配列を維持し、必要に応じて行と列を削除して更新することができます。

実際には、個別のSum配列を維持する必要はありません。
編集：

つまり
、円形の2Dリンクリストで構成される構造を使用できます。ノード構造は次のようになります。

struct node{
        int val;
        struct node *left;
        struct node *right;
        struct node *down;
};


最上部と左端のリストは、頂点（二分木ノード値）のヘッダーリストです。

頂点jが頂点の祖先である場合は、列のcurrentにこの新しいノードが割り当てられ、currentにこの新しいノードが割り当てられるiように、（空の）新しいノードを作成します。注：構造は、祖先行列の各行を左から右にスキャンし、0からNまでの行を挿入することで簡単に構築できます（ここでは頂点の数を想定しています）jdowni'sleft
N

Image1

Image4

これらの画像をImage1とImage2から借りて、グリッドのアイデアを出しました。ただし、2番目の画像には左端のヘッダーがありません。

いいえの場合N。頂点の。O(N^2)祖先マトリックス（ツリーが歪んでいる場合）または平均的なエ​​ントリに、より悪いエントリが存在する可能性がありO(NlogN)ます。

現在のルートを検索するには：O(N)
最初にダミーノードを想定し、左端のヘッダーを線形にスキャンして、でノードを選択しますnode->down->right == node->down。

この頂点情報を削除するには：O(N)
行を削除します。O(1) 

node->down = node->down->down;

列の削除：O(N)
対応する列に移動します-say（p）：

node* q = p;
while(q->down != p){
    q->down->left->right = q->down->right;
    q->down->right->left = q->down->left;
    q = q->down;
}


現在のルートを検出したら、その親ノードに割り当ててキューに挿入し、そのリンクが示すように次のレベルを処理できます。

全体的な時間計算量：N +（N-1）+（N-2）+....= O(N^2)。
最悪の場合のスペースの複雑さO(N^2)

すでに持っているソリューションからの漸近実行時間の大きな改善はありませんが。この種の構造は、スパース行列を格納し、それらの乗算などの演算を定義する場合や、行/列とその後のバックトラックを削除してKnuthのように再度追加するバックトラッキングアルゴリズムを使用している場合に特に便利です。 AlgorithmX。

于 2012-10-17T08:49:20.123 に答える
0

マトリックスを更新する必要はありません。現在のノードの子孫の合計配列の値をデクリメントし、それらのいずれかがゼロに達するかどうかを確認します。これは、現在のnoeが最後の祖先、たとえば直接の親であることを意味します。

for (i = 0 to N) 
    if matrix[i][temp]==1:
      Sum[i]=Sum[i]-1
      if Sum[i]==0:
        add i as child of temp
        add i to queue
于 2015-06-03T08:46:45.857 に答える