[SW 정글 36일차] 레드블랙트리 개념 익히기

오늘은 이번 주차 본 과제인 레드블랙트리에 대해 공부를 시작했다.

이진탐색트리의 단점은 보완하는 정말 신기한 자료구조이다.

Introduction to Algorithms를 2~3번 읽고나니 이해가 됐고 새로운 것을 배워서 뿌듯했다.

 

 

 

1. 균형 이진 탐색 트리란?

균형 이진 탐색 트리란 노드의 삽입과 삭제가 일어나는 경우에 자동으로 각 노드에서의 높이를 균형있게 유지지키는 것이다.

아래의 그림은 기존의 이진 탐색 트리의 문제가 발생하는 경우이다.

단순히 이진 탐색 트리에 값이 오름차순 혹은 내림차순으로 삽입되는 경우에 한쪽으로 치우치는 트리가 나올 수 있다.

이렇게 되면 이진 탐색 트리의 강점 중 하나인 탐색 시 시간복잡도가 O(logn)이라는 것이 O(n)이 되고 선형리스트와 다를 바가 없어진다.

그래서 이진 탐색 트리에 삽입이나 삭제 시에 트리의 균형을 맞추어 트리의 기본 동적 집합 연산들(삽입, 삭제, 탐색 등)이 최악의 경우에도 O(logn) 시간복잡도가 유지 되도록 해주는 것이다.

균형 이진 탐색 트리의 종류로는 2-3Tree, AA Tree, AVL Tree, B-Tree, Red-Black Tree, Scapegoat Tree 등이 있다.

이번에는 Red-Black 트리에 대해 집중적으로 알아보고 구현해보려고 한다.

 

 

 

2. Red-Black Tree란?

레드블랙 트리는 균형 이진 탐색 트리의 하나로써 각 노드를 RED, BLACK 2가지 색깔로 구분지어 트리의 균형을 맞춘다.

루트에서 리프노드까지의 경로 내에 나타나는 노드들의 색깔을 2가지로 제한하여 가장 긴 경로의 길이와 가장 짧은 경로의 길이가 2배이상 차이가 나지 않도록 해준다.

 

각 노드는 color, key, leftChild, rightChild, ParentNode 정보를 가진다.

자식 또는 부모노드를 가지고 있지 않는 노드들은 NIL노드를 참조하게 만들어주고 NIL노드는 말그대로 아무 값도 없는 노드를 말한다.

그렇게 되면 NIL 노드는 Red-Black Tree의 리프노드에 대한 포인터가 되고 NIL노드를 제외한 모든 노드가 레드블랙트리의 내부노드가 된다.

 

그러면 레드블랙트리가 되려면 어떠한 특성을 유지해야할까?

애래와 같은 5가지의 특성을 만족해야 레드블랙트리가 된다.

1. 모든 노드는 적색이거나 흑색이여야한다.

2. 루트는 흑색이다.

3. 모든 리프노드는 흑색이다.

4. 노드가 적색이면 그 노드의 자식은 모두 흑색이다.

5. 각각의 노드로부터 그 노드의 자손인 리프들로 가는 경로들은 모두 같은 수의 흑색 노드를 포함한다.

 

레드블랙트리에 삽입과 삭제를 할 때에 기존의 이진 탐색 트리와 처음에는 같은 동작으로 구현이 되지만 삽입, 삭제를 한 후에 위 5가지 특성을 만족하도록 추가적인 조작을 해야한다.

내일은 삽입, 모레는 삭제를 구현하면서 삽입과, 삭제 원리와 코드에 대한 설명을 해보려고 한다.

 

---

[오늘의 나는 어땠을까?]

어제까지 Red-Black Tree 구현을 위한 C언어 공부와 C언어를 이용하여 링크드리스트, 이진탐색트리 구현을 마치고 오늘부터 본격적으로 RB Tree 공부를 시작했다.

일단은 삽입과 삭제가 가장 어려운 기능이고 다른 것은 이진탐색트리와 같기 때문에 삽입에 대해 공부했다.

공부해보니 너무 신기했다.

기존에 있던 것의 단점을 보완하기 위한 무언가를 새로 만들었다는 것도 신기했고 그것을 컴퓨터에게 전달하여 컴퓨터가 만들 수 있도록 코드를 구현한 것도 신기했다.

지금은 누군가의 이론을 보고 내가 코드를 짜고 있지만 나도 언젠가는 새로운 것을 만들 날이 왔으면 좋겠다.

 

정글에 들어와서 항상 느낀 것이지만 정말 이해력이 빠르고 습득력이 빠른 사람들이 많다.

내 생각으로는 내가 가장 시간투자를 많이 하지만 효율성은 좋지 않은 것같아 '내가 앞으로 시간을 배로 투자해도 좋은 개발자가 될 수 있을지 의문도 들었고 내가 정말 개발자의 적성에 맞는지 의문도 들었다.

하지만, C언어라는 새로운 언어를 접하면서 파이썬에서 느낄 수 없었던 재미도 느꼈고 무언가를 새롭게 배우는 것이 즐거워서 지금은 적성에 맞는다고 생각하면서 끝까지 해보려고 한다.

 

끝까지.. 후회가 남지 않도록

 

---

<참고 자료>

https://www.codesdope.com/course/data-structures-red-black-trees-insertion/

https://www.youtube.com/watch?v=P4Xc7iojyXg 

https://ko.wikipedia.org/wiki/%EB%A0%88%EB%93%9C-%EB%B8%94%EB%9E%99_%ED%8A%B8%EB%A6%AC