Kırmızı-siyah ağaçlar 2-3-4 ağaçlara nasıl izomorfiktir?

Question

Ben de kırmızı siyah ağaç ve 2-3-4 ağaçları ve nasıl kötü durum operasyonları O (n logn) olduğundan emin olmak için yükseklik dengesini korumak temel bir anlayışa sahip.

Ama onlar eşdeğer veri yapıları vardır, yani kırmızı-siyah ağaçların bir izometridir Wikipedia

2-3-4 ağaçlardan bu metni anlamak mümkün olan değilim. Diğer bir deyişle, her 2-3-4 ağaç için, aynı düzende veri elemanları içeren en az bir kırmızı-siyah ağaç vardır. Ayrıca, düğüm genişlemesine, ayrışmasına ve birleşmesine neden olan 2-3-4 ağaçların yerleştirilmesi ve delesyon işlemleri, kırmızı-siyah ağaçlardaki renk-saygısız ve dönüşlere eşdeğerdir.

Ben işlemleri eşdeğerdir nasıl görmüyorum. Bu alıntı Wikipedia'da doğru mu? Operasyonların eşdeğer olduğunu nasıl görebiliriz?

Answer 1

rb-ağacı (kırmızı-siyah-ağacı) 2-3-4-ağacına izomorfik değildir. Çünkü bu 3 düğümün bir rb ağacına eşleştirilmesi için 2-3-4 ağacındaki 3 düğümün sola veya sağa sola dönüşebilir. Ama lblb ağacı (Sol yaslanmış kırmızı-siyah ağaç) yapar. Robert Sedgewick (bölüm Introduction yılında) den

Kelimeler:

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 

Ayrıca Page29 ve Robert Sedgewick'e dan presentation arasında Page30. Bu LLRB ağacıyla ilgili bir sunum.

ve wikipedia "kırmızı, siyah Ağaç" bölümünde "sırası 4, B-ağaç için benzerlik", iyi bir grafik bulunmaktadır.