저녁 먹으러 갈때 하늘이 너무 이뻐서 찍었다.
아쉽게도 저녁 먹고 나오니까 다시 저 광경을 보지 못했다.
평소에 사진을 많이 찍는 편인데 더(?) 많이 찍어야겠다는 생각이 들었다.
Red-black Tree
드디어 소문으로만 듣던 레드블랙트리를 마주했다.
우리 조는 Rb-tree 이전까지 파죽지세로 자신감이 뿜뿜이였는데 직접 경험하고,
시묵하고 모두가 퇴근했다..
이번 TIL에서는 레드 블랙트리가 무엇인지만 정리 해보려 한다.
정리에 앞서 쉬운코드님의 유튜브강의가 없었다면 정말 힘들었을 것 같아서 너무 감사하다.
내가 정리한 내용도 쉬운코드님의 영상의 내용이다.
영상은 쉬운코드님 - Rb-tree 강의를 참고하자.
Rb-tree?
출처 : stackoverflow
Rb-tree는 이진 탐색 트리(BST)의 한 종류이고, 스스로 균형을 잡는 트리이다.
BST에서 Worst Case일 경우 O(n)의 time-complexity가 발생하는데
Rb-tree는 스스로 좌우의 균형 맞추면서 O(logn)을 가능하게 해준다.
Rb-tree의 속성
본격적으로 Rb-tree의 속성을 알아보기 전에 Nil 노드에 대해서 알아보자.
Nil Node?
Nil 노드는 존재하지 않는 노드이고, 노드에 자녀가 없을 때 자녀를 Nil로 표기한다.
신기하게 Nil 노드는 Rb-tree에서 값이 있는 노드와 동등하게 취급한다.
다른 트리 구조의 leaf가 rb-tree에서는 Nil 노드라고 생각하면 이해하기 쉬울 수 있다.
5가지 속성
- 모든 노드는 red or black
- 루트 노드는 black
- 모든 Nil 노드는 black
- red의 자녀들은 black or red가 연속적으로 존재X
- 임의의 노드에서 자손 Nil 노드들까지 가는 경로들의 black수는 같다.
(자기자신은 카운트 X)
이 5가지의 속성이 rb-tree가 이렇게 구성되어 있구나 이해 할 수 있겠고,
5번 속성을 만족했을때의 경우 파생되는 중요한 조건이 있는데
첫번째 조건으로는,
1. 5번이 충족할 경우 노드 x의 black height가 존재한다.
black height는 노드 x에서 임의의 자손 Nil 노드까지 내려가는 경로에서의 black 수이고, 마찬가지로 자기 자신은 카운트 하지 않는다.
이어서 두번째 조건으로,
2. 두 자녀가 같은 색을 가질때 부모와 두 자녀의 색을 바꿔도 5번 속성은 여전히 만족한다.
이건 거꾸로 직접 변경해보거나 대충 생각해도 이해하기 쉽지만 이후 삽입이나 삭제에 있어서 크게 중요한 과정이다.
다음에는 삽입과 삭제에 대해서 정리할 것 같은데 정말 쉽지 않다.
그래도 아직까지는 재밌다는 생각이 들어서 빨리 마무리하고 주변 친구들을 도와주고 싶다.
오늘의 추천곡 🎶
10CM - '그라데이션'🎵
청춘 드라마가 떠오르는 노래! 어릴때 10cm의 '너에게 닿기를'을 정말 많이 들었었는데 후속곡같은 노래라서 반복해서 들었다. 이 노래를 듣고 청춘 드라마의 주인공이 되어보자..!
내일의 나에게 👍
- Rb-tree 부수기..
- CSAPP 7장
