Red-Black Tree (basic + insert)

안녕하세요 대학생개발자입니다.

 

휴... 요새 한창 매우 바쁘다가 한꺼번에 과제가 해결되버렸습니다...

 

예전에 제가 안된다고 했던 과제있죠?? 그게 레드블랙 트린데 말입니다...

사실 레드블랙트리를 아직도 100%이해했다고 자신하지 못하겠습니다ㅠㅠ...

물론 하나하나의 케이스를 놓고보면 어떻게 노드가 움직여야 되는지 어떤색으로 칠해져야되는지 알겠지만

그게 코드로 나오는데까지 시간이 상당히 오래 걸리더라구요...

 

아마... 이번 레드블랙 트리는 2번에 걸쳐서 나눠서 하게될 것 같습니다.

당연하게도 삽입과 삭제의 과정이 너무 케이스가 많기때문에 긴 글이 될 것같습니다.

실제로 다른글들도 읽어봤지만 한큐에 다 정리하기에는 양이 너무 많아보였고... 제가 실제로 메모장에 정리하면서 봤을때도 상당한 양이였기 때문에 두번에 나눠서 한다는점 양해 부탁드립니다.

 

일단 이런 내용은 잠시 접어두도록 하고 오늘의 내용에 대해서 얘기를 해보겠습니다.

오늘은 RedBlackTree에 대해서 얘기를 해보려고합니다.

 

아마 많은분들이 자료구조를 하시면서 트리, 이진트리등을 보셨을겁니다.

음... 제가 처음 자료구조를 할때는 그래프 알고리즘들에게 패배를 했었었는데요...

많은분들이 트리, 그래프 같은곳에서 힘들어 하시더라구요 확실히 선형과 비선형은 느낌이 좀 다르긴하죠.

 

아마 대부분 사람들이 책에서 트리라는 자료구조를 접하기 전까지는 자식 노드가 2개인 트리만을 봐왔을겁니다...

저도 그랬었구요 사실 트리의 노드가 3개이상이라고 하면 저는 그래프라고 불렀기때문에... 노드가 3개이상인 트리를 잘 사용하지 않았을 뿐더러 잘 접해보지도 않았었습니다.

아마 이런 트리 구조는 자료구조를 공부하지 않으신 분이라면 들어보지 못했을겁니다.

사실 트리라기 보다는 2차원 리스트 같은 느낌으로 되어있습니다.

이런 트리라면 최악의 경우 n까지 가야되겠군요

 

이런식으로 나뭇가지가 아래로 내려갈수록 뻗어나가는 것을 보고 우리는 트리라고 부르고있죠.

물론 그 나무가 뒤집어져 있긴합니다만 뻗어나가는 모습만 생각하자구요

 

거기서 하나의 노드에서 나뭇가지가 2가닥으로만 나가는것을보고 이진트리라고 부릅니다.

이진트리의 장점은 정렬을 하면서 들어가기때문에(inorder기준) 모든 노드의 좌우가 있는 케이스의 경우(완전이진트리) 검색과 삭제에 있어서 리스트에 비해 어마어마한 성능을 자랑합니다.

 

아마 대부분 업다운 게임을 해보셨을거에요

마음속으로 어떤 숫자를 생각하고있을 때 그 숫자를 불러 업 다운과 같이 높은지 낮은지를 보고 다음숫자를 추론해 맞추는거죠...

 

이걸 리스트와 이진트리로 본다면

리스트는 그냥 0부터 100까지 차례대로 불러보고 중간에 걸리면 맞는케이스가 되는겁니다.

즉 가장 느린케이스는 100번째에 정답이 되는 케이스가 되겠죠.

시간 복잡도 O(n)입니다. 최악의 경우 n번간다는 의미죠.

 

반대로 이진트리는 똑똑한 녀석입니다. 심리학이나 마술을 쓰지 않는 선에서 가장빨리 찾을수있는 방법을 알고있어요...

중간 값을 부르고 그보다 작으면 위의 절반은 버립니다. 필요가 없으니까요. 정답이 그보다 작은값인데 큰곳을 뒤지고 있는 행동은 멍청한 행동이니까 그게 맞는거죠..

시간 복잡도는 O(log n)입니다. 최악의 경우에가 되서야 log n번 한다는거에요... 어마어마하게 효율적이게 바뀌는 것이죠...

 

하지만 일반적인 이진트리의 경우

정렬되어있는 데이터를 차례대로 넣다보면 리스트와 다를바가 없어져 버립니다.

한쪽으로 편향되어있기때문에  

이런형태가 되어버릴테니까요 사실상 선형 구조와 동일해지는 겁니다.

이런경우에는 최악의경우 n번 반복해야되고 이진트리를 쓰는 이유가 사라지는 겁니다.

 

이런 이유때문에 트리의 균형을 잘 지켜줄 수 있는 방법으로 insert, remove 연산을 할 때 만약 밸런스가 무너져있다면 그 밸런스를 잡아주는게 어떻겠냐는 그런 아이디어에서 나온게 balanced tree입니다. 그리고 그 밸런스 트리에서 가장 유명한게 Red-Black tree와 AVL-tree 입니다.

그리고 오늘 다뤄보려고 하는건 Red-Black tree(이하RBT)입니다.

 

좋습니다. 그러면 우리가 리스트에 비해 레드블랙트리를 쓰는게 그저 검색이 빠르다는점 때문일까요?

그건또 아닙니다... 사실 검색이라고하면 가장 빠른건 O(1)이 나오는 녀석도 있으니까요... 해쉬죠

해쉬의 경우에는 hash function만 돌리면 바로 인덱스가 떨어지기때문에 어떤경우에든 1번입니다. 그이상이없죠.

그런데 왜 레드블랙트리냐구요?

 

해쉬의 경우에는 순회의 기능이 없습니다.(물론 만들려고하면 만들수있습니다만 원래 해쉬는 빠른 검색을 위한 자료구조이지 순회를 위한 자료구조는 아닙니다.)

 

그렇다보니 순회가 가능한 연결성 구조여야되겠구요... 그 와중에 검색이 빠른 레드블랙트리를 생각하게 된겁니다.

간단히 생각하시면 리스트는 느리고 해쉬는 순회가 안되니 중간을 찾았다 정도로 보시면 될 것 같습니다.

 

아... 그리고 AVL트리와 비교를 해보면 AVL트리가 더 검색효율은 좋습니다. 왜냐면 AVL트리는 더 깐깐하거든요.

-2 ~ +2 라는 balance factor라는 값을 두고 그 이상 높이가 차이나면 무조건 뒤집어 엎어버리는녀석이 AVL트리기 때문에 레드블랙트리의 경우에는 최대 높이 차이는 가장 낮은곳 * 2 인것이 비하면... 좀 많이 깐깐하죠??

 

이건 상황 봐가면서 쓰시면 될 것같습니다. 내가 필요한게 지금 검색성능이냐 혹은 빈번한 삽입정렬 및 검색이냐에 포커싱을 두고 어떤자료구조가 더 효율적인지 쓰면 좋을 것 같습니다.

저같은 경우에는 검색도 적당히 빠르면서 삽입과 삭제도 적당히 느린 자료구조를 찾다보니 AVL보다는 레드블랙트리가 더 좋다고 판단했습니다.

 

 

네 여기까지 왔다면 레드블랙 트리가 필요한 이유까지는 끝난겁니다...

 

자 그럼 여기서부터는 많은사람들이 구글에 설명하고 있는 레드블랙트리의 이론이니까... 저보다 더 잘 이해할수있게 설명하신분이 있다면 거기서 공부하시면 되겠습니다.

 

레드블랙트리의 규칙에 대해서 얘기해볼겁니다.

레드블랙트리라고 하면 무조건 이 룰을 따라야 하기 때문입니다.

 

1. 모든 노드는 레드, 블랙중 하나의 색을 가져야한다.

2. 루트는 블랙이어야된다.

3. 리프노드도 블랙이어야된다.

4. 레드노드의 자식은 블랙이어야된다.

5. 루트노드부터 모든 리프노드까지 경로의 블랙 노드 갯수는 동일하다.

 

레드블랙 트리는 이 조건들을 만족하는 이진탐색트리입니다.

 

그리고 일반적인 이진트리와 다르게 각 노드는 부모의 포인터를 가지고있습니다. 이것은 없어도 구현은 가능은하지만.. 편의상 일반적으로 가지고있습니다.

 

금방 추론하실수 있겠지만 레드노드의 자식은 블랙이어야된다 라는 규칙이 존재하기 때문에 최대 깊이차이가 2배이상 날 수 없는겁니다. 그리고 그걸 통해서 밸런스를 맞출거구요.

 

모든 마지막 노드들은 nil이라는 더미노드를 자식노드로 가지고있습니다.

닐노드는 무조건 블랙이고 모든 리프노드에 nil노드를 연결해야됩니다.

3번조건 모든 리프노드는 블랙이다의 조건을 만족하기 위한 더미노드입니다.

 

그럼 밸런싱 작업을 하기전에 꼭 필요한 노드 위치를 재정렬해주는 함수인데요...

뭐 이름은 아무래도 좋습니다. 하지만 그 노드를 기준으로 왼쪽으로 혹은 오른쪽으로 회전하는 기능을 하기때문에

저는 RotateLeft, RotateRight라는 이름을 붙여서 사용했습니다.

이 함수들이 해주는 기능은 이름과 같은데요

RotateRight의 경우에는 N을 기준으로 저런식으로 회전시켜버립니다.

RotateLeft는 저것과 정확히 반대입니다.

이렇게 작동합니다.

자아... 그러면 Insert를 살펴볼건데요

 

일단 새로 삽입되는 노드는 무조건 끝단에 들어가게될겁니다.

이건 BST도 동일한건이니까 이유는 생략하겠습니다.

추가로 새로 삽입되는 노드는 무조건 RED로 들어가게됩니다.

왜냐하면 모든 경로상의 블랙의 갯수가 동일해야되는 조건이 있기때문에 블랙이 만약 들어간다면 모든 노드를 다 뒤집어 엎어야 되기 때문입니다.

그래서 삽입되었을때 문제가 되지 않는 레드로 들어가게됩니다.

 

그렇다면 밸런스를 잡아주는 경우는 언제인가 하면 새로 삽입된 노드의 부모의 컬러가 RED일때만 해당됩니다.

4번 규칙에 의해 레드의 자식은 무조건 블랙이어야 되기 때문입니다.

 

그럼 이 경우를 해결하기 위해서는 우선 부모의 색깔을 알아야될겁니다.

그리고 부모와 같이 부모의 형제노드까지 알아야됩니다.

5번 규칙 "루트노드부터 모든 리프노드까지 경로의 블랙 노드 갯수는 동일하다." 를 맞춰주기 위해서인데요.

우리 노드에서 블랙이 1개가 추가가 된다면 부모 기준 우리쪽이 1이 늘어나게되고 반대쪽 노드는 블랙의 갯수가 1개 적습니다. 그러면 부모선에서 양쪽 노드에 1개씩 추가하면 가능하지만... 그렇게되면 할아버지 노드를 기준으로 부모와 삼촌노드의 블랙갯수가 틀어지게 됩니다. 그렇기 때문에 삼촌노드의 색깔도 알아야 됩니다.

즉 할아버지를 기준으로 좌 우 밸런스가 맞아야 된다는 겁니다.

 

그럼 하나씩 해결 방법을 적어보겠습니다.

지금 케이스는 P노드가 G노드의 왼쪽에 있을 경우를 기반으로 하니까 반대의 경우는 지금 적혀있는 설명과 정확히 반대로 하시면 됩니다.

 

 

1. 부모 레드, 삼촌도 레드.

부모가 레드고 삼촌이 레드고 나도 레드인 상태입니다.

부모가 레드고 삼촌이 레드라면 당연히 할아버지는 블랙일것입니다.

그럼 이 블랙을 부모와 삼촌에게 내려주고 할아버지를 레드로 바꿔버립니다.

이렇게되면 할아버지를 기준으로한 블랙갯수는 같아집니다.

하지만 할아버지 위가 레드일 수 있으니 할아버지를 새 노드로 잡고 루프를 돌 필요가 있습니다.

만약 계속 반복이라면 루트까지 올라가면서 확인해야되겠죠...

이렇게 하면서 G가 루트가 될때까지 계속 가야될것입니다...

 

2.  내가 오른쪽 레드면서, 부모가 레드, 삼촌은 블랙.

이 경우에는 색깔을 내린다는게 불가능합니다. 왜냐면 이미 삼촌이 블랙이기때문에 내리게되면 삼촌의 경우에는 블랙이 1개가 사라지는 케이스가되게 되므로 그 경로에서는 내 노드까지 오는 경로수의 블랙 갯수 -2가 되는것입니다.

 

여기서부터는 아까 만들었던 Rotate함수를 사용해서 밸런스를 맞춰줘야 할 때입니다.

우선 2단계의 경우에는 다음에 있을 3단계를 위한 준비 과정에서의 밸런싱작업입니다.

왜냐면 노드가 한쪽으로 치우쳐져 있어야 회전이 가능하기때문입니다.

아마 AVL트리를 해보신분들은 함수를 RotateLL RotateLR 등으로 나눠서 쓰시는데... 그걸 하나로 묶은 케이스라고 생각하셔도 될 것 같습니다. 

LR의 경우에는 먼저 P노드를 기준으로 RR호출해서 LL상태로 만드는데 지금 RotateLeft한 상황과 동일한 경우입니다.

 

그리고 부모와 나의 포인터를 바꿔줍니다.

물론... 실제 U가 블랙노드라면 이미 P에서부터 밸런스가 맞지 않으니  P가 레드일수가 없는것 아니냐 라고 하실수 있습니다.

U는 블랙이니까 사실상 닐노드여도 무관합니다. 그런 케이스로 혹시 틀렸다고 엥? 하시는 분이 계실까봐 싶어서 말씀드립니다.

 

 

3. 나는 왼쪽레드, 부모도 레드, 삼촌은 블랙

위의 상황으로 이제 나는 왼쪽레드 부모는 레드 삼촌은 블랙 상황이 만들어졌습니다.

그럼 여기서 문제되는 상황은 레드의 자식이 레드인 경우입니다. 그렇다면 반대쪽으로 레드를 하나 넘겨주면 해결이 되겠죠.

부모를 블랙으로 바꾸고 할아버지를 레드로 바꾼다음 할아버지를 기준으로 RotateRight를 하면 

다음과 같이 변하게 되겠습니다.

어... 근데 보니까 U가 밑에 달려서 블랙노드의 갯수가 안맞는 것 같다구요?

아까 말씀드렸듯이 저 케이스가 나오려면 U는 닐노드여야 가능합니다. 물론 저경우에서 닐노드또한 블랙이기 때문에 전혀 문제될 상황이없고 이렇게 본다면 조금 이해가 편하실수도 있겠습니다.

아까보다 이해가 잘 되시죠? 이렇게 본다면 밸런스가 맞는다는 의미입니다.

그러면 여기까지 해서 레드블랙트리의 삽입과정을 마치도록 하겠습니다.

 

 

RedBlackTree Insert

 

 

음... 엄청 글이 길어진 것 같습니다.

다음번 글에서는 삭제과정에 대한 내용을 다룰 예정입니다.

아마 삭제과정을 다 다루고 난 뒤에 깃허브에 소스코드가 올라갈 것 같습니다.

오늘 구현이 다되어서 검증이 아직 덜 되었습니다... 검증을 거친 이후에 확실해졌을때 올리도록 하겠습니다.

 

그럼 오늘도 긴글 읽어주신 여러분들께 감사드립니다.

그럼 다음에 뵙겠습니다 안녕히계세요