red-black tree

red-black tree 

규칙

1. 모든 노드는 black or red
2. 루트 노드는 black
3. 리프 노드는 black
4. red 노드의 자식은 black, black 노드 자식은 black or red
5. 모든 리프 노드까지의 black node 개수는 동일해야한다.

insert

• 새로운 노드는 red
• parent 노드가 red && sibling 노드도 red
• recoloring(both nodes color black)
• parent 노드가 red && new 노드가 parent 노드의 right child && sibling 노드는 black : parent 노드를 좌회전함
• parent 노드가 red && new 노드가 parent 노드의 left child && sibling 노드는 black
  : parent 노드를 black으로 칠하고 grand parent 노드를 red로 칠하고 gp를 우회전함

delete

• 삭제한 노드가 red일 경우 규칙에 영향을 미치지 않으므로 뒷처리를할 필요가 없다. 그냥 삭제하면 됨
• 삭제한 노드의 sibling이 red인 경우

1. sibling 노드를 black으로 칠함
2. parent 노드를 red로 칠함
3. parent 노드를 좌회전함

• sibling 노드는 black && sibling 노드의 양쪽 자식이 모두 black

1. sibling 노드를 red로 칠함
2. parent 노드를 black으로 칠함

• sibling 노드는 black && sibling's left 는 red && sibling's right는 black

1. sibling 노드를 red로 칠함
2. sibling 노드의 left child를 black으로 칠함
3. sibling 노드를 우회전함

• sibling 노드는 black && sibling's left는 black && sibling's right는 red

1. parent 노드의 색을 sibling 노드에 칠함
2. parent 노드와 sibling's right 노드를 black으로 칠함
3. parent 노드를 좌회전함

위의 delete 과정을 이해해보자.

삭제한 노드가 red인 경우 트리에 영향을 미치지 않으므로 reconstruct만 하면 된다. 

sibling 노드가 red인 경우에는 sibling 노드를 black으로 칠하고 parent 노드를 red로 칠한다. 하지만 이는 아직 reconstruct가 되지 않았다. 따라서 노드의 상황에 따라 sibling 노드는 black이지만 sibling 노드의 left, right child에 따라 다르게 reconstruct 해야한다.