6

私は C プログラミングは初めてで、C で C アルゴリズムを学んでいます。

node二分木データ構造を定義する方法に関する私の問題は次のとおりです。

親ノード ポインタを使用するか使用しないか

Nodeデータ構造を定義するための 2 つの典型的なサンプル コードを次に示します。

親ノードポインタなし

typedef struct binaryTreeNode_{
  int key;
  void *data;
  binaryTreeNode_ *leftNode;
  binaryTreeNode_ *rightNode;
} binaryTreeNode;

親ノードポインタあり

typedef struct binaryTreeNode_{
  int key;
  void *data;
  binaryTreeNode_ *leftNode;
  binaryTreeNode_ *rightNode;
  binaryTreeNode_ *parentNode;
} binaryTreeNode;

私の質問

明らかに、親ノード ポインターでノード構造を使用すると、多くの作業がはるかに簡単になります。ノード/ツリー、バイナリ ツリーを使用した DFS/BFS をトラバースするように。だから私の質問は、親ノードのない構造に基づくいくつかのソリューションがあるのはなぜですか? .

歴史的な理由はありますか？単純に RAM/DISK 容量の制限があるのであれば、親ノードを持たないソリューションはやめてもいいのではないでしょうか?

関係ないかも

Linked ListやDoublely Linked List と同様に、 andを実装するためにDoublely Linked Listを使用する必要がStackありQueueますか?

4

7 に答える 7

11

親ポインタなしでツリーを使用するのには十分な理由があり、メモリ使用量は問題ではありません。

関数型プログラミングの世界 (Lisp、Scheme、Standard ML、OCaml、Haskell、F# などを考えてください) では、ツリーと連結リストは非常に一般的なデータ構造です。 FP。ツリーとリストは再帰的に定義され (ツリーはリーフまたは子がツリーである内部ノードのいずれかであり、リストはnilデータ要素とリストが添付されたノードまたはノードのいずれかです)、ほとんどの場合、不変のデータ構造として実装されます。 不変性は、並列処理がよりクリーンになり (プログラマーに見えるロックがなくなる)、関数間のデータ共有がより適切になり (データをコピーする必要がなくなる)、証明がより簡単になるため、役立ちます。

親ポインターまたは二重リンク リストの問題は、不変性が突然窓の外に出てしまうことです。不変オブジェクトでは、作成時にオブジェクトに関するすべてを指定する必要があります。したがって、不変性を維持したい場合は、子が作成されるまでノードを作成することはできません (これらの子は作成時に指定する必要があるため)。親が作成されました (親が存在しないため)。言い換えれば、不変性は循環依存ではうまく機能しません。同様に、ミューテーションがなければ、2 番目のノードが作成されるまで最初のノードを作成できないため、2 重リンク リストを作成することはできません。

FP 関係者は、厳密に不変のデータ構造を使用して多くのコードを記述し、多くの有用なプロパティを起動することを証明しています。確かに、親ポインタを維持することは、プログラマの作業をより困難にします。なぜなら、ツリー内の 1 つのノードを変更するとすぐに、そのすべての子の親ポインタを変更しなければならないためです。これは面倒です。

リストとツリーに関する多くの考え方は、親ポインターや二重リンク リストを含まない FP の影響を受けており、親ポインターを維持することはバグが発生しやすいトリッキーな作業であるため、多くの C ツリー実装では親ポインターを使用しません。 .

また、もう 1 つ注意してください。スタックとキューに連結リストと二重連結リストを使用することについてお尋ねします。スタックを実装するために二重にリンクされたリストを使用する必要はありません。これは、最初の要素 (およびスタックが変更可能な場合は 2 番目の要素) 以外の要素を効率的にトラバースする必要がないためです。償却された一定時間のキュー操作を提供する、2 つのスタックを持つキューを実装するためのかわいいトリックがあります。ただし、それを使用していない場合、キューは双方向リンクリストまたは配列の適切な使用例でもあります。

于 2012-05-03T07:15:57.813 に答える
9

ツリーは、通常の/単純な操作に親ポインタを必要とすることはめったにありません。親ポインターが必要になるのは、特殊なこと (葉からノードに戻るパスをたどるなど) を行う場合のみです。

歴史的な理由はありますか？単純に RAM/DISK 容量の制限があるのであれば、親ノードを持たないソリューションはやめてもいいのではないでしょうか?

いくつかの歴史的な理由もあります。また、メモリの制約により、最小で最もコンパクトな構造を使用する必要があります。今日でも、厳しいメモリ要件を持つ組み込みシステムがあります。また、機能する既存のコードをいじりたくないので、これらのことは固執します。

だから私の質問は、親ノードのない構造に基づくいくつかのソリューションがあるのはなぜですか?

おそらく、アプリケーションが親にそれほど頻繁にアクセスする必要がなかったためです。これは典型的な時空トレードオフであることに注意してください。

Linked List や Doublely Linked List と同様に、Stack と Queue を実装するために Doublely Linked List を使用する必要がありますか?

それは、アプリケーションと、データ構造が操作ごとに提供する必要がある保証によって異なります。また、XOR リンク リストの検索にも興味があるかもしれません。

于 2012-05-03T07:13:06.837 に答える
4

多くのアルゴリズムでは、親ポインターは不要です。ただし、メモリの消費と追加のアルゴリズムの複雑さが発生します。

連結リストと二重連結リストのように...

違いは、後者はO(1)時間の複雑さでより多くの操作を実行できることです。コストは、追加のメモリ オーバーヘッドです。つまり、時間と記憶のトレードオフがあります。

スタックとキューを実装するために双方向リンク リストを使用する必要がありますか?

両方とも、双方向リンク リストを使用して実装できます。ただし、2 つの構造のうちの 1 つ (スタックなのかキューなのかは、あなたに任せます!) では、二重にリンクされたリストの余分なオーバーヘッドはまったく役に立ちません。

于 2012-05-03T07:10:46.197 に答える
1

「ツリーに」ジャンプするコードがある場合にのみ、親ノードが必要です。たとえば、Web ブラウザーでは、常にイベント ハンドラーで DOM 要素を取得し、そこから DOM ツリーを上に移動して親 HTML 要素を見つける必要があります。

ただし、多くのデータ構造では、通常、ルートから開始して、深さ優先または幅優先のいずれかで下ります。問題ではありません。どこから開始したかはわかっているため、親参照は必要ありません。

http://en.wikipedia.org/wiki/Depth-first_search

http://en.wikipedia.org/wiki/Breadth-first_search

基本的に、アルゴリズムがデータ構造を決定します。両方とも一緒です。一方を考慮せずに考えるのは役に立ちません。

于 2012-05-03T07:08:53.603 に答える
1

二分木は、親ノードへの参照を必要とする操作を定義しません。常に上から下にトラバースします。

于 2012-05-03T07:08:56.817 に答える
1

赤黒ツリーや AVL ツリーなどのほとんどのバランスの取れたツリーには、ノード構造に親ポインターが埋め込まれています。そして、それらはいくつかの追加のプロパティを持つ二分探索木です。その理由は、必要なリバランス操作の実行がはるかに簡単になるためです。

親ポインターがないと非常に扱いにくいシナリオもいくつかあります。

二分探索木を考えてみましょう。そこから無作為に犠牲ノードを選びます。どうやって木から取り除くのですか？親ポインターがないと、ツリー内のどこにあるかわからないため、検索を実行してその親を見つけ、どのエッジを更新するかを知る必要があります。親ポインターを使用すると、代わりに大まかに次のようになります。

parent = victim->parent;
if (parent) {
    if (parent->left == victim) {
        parent->left = NULL;
    } else {
        parent->right = NULL;
    }
}
... free(victim);

親ポインターを使用しないと難しい別の操作は、ノードの後継者を見つけることです。特に、ツリーで同じキー値を持つ複数のオブジェクトを格納できる場合は、マルチセットを実装する場合に必要です。しかし、それらを使えば簡単です:

bstree *successor(bstree *node) {
    // If node has a right child, the successor is the minimum 
    // node of that subtree.
    if (node->right) {
        return minimum(node->right);
    }
    // If node hasn't, we look upwards.
    bstree *x = node->parent;
    while (x && node == x->right) {
        node = x;
        x = node->parent;
    }
    return x;
}

親ポインターは、データ構造の美しさを損ないます。彼らは、残念なことに、木をもはや木の構成として扱うことができないようにしています。しかし、私が見たツリー構造のほとんどの実用的な実装では、それらが非常に便利であるため、そこに存在します。

于 2016-11-01T12:47:47.087 に答える
0

一部のバランス ツリーの実装では、親へのポインターが維持されます。Glib Balanced Treesには、そのようなポインターを含むノードがあるようです。

ただし、ツリーをトラバースする内部再帰関数がある場合は、再帰呼び出し中にツリーとその直接の親の両方を渡すようにコーディングできます。

于 2012-05-03T07:10:35.740 に答える