알고리즘 ) Red-Black Tree

안녕하세요 :) Zedd입니다. 오늘은 알고리즘 파티인가요?

이 전글 <Amortized Analaysis>와 Red-Black Tree가 같은 강의자료에 있길래..

얼른 iOS글도 써야하는데...ㅎ_ㅎ 뭐 연휴는 기니까....

히유ㅠㅠ강의자료 보다보니까, 이때 생각도 나고 디게 그립네요.

몇달전에 제가 공부하던것들인데 말이에요. 

그 중에서도..네..시험에 Red-Black Tree가 나왔는데..

바닥에 지우개가 떨어져서 줍지도 못하고 그 샤프 뒤에 있는 그 짱쪼끄만 지우개로 지우면서 문제를 풀었던 기억이 있네요ㅎㅎ

그만큼 지우개가 상당히 중요한 Red-Black Tree입니다 ㅎ

간단하게 Red-Black Tree에 대한 글을 써보려고해요 :)

Red-Black Tree

---

이름부터 간지나죠? 우리말로 말하려면.. 적흑.....나무..(한자긴하지만)

....

zzzzzzz 교수님이 이거 배울 때 

한글로 적흑트리, 적흑나무 라고 말한 책도 있는데...우리는...레드블랙트리라고 부르겠습니다..라고 했었다는

네..저도....레드블랙트리라고 하겠습니다 ㅎ

레드블랙트리를 알려면 이진탐색트리(Binary Search Tree)를 아셔야합니다. 

정말정말 간단하게 이진탐색트리(Binary Search Tree)를 설명하자면,

이 이진탐색트리(Binary Search Tree)는 "자료구조"에요.

특정  key값에 대해서 삽입, 삭제, 탐색이 가능한 자료구조죠.

이진탐색트리(Binary Search Tree)는 특징이 하나가 있는데, 

자신의 왼쪽 서브트리에는 현재노드보다 Key값이 작은것. 오른쪽 서브트리에는 Key값이 큰 것들이 오게됩니다.

이때문에 이진탐색트리(Binary Search Tree)는 탐색이 간단하게되는데요.

이 이진탐색트리에서 중위순회(inorder traversal)를 하면, 오름차순으로 정렬된 순서로 Key값을 얻을 수 있게 됩니다. 

예를 하나 볼까요? 

(참고로 이진 탐색 트리는 이진트리이기 때문에, 자식이 없을 수도, 한개일수도, 두개일수도 있어요.)

자, 위 트리에서 대해서 중위순회를 해봅시다.

왼쪽자식->부모->오른쪽자식순으로 순회하는 방법이죠?

20 -> 30 -> 40 -> 50 -> 60 -> 80

쨘

오름차순으로 정렬이 되었죠? 

하지만 위에서 말했죠?

이진트리이기때문에,

이렇게 계속계속 큰것만 들어오면 위 그림처럼 트리가 생겼을 수도 있답니다. 

최악의 경우 O(트리의 높이=h)만큼의 탐색시간이 걸리게되죠.

아니 진짜 간단하게 설명할라했는데 이까지 와버렸군

암튼 레드블랙트리 설명하다말고 왜 이진탐색트리를 설명하냐 ㅡㅡ

그 이유는 레드블랙트리도 이진탐색트리이기때문이죠!!!!!!!!!!!!!!!!!!

아하 그럼 여기서 우리는 레드블랙트리의 특징을 하나 알 수 있게되죠.

왼쪽 서브트리에는 현재 노드의 Key값보다 작은값이. 오른쪽 서브트리에는 현재노드의 Key값보다 큰 값이 오겠네요. 

그럼 레드블랙트리에서도 search연산이 최악의 경우 O(트리의높이=h)가 걸리겠네요?

그럴 것 같지만!!!!

레드블랙트리는 balanced binary search tree랍니다.

balanced binary search tree는 뭔가 균형이 맞을 것 같죠? 네 맞습니다. 레드블랙트리에서는!

이러한 모양이 나올 수 없도록 "조건"을 걸어놨답니다.

이 조건이 레드블랙트리를 이진탐색트리이지만, 균형잡힌 트리로 만들어주는 역할을 하죠. 

이 말뜻은...

균형이 잡혀 위 그림 같은 경우가 안나온다 ==> 레드블랙트리의 높이는 logn에 바운드 된다 ==> 레드블랙트리에서 search연산은 O(logn)의 시간복잡도를 가지게 된다. 

라는 소리가 됩니다!!!!XD

자..그럼 이제 레드블랙트리의 "조건"을 알아볼까요?

중요하니까 잘 보세요!!!

1. Root Property : 루트노드의 색깔은 검정(Black)이다.

2. External Property : 모든 external node들은 검정(Black)이다.

3. Internal Property : 빨강(Red)노드의 자식은 검정(Black)이다. 

== No Double Red(빨간색 노드가 연속으로 나올 수 없다.) 

4. Depth Property : 모든 리프노드에서 Black Depth는 같다. 

== 리프노드에서 루트노드까지 가는 경로에서 만나는 블랙노드의 개수는 같다. 

(그냥 노드의 수는 다를 수 있음.)

자. 레드블랙트리는 이렇게 4개의 조건을 가지고있습니다. 

위 4개의 조건이 이진탐색트리인 레드블랙트리의 높이를 logn에 바운드되도록 해준답니다.

조건에 검정, 빨강등이 나오네요. 이래서 Red-Black Tree라 불린답니다. :)

자. 이걸 구구절절 설명하기보다는 예제를 통해 한번 볼까요?

이제 우리는 트리를 하나 만들거에요. 

레드블랙트리의 1번 조건(Root Property)에 의해 

루트노드의 색깔은 검정(Black)을 줬습니다.

이제 값들을 삽입해볼게요.

참고로, 삽입되는 노드의 색깔은 무조건 Red입니다. 

?

네. 삽입되는 노드의 색깔이 무조건 Red이게 되면

3번조건이 위배될 가능성이 있겠네요.

Double Red가 생길 수 있다는 거니까요.

일단 값을 넣어봅시다. 

2와 8을 넣어보았어요. 

2는 4보다 작으니까 왼쪽, 8은 4보다 크니까 오른쪽.

맞죠?

값을 하나 더 넣어볼까요?

네 3은 4보다는 작고 2보다는 크니 바로 "저 위치"에 가야겠죠? 

하지만, 이렇게 되는 순간

3번 조건(Internal Property)를 위반하게 됩니다.

Red의 자식은 Black이어야하는데 Red가 와버렸네요.

이런 상황을 위해서 언급했다시피 Double Red라고 합니다.

이 Double Red를 해결해줘야만 레드블랙트리라고 할 수 있겠죠?

이 Double Red를 해결하는 전략이 2가지 있습니다.

● Restructuring

● Recoloring

지금부터 헷갈릴 수 있어요. 

잘 보셔야합니다. 

언제 Restructuring, Recoloring이 일어나는지 어떻게 일어나는지를 설명할거에요.

자. 그림으로 정리해봤는데요. 

Double Red를 해결하는 방법은 현재 insert된 노드의 uncle node의 색깔에 따라 수행하는 프로시저가 다릅니다. 

네. 제 부모의 형제요!!

즉 위 그림으로 따지면, 현재 insert된 노드 z의 uncle node는 무엇이죠? 내 부모(v)의 형제(w)니 

w가 되겠네요. 

w가 검정(Black) 일 땐 Restructuring.

w가 빨강(Red)일 땐 Recoloring을 수행하게 됩니다.

Restructuring

---

Restructuring을 먼저 보도록 하죠.

Restructuring을 하는 과정을 말로 먼저 말씀드리면,

현재 insert된 노드(z)와 내 부모(v)와 내 부모의 부모(Grand Parent)를 가지고 Restructuring을 합니다.

Restructuring. 뭔가 재건축..?하는 것 같죠? 맞습니다.

Restructuring은 다음과 같이 이루어집니다. 

1. 나(z)와 내 부모(v), 내 부모의 부모(Grand Parent)를 오름차순으로 정렬

2. 무조건 가운데 있는 값을 부모로 만들고 나머지 둘을 자식으로 만든다.

3. 올라간 가운데 있는 값을 검정(Black)으로 만들고 그 두자식들을 빨강(Red)로 만든다. 

예제를 같이 볼까요?

현재 insert된 노드(z)와 그의 부모 v. 그리고 그 부모의 부모(Grand Parent)를 잡았아요.

그리고 이제 뭘 하면 된댔죠?

네! 정렬입니다. 

네 오름차순 정렬이니 이런 식으로 정렬되겠네요.

이제 가운데 있는 값을 부모로 만들고 나머지 둘을 자식으로 만들랬죠? 

6보다 작은 4를 왼쪽에 두고 6보다 큰 7을 오른쪽으로 두는건 이진탐색트리니까 당연하겠죠?

그리고 마지막단계. 부모로 올라간 6을 검정(Black)으로 만들고 그 자식들을 빨강(Red)로 만듭니다. 

짠!!그리고 이제 원래 4의 자식이었던 2를 추가해주면 됩니다. 

쩌~~기 위에 원래 Key가 2인 노드가 하나 있었답니다. z의 uncle이었던 노드죠.

휴 이제 진짜 Restructuring이 끝났습니다 ㅎㅎ

Double Red가 진짜 없어졌죠? 

시간복잡도에 관한건 맨 아래에서 말씀드릴려고 했는데, 이것 하나만 알아두세요!

Restructuring은 다른 서브트리에 영향을 끼치지 않기 때문에 한번의 Restructuring이면 끝납니다. 

여기서 말하는 영향이란 Black Depth에요. 조건 4번 기억나시나요?

Depth Property였죠. 모든 리프노드에서 Black Depth는 같다..였는데

Double Red를 해결하기 전과 해결 한 후의 Black 노드의 개수에 변화가 없기때문에 다른서브트리에 영향을 끼치지 않게 됩니다. 

또한, Restructuring자체의 시간복잡도는 O(1)에 끝나지만, (순서결정시간 - 상수시간, 트리로 만드는시간 - 상수시간, 원래있던 노드들의 구조들을 바꿔주는 시간 - 상수시간)

 Restructuring은 어떤 노드를 insertion한 뒤 일어나므로 총 수행시간은 O(logn)이에요. 지금 현재 노드가 들어갈 위치를 먼저 찾아야 하기 때문이죠.

위에서 "Restructuring은 다른 서브트리에 영향을 끼치지 않기 때문에 한번의 Restructuring이면 끝납니다." 라고 그랬는데,

아 그럼 Recoloring은 한번에 안끝나나? 

네..그렇습니다. 아 아니 "한번에 안끝날 가능성이 있습니다." 라고 말하는게 정확하겠네요.

한번 같이 볼까요?

Recoloring

---

Recoloring을 하는과정을 먼저 말로 말씀드릴게요.

1. 현재 inset된 노드(z)의 부모와 그 형제(w)를 검정(Black)으로 하고 Grand Parent(내 부모의 부모)를 빨강(Red)로 한다.

2. Grand Parent(내 부모의 부모)가 Root node가 아니었을 시 Double Red가 다시 발생 할 수 있다.

말로하니까 역시 모르겠네요.

예제를 같이 봅시다!!

현재 insert된 노드 z의 부모 (v) = 7과, 그 형제 (w) = 2의 색깔을 검정으로 만들어주라고 그랬죠?

그리고 z의 Grand Parent를 빨강(Red)로 만들어줍니다. 

하지만, 만약 Grand Parent(내 부모의 부모)가 Root Node였다면, 

레드블랙트리의 1번조건(Root Property)에 의해 검정(Black)이 되게 됩니다. 

이렇게요!

하지만...사실 알고보니까 지금 우리가 보는 트리가 어떤 큰 트리의 서브트리였다고 생각해볼게요.

즉, 4라는 Key를 가진노드가 Root가 아니었던거죠. 

그럼 이 상태로 둬야할텐데, 이 4위에 또!!!!!!!!!!!사실은 또!!!! 빨강(Red)노드가 있을 수 있습니다.

그럼 또 Double Red가 생겼죠? 

즉, Recoloring의 경우 Restructuring과 다르게 propagation될 수 있습니다. 

최악의경우 Root까지 갈 수 있게되죠.

그러니까, 위에서 말한 "한번에 안끝날 가능성이 있습니다." 라는 말이 무슨뜻인지 아시겠죠?

그럼 만약 4의 부모가 또 Red였다고 생각해봅시다. 

그럼 Double Red가 생긴거네요?

Double Red를 해결하는 방법 두가지가 뭐였죠?

● Restructuring

● Recoloring

이었습니다.

만약 4의 부모가 Red였다면!!!그냥 다시 4의 부모의 형제노드(uncle node)의 색깔을 보고!!!!!!

Restructuring할건지, Recoloring할건지 결정해주면 됩니다.

이 때 uncle node의 색깔이 검정(Black)이었다면 Restructuring을 하게되겠죠? 위에서 말했다시피, Restructuring은 다른서브트리에 영향을 끼치지 않습니다.

그러니 Double Red는 이제 발생하지 않게되고 여기서 fix가 종료되게 되죠.

하지만, uncle node의 색깔이 빨강(Red)였다면, Recoloring을 다시 하겠죠?

Recoloring을 다 하고 나서, 또!11!!! Double Red가 생길 가능성이 있는 것이죠.

Recoloring에 대해 의문이 들 수 있어요. 

Q : 저렇게 막 내 부모랑 uncle노드를 막 검정으로 바꿔도돼??!! 레드블랙트리의 4번조건. Depth Property만족해?

A : 네. 만족합니다. Black Depth는 일제히 1증가하기 때문에 문제가 없습니다 :)

자. 이제 Recoloring의 시간복잡도를 한번 볼까요?

역시 Recoloring은 언제일어나는거라구요? 네. 뭐가 insert된 상태에서 일어날 수 있는거겠죠?

내가 지금 현재 넣는 트리는 레드블랙트리라는게 자명합니다. 레드블랙트리가 아니라면, Restructuring이든, Recoloring이든 일어나서 레드블랙트리로 만들어줬을 거니까요. 

네. 아무튼 insert를 하는데 "내 위치"를 찾아야합니다. 이 때 O(logn)이라는 시간이 걸리게됩니다. 

Restructuring과 마찬가지로 Recoloring은 O(1)의 시간이 걸립니다.

하지만, Recoloring은 Root까지 propagation될 수 있으므로 최악의 경우 O(logn)이 걸리게 됩니다. 

총 O(logn)이 걸리게 되는것이죠. 

어 위에서 Restructuring도 O(logn)이었는데 말이죠.

따라서!!!!!!!!!!!!!!!!!!!

레드블랙트리에 삽입(insertion)하는경우, Restructuring을 하든, Recoloring을 하든 O(logn)이 걸리게됩니다. 

와 드디어 레드블랙트리 설명이 끝났네요. XD..

가장 중요한 설명 하나가 남았습니다. 

저렇게 해주면 진짜 Balanced가 되냐?!?!?! 인거죠.

진짜 저 4가지 조건만 만족시켜주면, 진짜 레드블랙트리가 이진탐색트리임에도 불구하고 높이가 logn에 바운드 되냐 이거죠.

네. 됩니다.

자. 여기서 레드블랙트리 4번조건이 다시 봐야하는데요.  Depth Property였죠. 

어느 리프노드에서 루트노드까지 가더라도 Black Depth는 항상 같아야합니다. 

그럼 가장 "짧은" Black Depth를 가지는 external node가 있고,

가장 "긴" Black Depth를 가지는 external node가 있습니다. 

여기서 짧고 길다는 것은 정말 물리적으로 짧고 긴 것을 말해요.

하지만 이 둘의 Black Depth는 반드시 같아야하죠.

그럼 Black Depth는 같으면서 가장 짧으려면 어떻게하면되죠?

네!!! 검정(Black)노드만 있는거죠. 그러면 가장 짧아지겠죠?

그럼, Black Depth는 같으면서 가장 길려면 어떻게 해야할까요?

Double Red는 안되니까,

검정-빨강-검정-빨강-검정-빨강 ........-검정

이런식으로 이루어져있으면 가장 길겠죠? 

이 둘의 Black Depth. 즉 Root노드까지 가면서 만나는 Black node의 개수는 같아요.

이 둘의 높이차는 최대로 얼마나 차이날 것 같으세요?

네. 기껏해야 정말 기껏해야 2배차이납니다. 

상당히 Balance하죠. 

4번 조건인 Depth Property덕분에 레드블랙트리의 높이가 logn에 바운드 될 수 있는 것이죠. 

레드블랙트리는 현재 고안된 이진탐색 트리중 가장 성능이 좋다고 해요.

STL의 Map도 레드블랙트리로 구현되어 있다고 합니다 :)

흐아으ㅏㅏ레드블랙트리에 대해서 조금 이해가 가시나요?

왜 지우개가 많이 필요한지 아시겠나요!?!?!?!

Recoloring이면 다행이고,..Restructuring한번 일어나면....후..

그래서 레드블랙트리는 많이 해보시는게 좋아요 :)

레드블랙트리에 대한 궁금증이나 지적할 점이 있으시다면 댓글이나, PC화면 오른쪽하단에서 볼 수 있는 채널서비스를 이용해주세요 :)

레드블랙트리 이해에 도움이 되시면 좋겠어요🌲