Red-black 트리(개념)

1) Red-black 트리

1-1) Red-black 트리 vs AVL 트리 

- Red-black 트리도 AVL 트리와 유사하게 이진 탐색 트리의 특징을 갖고 있으며, 스스로 균형을 찾는 트리입니다. 

  Red-black 트리는 AVL 트리와 같이 키의 삽입과 삭제 시에 균형을 맞추는 방식을 택하고 있으나,

  노드의 재배치 가능성이 더 적습니다. 

  그래서 AVL 트리보다 덜 균형하고, 노드의 탐색 횟수가 더 많을 수 있습니다. 

  그러나 삽입, 삭제 시 재배치 가능성이 상대적으로 적기 때문에 AVL 트리보다는 삽입, 삭제 성능이 좋을 수 있습니다. 

  즉, 삽입이나 삭제가 많은 경우는 Red-black 트리를 사용하는 것이 더 좋으며, 

  연산이 적고, 탐색이 많은 경우는 AVL 트리를 사용하는 것이 더 좋습니다. 

 

1-1) Red-black 트리의 규칙

- Red-black 트리는 다섯 가지 규칙을 가지고 있는데, 

  첫번째로, Red-black 트리의 이름에 맞게, 모든 노드는 빨강 혹은 검정 노드만 존재합니다. 

  다른 색깔의 노드나, 색깔이 없는 노드는 존재할 수 없습니다.

  두번째로, 루트 노드는 항상 검정 노드여야 합니다. 

  일시적으로 노드를 재배치하는 경우는 빨강 노드일 수 있으나, 최종적으로는 항상 검정 노드여야 합니다. 

 

  세번째는, 모든 Leaf노드는 루트 노드와 동일한 색깔을 갖고 있어야 합니다. 

  여타 트리와 다르게 Red-black 트리는 논리적으로 Null 노드가 존재하는데,

  항상 Leaf 노드는 Null 노드이며, 검정 노드입니다. 

  이러한 특징으로 인해 루트 노드와 Leaf 노드는 항상 동일한 색깔을 갖고 있습니다. 

 

- 네번째는, 모든 빨강 노드의 자식은 검정 노드여야 한다는 것입니다.

  검정 노드의 자식이 검정 노드일 수 있으나, 빨강 노드의 자식이 빨강 노드일 수는 없습니다. 

  이러한 상황을 Double Red라고 부르며, 빨강 노드의 자식이 빨강 노드가 되지 않도록 노드가 재배치됩니다.

 다섯번째로, 노드를 재배치하게 만드는 것 중 하나인 

 특정 노드에서 후손 노드로 가는 경로는 동일한 수의 검정색 노드가 존재해야 한다는 규칙입니다. 

 예시로, 2번 노드에서 1번 노드를 거쳐 리프 노드로 가는 경로에는 2개의 검정 노드가 존재합니다. 

 그리고 다시 2번 노드에서 4번 노드를 거쳐 리프 노드로 가는 경로에는 2개의 검정 노드가 존재합니다. 

 또 다른 예시로 4번 노드 기준으로 봤을 때, 3번 노드를 거쳐 리프 노드로 가는 경로에는 2개의 검정 노드가 있으나,

 우측 자식 노드를 보면 한 개의 검정 노드만 존재합니다. 

 이러한 트리는 Red-black 트리 규칙에 위배되며, 노드를 재배치해야 합니다. 

 

참고

코드라떼 자료구조