AVL, Red-Black Tree

균형 이진 탐색 트리(Balanced Binary Search Tree)

균형 이진 검색 트리는 모든 노드의 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 최대 1인 트리를 말한다. 노드의 삽입과 삭제가 일어 날 때 균형을 유지하도록 하는 트리이다. 

 

왼쪽은 불균형 트리, 오른쪽은 균형트리

---

AVL 트리

AVL트리는 균형 이진 검색 트리의 일종으로, 균형 이진 탐색 트리와 같이 서브간의 높이가 최대 1인 트리를 말한다. AVL 트리는 Adelson-Velsky와 Landis에 의해 개발 되었으며, 이들의 이니셜을 따서 AVL 트리라는 이름이 붙여졌다.

 

AVL 트리의 높이는 O(log N) 이므로, 검색, 삽입, 삭제의 시간 복잡도는 모두 O(log N)이다. AVL트리는 이진 검색 트리의 특성을 그대로 가지며, 높이 균형을 유지하면서 데이터를 추가하거나 삭제할 수 있다. 

 

AVL 트리에서는 노드를 삽입하거나 삭제할 때, 균형을 유지하기 위해 회전 연산을 수행한다. 방법으로는 각 노드의 BF(Balance Factor)룰 [-1, 0,1]만 가지게 하여 균형을 유지 한다. 

 

BF(Balance Factor)
왼쪽 서브 트리 높이 - 오른쪽 서브 트리 높이

 

AVL 리밸런싱 (Re-Balancing)

균형이 깨진경우 BF값에 따라 균형을 맞추는 잡업을 수행한다. 

• BF가 ' + ' 이면 왼쪽 서브 트리에 이상이 있다는 것이다. 
• BF가 ' - ' 이면 오른쪽 서브 트리에 이상이 있다는 것이다.

 

회전연산

• 단순 회전 : LL(Left-Left), RR(Right-Right)
• 이중 회전: LR(Left-Right), RL(Right-Left)

LL : 회전 1회, 오른쪽 회전

RR : 회전 1회, 왼쪽방향 회전

LR : 회전 2회, RR 회전 후 LL 회전

RL : 회전 2회, LL 이후 RR

---

Red-Black 트리

Red-Black Tree는 이진 검색 트리의 일종으로, 모든 노드에 레드 또는 블랙 색상을 부여하여 균형을 유지하는 트리 자료구조이다.

 

Red-Black Tree는 높이가 log N 이하인 균형 이진 검색 트리이므로, 검색, 삽입, 삭제 연산의 시간 복잡도는 모두 O(log N)이다. 삽입과 삭제 연산에서는 레드-블랙 트리의 규칙을 만족하기 위한 회전 연산이 수행되며, 이러한 회전 연산은 레드-블랙 트리가 균형을 유지하도록 한다.

조건

• Root 노드와 Leaf 색은 Black 이다.
• red 색 노드의 자식은 black 이다(double red는 불가함)
• 모든 Leaf 노드에서 root 노드까지 가는 경로의 black 노드 수는 같다. 
• 조건이 깨지는 상황에서 Rebalancing을 한다. 

 

Red-Black 트리 - 삽입 (1)

• 노드 삽입 후 double red가 발생하는 case
  • 부모 노드와 부모의 형제 노드가 red 일 때
• Recoloring 작업을 진행 
  • 삽입한 노드의 부모와 부모의 형제 노드를 black으로 변경
  • 부모의 부모 노드를 red로 변경
  • 부모의 부모 노드가 root 인지 double red 인지에 따라 조정 진행.

 

Red-Black 트리 삽입 (2)

• 노드 삽입 후 double red 발생하는 case
  • 부모 노드의 형제 노드가 black 이거나 없을 때
• Recoloring 작업을 진행
  • 조정대상 : 삽입한 노드, 부모 노드, 부모의 부모 노드
  • 조정 대상 노드들을 오름차순 정렬
  • 가운데 노드를 부모 노드로 선정하고 black으로 변경
  • 나머지 두 노드를 자식 노드로 두고 red로 변경

 

Red-Black 트리 - 삭제(기본)

• 삭제 대상 노드가 black이고 그 자리에 오는 노드가 red인 경우
  • 해당 자리로 오는 red 노드를 black으로 변경 

 

Red-Black 트리 - 삭제(이중 흑색1)

• 삭제 대상 노드가 black, 그 자리에 오는 노드가 black인 경우
• 이중 흑색 노드의 형제 노드가 black이고, 형제 양쪽 자식이 모두 black 인 경우
  • 형제 노드를 red로 변경
  • 이중 흑색 노드의 검은색 1개를 부모 노드로 전달
  • 부모가 root가 아닌 이중 흑색 노드가 되면 해당 case 반복 진행

 

Red-Black 트리 - 삭제(이중 흑색2)

• Double Black case
• 이중 흑색 노드의 형제 노드가 red인 경우
  • 형제 노드를 Black으로 변경
  • 부모 노드를 Red로 변경
  • 부모 노드를 기준으로 왼쪽으로 회전
  • 그 다음 이중 흑색 case에 따라 반복 진행 

 

Red-Black 트리 - 삭제 (이중 흑색 3-1)

• Double Black case
• 이중 흑색 노드의 형제 노드가 Black이고, 오른쪽 자식이 red인 경우
  • 부모 노드와 형제 노드의 오른쪽 자식 노드를 검은색으로 변경
  • 부모 노드를 기준으로 왼쪽으로 회전

 

Red-Black 트리 - 삭제 (이중 흑색 3-2)

• Double Black case
• 이중 흑색 노드의 형제 노드가 black 이고, 왼쪽 자식이 red인 경우
  • 형제 노드를 red로 변경
  • 형제 노드의 왼쪽 자식 노드를 black으로 변경
  • 형제 노드를 기준으로 오른쪽으로 회전
  • 이중 흑색 3-1 case 진행 

---

Red-Black 트리 vs AVL 트리

- 알고리즘 복잡도

• 둘 다 O(log N)

- 균형 수준

• AVL 트리가 Red-Black 트리 보다 좀 더 엄격하게 균형을 잡음.
• Red-Black 트리는 색으로 구분하는 경우로 인해 회전수가 감소

- 실 사용시

• Tree 체계가 잡힌 후, 탐색이 많은 경우에는 AVL 트리가 유리
• 삽입, 삭제가 빈번한 경우에는 Red-Black 트리가 유리