[SW 정글 37일차] 레드블랙트리 삽입, 삭제

오늘은 이틀동안 공부하고 직접 구현한 레드블랙트리의 삽입과 삭제 기능에 대해 정리해보려고 한다.

삽입과 삭제.... 처음 봤을 때에는 '내가 이걸 어떻게 코드를 짜?'였지만 계속 반복해서 보다보니 이해가 되면서 다른 사람들의 코드를 참고하여 직접 구현한 코드를 보게 되었다.

 

 

 

1. 레드블랙트리의 삽입원리

레드블랙트리에서 삽입은 일단은 이진탐색트리와 똑같이 새로운 노드의 키값에 따라 자신의 위치를 찾아가는 것을 동일하다.

이진탐색트리와 같은 원리로 일단은 노드를 삽입한 후에 레드블랙트리의 특성을 위반하지 않도록 fixed-up하는 방식이 있고 다른 방법은 삽입을 하는 과정에서 계속해서 자신을 위치를 찾으면서 내려갈 때마다 특정 조건 상황에 맞딱뜨렸을 때 fixe-up하는 방식이 있다.

나는 첫번째 방식을 택했고 두번째 방식은 jake lee라는 분이 유튜브에 설명 영상을 올렸다.

 

내가 공부하고 정리한 레드블랙트리의 삽입원리는 다음과 같다.

 

 

2. 레드블랙트리의 삭제원리

레드블랙트리에서 삭제의 원리는 삽입보다 훨씬 복잡하다.

복잡하다는 것은 삽입보다 생각해야할 case가 많고 case가 분류되도 '정말 이것만 해결하면 될까?'라는 생각을 품게 된다.

일단은 삭제하고하는 노드의 자식의 상태(0개인지, 1개인지, 2개인지)에 따라 정말 가능한 경우를 생각해서 그 이후에 어떻게 해결해야할지는 생각했다.

색깔이 2개이고 큰 케이스로는 3개여서 경우의 수가 많다고 생각할 수 있지만 실제로 생각해야할 경우의 수는 어짜피 자식이 없는 경우와 자식이 1개인 경우에서 색깔에 따라 다르게 되고 발생할 수 있는 색깔의 경우의 수도 한정적이다.

또한, 삭제 후 fixed-up하는 과정을 들어가기 전에 단순히 색깔만 바꾸거나 위치만 바꾸면 해결되는 경우도 있다.

 

내가 공부하고 정리한 레드블랙트리의 삭제원리는 다음과 같다.

여기서 쓰여진 fixed_up과정은 아래의 사이트에서 case6까지 확인할 수 있다.

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

레드-블랙 트리 - 위키백과, 우리 모두의 백과사전

핵심은 삭제하고자하는 노드가 Black이고 그 자식노드도 Black일 때, 삭제하고자하는 노드(Black)을 삭제한다면 레드블랙트리의 특성 5 (각각의 노드로부터 그 노드의 자손인 노드들로 가는 경로들은 모두 같은 수의 흑색노드를 가진다)를 만족하지 못하기 때문에 fixed_up을 진행하는 것이다.

 

 

 

구현한 코드는 내 깃헙 repository에서 확인할 수 있다.

https://github.com/JJong-Min/rbtree-lab

GitHub - JJong-Min/rbtree-lab: Red-Black Tree 구현코드입니다.

 

아래 사이트는 레드블랙트리에 값을 삽입하거나 삭제할 때, 레드블랙트리가 어떻게 형성되는지를 시각적으로 볼 수 있는 사이트이다.

알아야할 점은 자식노드가 2개일 경우에 노드를 삭제 시에 대체 값으로 successor가 아닌 preceder를 쓰기 때문에 successor로 대체하는 코드를 구현한다면 트리의 색이 다를 수 있다.

https://www.cs.usfca.edu/~galles/visualization/RedBlack.html

Red/Black Tree Visualization

 

---

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

오늘로써 레드블랙트리의 중요 연산 구현을 완료했다.

정글에 들어오고나서 가장 뿌듯하고 내가 성장하고 있구나라고 느낀 날이다.

삽입은 삭제에 비해 개념을 이해하기 쉬웠고 case를 보면서 내가 코드를 짜고 좋은 오픈소스가 있어 비교를 하며 수정을 해나갈 수 있었다.

하지만, 삭제는 오픈소스마다 처음 접근하는 방법이 조금씩 다르고 일단 접근하는 원리는 이해는 하겠는데 '정말 이 경우만 fixed, rotation, color change를 하면 되는가'를 계속해서 생각하고 그럴수록 더욱 복잡해졌다.

그래서 팀원 각자 구현하는 것보다 팀원들에게 페어프로그래밍을 하면 어떨지 의사를 물어보고 2명 모두 흔쾌히 수락을 해줬다.

정글에 들어오기 전에 페어프로그래밍으로 꼭 경험해보고 싶었는데 이번이 가장 적절한 시기라고 생각했고 정말 좋은 결과를 이뤄냈다.

단순히 삭제 구현을 성공한 것이 좋은 결과라고 하는 것이 아니라 페어프로그래밍을 한 후, 팀원들의 만족도와 성취감이 매우 높았음을 느꼈기 때문이다.

 

내가 느끼는 정글의 장점을 앞선 글들에 많이 썼지만 오늘도 느낀 장점은 매 주 팀별활동으로 이루어진다는 것도 큰 장점 중 하나라고 생각한다.

각자의 생각을 공유하며 부족한 점을 채울 수 있고 페어프로그래밍을 하며 혼자 하면 많은 시간이 걸릴 것을 세명이서 같이 바로바로 피드백을 하며 코드를 구현하면서 좋은 결과를 만들 수 있기 때문이다.

 

오늘의 느낀 뿌듯함, 성장성을 매일 느끼며 목표를 이루고 수료날을 맞이하고 싶다.

---

<참고 자료>

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

https://www.geeksforgeeks.org/red-black-tree-set-1-introduction-2/

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