이진 트리의 밸런싱: AVL 트리, Red-Black 트리

앞선 게시물에서 이진 트리가 편향될 때 시간 복잡도가 어떻게 악화되는지 ( O(log n) ➡️ O(n) ) 알아보았다. 이번에는 밸런싱을 통해 어떻게 편향 문제를 해결할 수 있는지 알아본다.

AVL 트리

BF

• BF(Balance Factor): 왼쪽 서브 트리의 height - 오른쪽 서브 트리의 height
• BF의 허용 범위: -1 이상 1 이하. 이를 벗어나면 균형이 깨지기 때문에 rebalancing이 요구된다.

Rotation

Rebalncing은 Rotation을 통해 수행된다. BF가 허용 범위를 벗어난 노드를 기준으로 rotation이 이루어진다.

Single Rotation

• LL or RR case에서 수행된다. (오른쪽 자식의 오른쪽 자식, 또는 왼쪽 자식의 왼쪽 자식에 새로운 노드가 추가되며 균형이 깨진 경우)
  
• Rotation 대상인 서브트리의 루트노드를 자식노드의 새로운 자식으로 하고, 기존의 자식노드의 서브트리, 즉 손자 서브트리는 기존의 루트 노드의 서브 트리가 된다.
• 노드의 삭제를 통해 균형이 깨졌을 때도 똑같이 작업한다.

Double Rotation

• LR or RL case에서 수행된다. (오른쪽 자식의 왼쪽 자식, 또는 왼쪽 자식의 오른쪽 자식에 새로운 노드가 추가되며 균형이 깨진 경우)
  
• 서브트리의 서브트리부터 Rotation을 하고, 그 후 Rotation 대상인 서브트리의 루트노드를 해당 노드의 서브트리의 자식으로 하면서 다시 Rotation한다.
• 노드의 삭제를 통해 균형이 깨졌을 때도 똑같이 작업한다.

Red-Black 트리

규칙

1. 모든 노드는 Red 또는 Black
2. 루트 노드는 Black
3. leaf 노드는 Black (모든 leaf 노드는 NIL이고, NIL은 Black이다)
4. Red 노드의 자식은 모두 Black (Black의 자식은 Red, Black 둘 다 가능)
5. 특정 노드에서 leaf 노드까지의 경로에는 모두 같은 수의 Black 노드를 가진다. (즉 Black depth가 같다)
   위의 규칙들에 어긋난다면 노드의 재배치가 필요하다.

RB 트리의 높이

4번 규칙에 의해, Red 노드는 부모-자식에서 연속적으로 나올 수 없다.
따라서 높이 h인 노드의 bh(자기 자신을 제외한 leaf까지의 black 노드의 개수)는, bh>=h/2다.

삽입

일반적인 BST와 동일하게 삽입 후, 규칙 위반을 검사하여 재조정한다.

• 삽입하는 노드는 항상 Red다. (5번 조건을 위함)
• 규칙 위반 시 rotation을 통해 height를 조정한다.
  즉, 새로 삽입한 노드의 부모가 black이라면 상관이 없지만, red라면 4번 규칙에 위반된다.
  이러한 red-red 충돌의 수정이 필요하다. 해결법은 다음 3가지 상황으로 나뉜다.

1. 새로 추가된 노드의 삼촌 노드(부모의 형제 노드)가 red일 때
   이러한 경우, 새로운 노드는 red를 유지하고, 부모와 형제 노드를 black으로 바꾼다. 이 후 할아버지 노드를 red로 바꾼다. 이렇게 되면, 할아버지-부모,삼촌-새로운 노드 간에는 4번 규칙을 유지하게 되지만 할아버지와 그 부모 노드간의 red-red 문제가 발생할 수 있다. 이러한 문제는 다시 해당 노드의 레벨에서 해결한다.
2. 새로 추가된 노드가 오른쪽 자식이고, 새로 추가된 노드의 삼촌 노드(부모의 형제 노드)가 black인 경우
   새로운 노드와 그 부모에 대해 left-rotation 하고, case 3으로 진행한다.
3. 새로 추가된 노드가 왼쪽 자식이고, 새로 추가된 노드의 삼촌 노드(부모의 형제 노드)가 black인 경우
   새로운 노드의 부모를 black으로 바꾸고, 할아버지를 red로 바꾼다. 이후 새로운 노드의 부모와 할아버지에 대해 right-rotation을 한다.
   그림 참고

삭제

일반적인 BST와 동일하게 삭제 후, 규칙 위반을 검사하여 재조정한다.
1. 삭제한 노드가 Red인 경우, 추가 작업이 필요없다.
2. 삭제한 노드가 Black인 경우, 상황에 따른 조정이 필요하다.

• 기본 작업: 삭제된 노드의 자리를 대체하는 노드를 Black으로 변경한다.
• 기본 작업 대상의 노드가 원래 Black이었다면, 해당 노드는 이중 흑색 노드가 된다. 이중 흑색 노드의 처리는 상황에 따라 다르다. 아래 설명은 이중흑색노드가 부모의 왼쪽자식일 경우를 기준으로 설명한다.

1. 이중흑색노드의 형제가 Red인 경우

• 형제를 Black, 부모를 Red로 한다. 이 후, 부모와 형제를 기준으로 left-rotation 한다.

2. 이중흑색노드의 형제가 Black인 경우

• 형제의 양쪽 자식 둘 다 Black인 경우, 형제를 Red로 하고, 이중흑색노드의 Black 하나를 부모에게 전달한다. 이를 통해 이중흑색노드는 단일 Black이 된다. 부모가 Red라면 Black이 되지만, 원래 부모가 Black이라면 이중흑색노드가 된다.
• 형제의 왼쪽 자식이 Red, 오른쪽 자식이 Black인 경우, 형제를 Red, 형제의 왼쪽 자식을 Black으로 한다. 이 후 형제를 기준으로 right-rotation한다.
• 형제의 오른쪽 자식이 Red인 경우, 부모 노드의 색을 형제에게 넘긴다. 부모 노드와 형제 노드의 오른쪽 자식을 검은색으로 칠한다. 부모 노드 기준으로 left-rotation한다.
  참고

AVL vs Red-Black

공통점

둘 모두 키의 삽입이나 삭제 시 이진 탐색 트리를 밸런싱한다.

차이점

Red-Black 트리가 AVL 트리에 비해 상대적으로 노드의 재배치 가능성이 적다. 따라서 AVL이 더 균형을 이룬다.

• 따라서 AVL이 Red-Black에 비해 더 빠른 조회가 가능하다. (균형)
• Red-Black의 회전 횟수가 상대적으로 AVL에 비해 적기 때문에 (느슨한 균형) 더 빠른 삽입 / 삭제가 가능하다.
• AVL은 노드마다 BF 저장을 위한 int가 요구되지만, Red-Black은 1비트만 있으면 된다. (Red or Black)

따라서 삽입/삭제 연산이 많은 경우 Red-Black, 연산이 적고 탐색이 많은 경우 AVL을 사용하는 것이 좋다. 일반적으로 Red-Black은 대부분의 언어 라이브러리에서, AVL은 빠른 탐색이 필요한 DB 등에서 사용한다.

시간복잡도

둘 모두 균형을 유지하는 BST이기 때문에 O(log N)의 삽입, 삭제, 검색 시간복잡도를 가진다.