[Data Structure] Red-Black 트리

Red-Black 트리는 이진 탐색 트리(Binary Search Tree, BST)의 한 종류로, 각 노드의 추가적인 색깔 정보(빨강 또는 검정)를 부여하고 이를 이용해 트리의 균형을 유지하는 자가균형 이진 탐색 트리이다.

 

 

 

Red-Black 트리의 표현

---

Red-Black 트리는 다음과 같은 규칙을 이용해서 트리의 균형을 유지한다.

• 모든 노드는 빨간색 또는 검은색이다.
• 루트 노드는 검은색이다.
• 리프 노드(NIL)는 검은색이다. (NIL, Null Leaf : 아무 데이터도 갖고 있지 않지만 색만 검은색인 더미 노드)
• 빨간색 노드의 자식노드는 모두 검은색이다. (검은색 노드는 빨간색과 검은색 모두 자식으로 가질 수 있다.)
• 루트 노드와 모든 리프 노드 사이에 있는 검은색 노드의 수는 모두 동일하다.

 

Red-Black 트리 (출처 : 위키피디아)

 

여기서 주의깊게 봐야 할 부분은 Red-Black 트리의 리프 노드(NIL)이다. NIL 노드는 아무 데이터도 갖고 있지 않지만, 색깔만 검은색인 노드(또는 센티넬 노드, Sentinel Node)로, Red-Black 트리의 구현을 용이하게 만들기 위해 사용된다. 원래 리프 노드의 색이 어떤 것이든, NIL 노드를 양쪽 자식으로 연결하면 '모든 잎 노드는 검은색이다'라는 규칙을 항상 지킬 수 있기 때문이다.

 

 

Red-Black 트리의 특징

---

1. 트리의 높이 균형 유지

트리가 항상 균형을 유지하도록 설계되어 있기 때문에 삽입 및 삭제 연산 후에 규칙에 맞게 색깔 변환과 회전 연산을 사용하여 스스로 균형을 유지하기 때문에 성능 저하가 발생하지 않는다.

 

 

2. 트리의 높이 제한

'루트 노드와 모든 리프 노드 사이에 있는 검은색 노드의 수는 모두 동일하다'는 규칙으로 인해 Red-Black 트리의 높이는 2log(n+1) 이하로 제한된다. 

 

 

3. 빠른 탐색, 삽입, 삭제 연산

Red-Black 트리는 항상 균형을 유지하기 때문에 탐색, 삽입, 삭제 연산의 O(log N) 시간 복잡도를 항상 보장한다. 균형을 유지하기 위한 회전 연산 또한 O(log N) 시간 복잡도를 가진다.

 

 

- AVL 트리와 Red-Black 트리 비교

균형 유지 방식

1. 균형 조건:
   • AVL 트리: 모든 노드에서 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이(균형 인수)가 -1, 0, 1 중 하나여야 합니다. 이 때문에 AVL 트리는 매우 엄격하게 균형을 유지합니다.
   • Red-Black 트리: 모든 경로에서 검정색 노드의 수가 동일해야 하며, 빨간색 노드는 연속해서 나타날 수 없습니다. 이 규칙을 통해 균형을 유지하지만, AVL 트리보다 덜 엄격합니다.
2. 균형 유지 방법:
   • AVL 트리: 삽입 및 삭제 후에 균형 인수를 확인하고 필요시 회전 연산(단일 및 이중 회전)을 사용하여 균형을 맞춥니다.
   • Red-Black 트리: 삽입 및 삭제 후에 색깔 변환과 회전 연산(좌회전, 우회전)을 사용하여 균형을 맞춥니다.

회전 연산

1. 회전 빈도:
   • AVL 트리: 더 엄격한 균형 조건 때문에 삽입과 삭제 시 더 자주 회전이 발생합니다.
   • Red-Black 트리: 덜 엄격한 균형 조건 때문에 상대적으로 회전이 덜 발생합니다.

연산 성능

1. 삽입 및 삭제:
   • AVL 트리: 삽입 및 삭제 연산이 더 자주 회전을 필요로 하므로 이 연산들이 더 느릴 수 있습니다. 하지만 이러한 연산들이 많지 않은 경우에는 큰 문제가 되지 않습니다.
   • Red-Black 트리: 삽입 및 삭제 연산에서 평균적으로 더 적은 회전이 필요하므로 이러한 연산들이 상대적으로 더 빠를 수 있습니다.
2. 검색:
   • AVL 트리: 엄격한 균형을 유지하기 때문에 검색 연산에서 최적의 성능을 보입니다.
   • Red-Black 트리: AVL 트리보다 덜 엄격하게 균형을 유지하지만, 여전히 O(log⁡n)O(\log n)O(logn)의 검색 성능을 보장합니다.

높이

1. 트리 높이:
   • AVL 트리: 트리의 높이가 더 낮습니다 (1.44log⁡(n+2)−0.3281.44 \log(n + 2) - 0.3281.44log(n+2)−0.328). 이는 트리가 더 균형 잡혀 있음을 의미합니다.
   • Red-Black 트리: 트리의 높이가 상대적으로 더 높습니다 (2log⁡(n+1)2\log(n + 1)2log(n+1)). 이는 트리가 덜 균형 잡혀 있음을 의미합니다.

 

응용 분야

1. AVL 트리: 검색이 빈번하고 삽입 및 삭제가 상대적으로 적은 응용 프로그램에 적합합니다. 예를 들어, 데이터베이스 인덱스, 라우팅 테이블 등에서 많이 사용됩니다.
2. Red-Black 트리: 삽입 및 삭제 연산이 빈번한 응용 프로그램에 적합합니다. 예를 들어, 자바의 TreeMap 및 TreeSet, C++의 std::map 및 std::set 등이 Red-Black 트리를 기반으로 구현되어 있습니다.

요약

• AVL 트리는 더 엄격하게 균형을 유지하여 검색 성능이 뛰어나지만, 삽입 및 삭제 시 더 많은 회전이 필요할 수 있습니다.
• Red-Black 트리는 덜 엄격하게 균형을 유지하여 삽입 및 삭제 성능이 상대적으로 더 좋지만, 검색 성능은 AVL 트리에 비해 약간 떨어질 수 있습니다.