1、2、3、4、および 5 はすべてサブツリーです。ツリー 1、2、3 のルート ノードの色は黒であることがわかっています。ノード 1 ～ 5 のいずれかがリーフ ノードであるかどうかはわかりません。これは、この挿入ケースが、新しく挿入されたノードの祖父母である N で再帰的に呼び出された可能性があるためです (挿入ケース 3 から)。
回転の前後で、サブツリー 1、2、および 3 はすべて 1 つの黒いノードの下にあり (前に G、後は P)、サブツリー 4 と 5 は 2 つの黒いノードの下にあります (前に G と U、後は P と U)。サブツリー 1、2、および 3 はそれぞれ、サブツリー 4 および 5 よりも 1 つ多い黒いノードを持っています。
深読みしたところ、絵に問題があったようです。
N挿入されたばかりのノードであるため、最後のノードの前に子insert[ P1,3] または [2,3] があったことを意味します (挿入は 2 または 1 でした)。その場合、最後の挿入の前にPandUが赤だったに違いありません (そして 4,5 は黒です)。
James さん、Wiki のダイアグラムを解読しておめでとうございます。それは間違っていません、ただあいまいです。
このページの「トーク」タブには、「三角形は葉ではなくサブツリーを表すためのものです。一部のサブツリーには、ルートが黒でなければならないことを示すために上部に黒い円があります。」と記載されています。
明らかに、円のない三角形は、ルート ノードの色とツリーの深さが不明な (おそらく関係のない) サブツリー (葉を含む) を表しています。
したがって、これらの図は、「ルール 5」に違反しているかどうかを判断するのに十分な情報を提供していません。そうではないことを当然のこととして受け止めなければなりません。
