빨간 검은 나무 삽입 케이스

Question

이것은 매우 쉬운 질문 일 수 있지만 만족할만한 대답을 찾을 수 없습니다. 노드는 레드 - 블랙 트리에 삽입 된 후, 세 가지 경우가 발생 될 수

새롭게 추가 된 노드 = Z

사례 1 = 빨간색, Z = 빨간색 Z의 부모, Z의 삼촌 = 빨간색으로

케이스 2 : Z = 빨간색, Z = 빨간색, Z의 삼촌 = 검정색 Z = 오른쪽 아이

케이스 (3)의 상위 : Z = 빨간색, Z의 부모 = 빨간색, Z = 좌측 아이 삼촌 z = black의

그러나 사례 2 또는 사례 3을 직접 입력 할 수는 없다고 생각합니다. x와 y는 각각 형제이고 빨강과 검정이라고 가정합니다. 노드 x 아래에 z를 삽입하면 케이스 1에 들어 가지 않고 케이스 2 또는 케이스 3이 관찰 될 수 있습니다. 그러나 노드 z를 추가하기 전에 블랙 - 높이 규칙이 이미 깨 졌으므로 적 - 검은 나무가 균형을 이루지 못합니다 .

노드 z는 노드 x의 nil 포인터 중 하나에 추가 될 수 있지만 트리가 이와 같이 불가능합니다. 삽입 할 때마다 빨강 - 검정 나무가 균형을 이루어야합니다.

그러나 내 알고리즘 교수는이 이론을 거부했습니다. 그러므로 나는이 상황을 보장 할 수 없다. 케이스 1없이 케이스 2 또는 케이스 3에 관여 할 수 있습니까?

Answer 1

nulls는 검은 색입니다.

그것은 다음과 같이 발생합니다

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