저번 수업시간에 배운 레드 블랙 트리 우리나라 말로는 적흑 나무에 대해 글을 쓰고자 한다.
한국어로는 적흑나무인데 너무 없어 보여서 레드 블랙 트리라고만 명칭 하겠다.
레드 블랙 트리란?
이진 검색 트리는 저장과 검색에 평균 Θ(logn) 시간이 소요되지만 운이 나쁘면 트리의 모양이 균형을 이루지 못한다. 균형이 많이 깨지면 Θ(n)에 근접한 시간이 소요될 수도 있는데 그런 이진 검색 트리의 균형을 잡기 위해 고안해낸 것이 레드-블랙 트리이다.
레드 블랙 트리는 이진 검색 트리의 모든 노드에 레드 or 블랙의 색상을 칠하고 몇 가지 규칙을 통해 균형을 이룬다.
그 규칙은 아래와 같다.
- 루트는 블랙이다.
- 모든 리프(NIL)는 블랙이다.
- 노드가 레드이면 그 노드의 자식은 반드시 블랙이다.
- 루트 노드에서 임의의 리프 노드에 이르는 경로에서 만나는 블랙 노드의 수는 모두 같다.
1. 레드 블랙 트리에서 삽입
레드 블랙 트리에서 노드를 삽입할 때는 먼저 이진 검색 트리의 삽입 알고리즘에 따라 삽입 한 다음에 새 노드의 색상을 레드로 색칠한다.
이렇게 노드를 삽입하면 부모가 블랙이면 그것으로 삽입이 완료되지만, 부모 노드가 레드인 경우 규칙이 깨지게 되므로 정렬이 필요하다.
이때 정렬을 위해 보아야 할 것이 부모 노드의 형제 노드이다. 우리는 이를 말하기 쉽게 삼촌 노드라고 하겠다.
왜 삼촌 노드만을 보는가? 그것은 이미 레드 블랙 트리의 특성에 따라 부모가 이미 레드여서 문제가 발생할 시 형제 노드가 있다면, 이는 무조건 블랙이고 부모노드의 부모 노드 역시도 무조건 브랙이기 때문이다. 그렇기 때문에 생각해야할 케이스는 삼촌 노드의 색상밖에 없다.
그러므로 삼촌 노드의 색상에 따라 정렬을 위해서 3가지 Case로 나눈다.
Case1. 삼촌 노드가 레드인 경우
부모 노드 : p, 삽입한 노드 : x, 삼촌 노드 : s로 설명하면
우선 p,s의 색을 레드 -> 블랙으로 바꾼다.
그리고 p의 부모노드를 블랙에서 레드로 변경해준다.
p의 부모인 노드의 부모가 색상이 레드라면 똑같은 문제가 발생한다. 그러면 다시 재귀적으로 시작하면 된다.
Case2. 삼촌 노드가 블랙이고, 삽입한 노드가 우측 자식인 경우
좋은 사진
우선 Case2의 경우 좌측 회전을 시킨다.
여전히 규칙을 위반한다. 그러면 Case3으로 간다.
Case3. 삼촌 노드가 블랙이고, 삽입한 노드가 좌측 자식인 경우
위에서 이어진 채로 설명해보겠다.
위 형태에서
우선 정렬해야할 크기순으로 배열로 둔다.
그 후 가운데를 부모 노드로 해서 색을 검정색으로 바꾸고, 나머지 2개 노드를 붉은색으로해서 자식 노드로 둔다.
그러면 아래와 같이 정렬된다.
2. 레드 블랙 트리의 삭제
이제 삽입을 했으니 삭제에 대해 다뤄보자
기본적으로 삭제는 이진 검색 트리의 방법을 따른다. 하지만 그 후 노드의 색상 문제가 생길 수 있다.
그 다양한 케이스를 다뤄볼 생각이다.
Case 1-1
p와 s의 색상을 맞바꾼다.
그럼으로써 어떤 케이스로 가든 특성 4를 만족한다.
Case *-2
p를 중심으로 좌회전 시키고, p와 s의 색상을 바꾼다.
r의 색상을 레드에서 블랙으로 바꾼다.
Case *-3
s를 중심으로 우측으로 회전 시키고 l과 r의 색상을 맞바꾼다.
그 후 Case *-2로 이동한다.
Case 2-1
s의 색상을 블랙 -> 레드
p를 지나가는 경로 전체에서 블랙 노드가 하나 부족한데 이는 원래 위 트리에서의 문제이기 때문에
p를 문제 발생 노드로 하여 재귀적으로 다시 시작한다.
Case 2-4
p를 중심으로 왼쪽으로 회전시키고 p와 s의 색상을 맞바꾼다.
다만 문제가 발생한 x의 부모 노드의 색상이 블랙에서 레드로 바뀌었다. 이제 이 문제는 Case 1에 해당한다.
