赤黒の木と 2-3-4 の木の両方と、それらが高さのバランスを維持して最悪の場合の操作が O(n logn) であることを確認する方法について、基本的な理解があります。
しかし、ウィキペディアからこのテキストを理解することはできません
2-3-4 木は赤黒木の等長図であり、同等のデータ構造であることを意味します。つまり、2-3-4 ツリーごとに、データ要素が同じ順序の赤黒ツリーが少なくとも 1 つ存在します。さらに、ノードの拡張、分割、およびマージを引き起こす 2-3-4 ツリーの挿入および削除操作は、赤黒ツリーの色反転および回転と同等です。
操作がどのように同等かわかりません。ウィキペディアのこの引用は正確ですか? 操作が同等であることをどのように確認できますか?
rb-tree(red-black-tree) は 2-3-4-tree と同型ではありません。この 3 ノードを rb ツリーにマッピングしようとすると、2-3-4 ツリーの 3 ノードが左または右に傾く可能性があるためです。しかし、llrb-tree(左寄りの赤黒木) はそうです。
Robert Sedgewickからの言葉(Introductionセクションで):
In particular, the paper describes a way to maintain
a correspondence between red-black trees and 2-3-4 trees,
by interpreting red links as internal links in 3-nodes and
4-nodes. Since red links can lean either way in 3-nodes
(and, for some implementations in 4-nodes), the correspondence is not necessarily 1-1
また、Robert Sedgewick からのプレゼンテーションの 29 ページと 30 ページ。これは LLRB ツリーに関するプレゼンテーションです。
ウィキペディアの「Red-black Tree」の「Analogy to B-trees of order 4」セクションには、適切なグラフが含まれています。