これら 2 種類の木はどのように同等なのでしょうか?
3188 次
2 に答える
5
ウィキペディアには、この件について次のように書かれています。
2-3-4 木は赤黒木の等長図であり、同等のデータ構造であることを意味します。つまり、2-3-4 ツリーごとに、データ要素が同じ順序の赤黒ツリーが少なくとも 1 つ存在します。さらに、ノードの拡張、分割、およびマージを引き起こす 2-3-4 ツリーの挿入および削除操作は、赤黒ツリーの色反転および回転と同等です。赤黒木への導入では、概念的に単純であるため、通常、最初に 2-3-4 木を紹介します。
より具体的な回答が必要な場合は、より具体的な質問をしていただければ幸いです。
于 2012-08-03T21:14:03.433 に答える
2
2-3-4 ツリーを赤黒ツリーに変換するには、3 つの子ツリーに赤いノードを導入し、4 つの子ツリーに 2 つの赤いノードを導入します。結果のツリーはバイナリ ツリーになります。このように、2-3-4 木は赤黒木に相当します。
于 2012-08-03T21:13:48.613 に答える