균형 이진 트리 (by 이진 탐색 트리)

👩‍💻  균형 이진 트리란?

균형 이진 트리란? 모든 노드의 좌우 서브 트리 높이가 1이상 차이 나지 않는 트리이다. 

 

✏️ 이진 탐색 트리의 편향 발생

경우 1) 이진 탐색 트리에 삽입 되는 순서 : 20 -> 10 -> 30 -> 5 인 경우에는 균형 이진 트리가 된다.

경우 2) 이진 탐색 트리에 삽입 되는 순서 : 5 -> 10 -> 20 -> 30 인 경우에는 사향 이진 트리가 된다.

 

✏️ Balanced Binary Search Tree

노드의 삽입과 삭제가 일어날 때 균형을 유지하도록 하는 트리

 

종류 :

1. AVL트리
2. Red-Black 트리

 

✨ AVL 트리

• 노드가 삽입, 삭제 될 때 트리의 균형을 체크하고 유지하는 트리
• 각 노드의 BF를 [-1, 0, 1] 만 가지게 하여 균형을 유지
• BF[Balance Factor]
   ㄴ 왼쪽 서브 트리의 높이 - 오른쪽 서브 트리의 높이

💫 AVL트리의 리밸런싱 

1. 균형이 깨진 경우 : 

• BF가 '+' 이면 왼쪽 서브 트리에 이상이 있음
• BF가 '-' 이면 오른쪽 서브 트리에 이상이 있음

2.  회전 연산 : 

• 단순 회전 - LL, RR
• 이중 회전 - LR, RL

2-1)

• LL (Left-Left) 
  • 회전 1회 
  • 오른쪽 방향으로 회전
• RR (Right-Right)
  • 회전 1회 
  • 왼쪽 방향으로 회전
• LR (Left-Right)
  • 회전 2회
  • RR 회전 후 LL 회전 (왼쪽으로 방향 회전 후(아래부분을) 오른쪽으로 방향 회전)
• RL (Right-Left)
  • 회전 2회
  • LL회전 후 RR회전 

 

 

✨ Red-Black 트리

red와 black으로 구분하여 (클래스에서) 아래의 조건을 따라 균형을 맞추어 나가는 트리이다.

AVL트리에 비해서는 직관적이지 않다.

 

✔︎ 조건

• root 노드와 leaf 노드의 색은 black (단 여기서 leaf노드는 기존의 개념과 약간 다르게 정의한다)
• red 색 노드의 자식은 black(double red 불가)
• 모든 leaf 노드에서 root 노드까지 가는 경로의 black노드 수는 같음

조건이 깨지는 상황에서 Rebalancing! 으로 균형 유지

 

💫 Red-Black 트리의 삽입

case1) 노드 삽입 후 double red 발생 : 부모 노드의 형제 노드가 red 일때

✔︎ Recoloring 진행 :

• 삽입한 노드의 부모와 부모의 형제 노드를 black 으로 변경
• 부모의 부모 노드를 red로 변경
• 부모의 부모 노드가 root인지 double red인지에 따라서
  블랙으로 냅둘지, red로 변환후 반복해서 위의 노드와 비교해 recoloring 할지 경정

 

case2) 노드 삽입 후 double red 발생 : 부모 노드의 형제 노드가 black이거나 없을 때

✔︎ Restructuring 진행 : (회전 연산)

• 조정 대상 : 삽입한 노드, 부모 노드, 부모의 부모 노드
• 조정 대상 노드들을 오름차순 정렬
• 가운데 노드를 부모 노드로 선정하고 black으로 변경
• 나머지 두 노드를 자식 노드로 두고 red로 변경

 

💫 Red-Black 트리의 삭제

✔︎ 삭제 대상 노드가 black 이고 그 자리에 오는 노드가 red인 경우

• 해당 자리로 오는 red 노드를 black으로 변경

✔︎ 삭제 대상 노드가 black 이고 그 자리에 오는 노드가 black인 경우 (이중 흑색 케이스 2가지 방법)

case1) "이중 흑색 노드"의 형제 노드가 black 이고, 형제의 양쪽 자식 모두 black인 경우

• 형제 노드를 red로 변경
• 이중 흑색 노드의 검은색 1개를 부모 노드로 전달
• 부모가 root가 아닌 이중 흑색 노드가 되면 해당 case 반복 진행

 

case2) "이중 흑색 노드"의 형제 노드가 red인 경우

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

 

case3-1) "이중 흑색 노드"의 형제 노드가 black이고, *오른쪽 자식이 red인 경우

• 부모 노드와 형제 노드의 오른쪽 자식 노드를 검은색으로 변경
• 부모 노드를 기준으로 왼쪽으로 회전 

case3-2) "이중 흑색 노드"의 형제 노드가 black이고, *왼쪽 자식이 red인 경우

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

 

✏️ "Red-Black 트리" VS "AVL 트리"

✨ 알고리즘 시간 복잡도 

둘 다 O(logN)

 

✨ 균형 수준

AVL트리가 Red-Black 트리 보다 좀 더 엄격하게 균형을 잡음

Red-Black 트리는 색으로 구분하는 경우로 인해 회전 수가 감소

 

실 사용시,

Tree 체계가 잡힌 후, 탐색이 많은 경우에는 AVL트리가 유리

삽입, 삭제가 빈번한 경우에는 Red-Black트리가 유리