レッドブラックツリー挿入ケース

Question

これは非常に簡単な質問かもしれませんが、私は満足のいく答えを見つけることができませんでした。ノードは赤黒木に挿入された後、三つの異なるケースが発生することができる。

新たに追加されたノード= Z

ケース1：Z =赤、赤Z =の親、Zの叔父=赤

ケース2：Z =赤、Z =赤、Z =右の子の親、Z =黒

ケース3の叔父：Z =赤、Z =左の子のZ =赤、親、叔父z =黒の

しかし、ケース2またはケース3に直接入ることはできないと思いますxとyはそれぞれ兄弟で、赤と黒であるとします。ノードxの下にzを挿入すると、ケース1に入ることなく、ケース2またはケース3が観測されます。ただし、ノードzを追加する前に、黒の高さのルールが既に破損しているため、 。

  Grandparent 
      /  \ 
     x(red)  y(black) 
     / \  / \ 
    nil(b) nil(b) nil(b) nil(b) 

ノードZは、ノードXのゼロポインタのいずれかに添加することができ、ツリーがこのようなものであることは不可能です。挿入するたびに、赤黒の木はバランスをとる必要があります。

しかし、私のアルゴリズムの教授はこの理論を拒否しました。したがって、私はこの状況を保証することはできません。ケース1、ケース2なしでケース2またはケース3に関与することは可能ですか？

Answer 1

nullは黒であることに注意してください。

それはこのように行われます

  Grandparent 
      /  \ 
     x(red)  nil(b) 
     / \  
    nil(b) nil(b) <-- z goes here