[Tree] Red-Black 트리

레드블랙 트리는 한 쪽으로 치우치는 트리의 단점을 해결하기위해 나온 알고리즘이다.

 

https://nesoy.github.io/articles/2018-08/Algorithm-RedblackTree

 

 

 

1. 특징

레드-블랙 트리는 4가지의 특징을 가지고 있다.

• 모든 노드는 Red or Black을 가진다.
• 루트 노드는 항상 Black 이다.
• 모든 리프 노드는 Black 이다.
• Red의 자식 노드는 항상 Black 이다.
• 루트에서 리프 까지의 경로를 진행하면 항상 Black 노드의 개수가 같다.

리프 노드는 항상 Black이다. 때문에 메모리 절약을위해서 하나의 리프 노드로 만드는 방법을 이용한다.

 

 

 

 

 

 

 

2. 동작

1) 삽입

Insert하는 노드는 일단 항상 Red 노드이다.

기본적으로 insert할 때는 일반 이진트리와 마찬가지로 작은거(Left node), 큰거 (Right Node)로 자식노드를 추가한다.

 

• Insert 11, 22, 5, 8로 넣었다면

 

위와 같이 Red 노드로 계속 추가하기 때문에 위와 같은 트리 그래프를 가지게 된다.

이렇게 Insert를 하다보면 결국 Double-Red가 되게 된다. 하지만 레드-블랙 트리의 특징상 연속된 레드 노드는 불가하기 때문에 아래 두 가지 방법을 통해서 문제를 해결한다

Recoloring, Restructing

 

 

Recoloring과 Restructing은 부모노드의 형제노드를 보고 어떤 방법을 사용할지를 결정한다.

 

 

2) Recoloring

위 그래프와 같이 부모의 형제노드가 Red일 때는 Recoloring을 진행한다.

가장먼저 부모노드와 부모노드의 형제노드를 Black으로 색을 바꿔준다.

두 번째로 할아버지 노드가 Black이면 Red로 바꾼다(단, 할아버지노드가 루트 노드인 경우에는 검정색유지)

즉 위에서보는 그래프의 경우에는 11이 루트노드이기 때문에 블랙으로 끝이나게 된다.

 

여기서 한 가지 의문점이 생길 수 있습니다. 바로 11이 루트노드가 아니어서 Red 노드로 바뀌는데 11의 부모노드가 Red여서 또 Red-Double이 발생할 수 있는 부분이다.

 

이 경우에는 다시 또 11노드를 기준으로 Recoloring 혹은 Restructing이 발생한다.

 

• Insert 2, 4를 하면

다시 Red-Double이되고 여기서 다시 Recoloring이 진행된다.

그럼 다시 부모노드와 부모의 형제 노드가 다시 Black 노드가되고 할아버지 노드를 Red로 변경한다.

 

 

 

 

3) Restructing

Restructing은 두 가지 케이스에서 발생한다. 부모의 형제노드가 Black인 경우 발생하며 부모의 형제노드가 없는 경우에도 Restructing을 진행한다.

 

위의 노드를 이어서 보면..

 

• Insert 9,10을 하게되면

또 다시 Red-Double이 발생하게 된다. 그리고 여기서 보면 10을 기준으로 부모노드의 형제노드가 없기 때문에 Restructing이 발생한다.

 

Restructing방법은 자신과 부모, 할아버지 노드를 오름차순으로 정렬한다.

8 - 9 - 10

으로 정렬된다. 여기서 가운데 숫자인 9를 최상위 노드로하고 8과 10을 양쪽 Left, Right 자식 노드로 노드를 만든다.

이렇게 만들어진 노드에서 최상위 노드는 Black으로, 양쪽 자식 노드는 Red로 색칠한다.

 

그리고 위와 같이 만들어진 해당 노드를

다시 연결해주면 된다.

즉 위와 같은 그래프를 만날 수 있다.

Restructing은 Recoloring과 다르게 재귀형식으로 일어나지 않고 단 한번으로 끝이난다.