[SW 정글] 5/1 ~ 5/4 TIL RB Tree (feat, C)

이번주차는 RED - BLACK TREE를 직접 구현해보는 것이 과제이다.

 

rb tree의 조건은 다음과 같다

 

1. 모든 노드는 색을 가진다. Red or Black

2. root 노드는 black

3. leaf node는 black

4. red node의 child node는 black(black node의 child node는 상관없다.)

5. 각 노드에서 leaf node로 가는 경로 중 black node의 수는 항상 같아야 한다. (-> 이 조건 때문에 균형이 유지된다.)

 

fact 1, v의 서브트리의 내부노드 개수 >= 2^(bh(v)-1)

 

fact 2, black의 노드 개수 >= h/2 

      =>    black(root) >= h/2

 

fact 3, h = O(log2N)

 

h(v) : v의 높이

bh(v) : v에서 leaf node까지 존재하는 black node의 개수(v는 제외한다.)

 

 

먼저, rb tree는 균형 이진 트리의 한 종류로 삭제시 회전수가 낮기 때문에 많이 쓰인다고 한다.

 

삽입, 삭제 이론은 매우 어려웠지만(특히 삭제), Introduction to Algorithms 책에 있는  pseudo code를 보고 짜서 그런가 큰 어려움은 없었다. (오타 때문에 디버그만 오래걸리는 거 빼고 !)

 

이론 설명은 권오흠님께서 정말 잘 가르쳐주셨다 !

 

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

강의도 30분이 넘어가기 때문에 따로 블로그에 정리하지는 않겠다!

 

궁금하면 권오흠 님의 레드블랙트리 1,2,3를 들어보는 것을 추천한다!

 

그러나, 주의할 점은 레드블랙 트리 삭제 부분에서 Introduction to Algorithms책과 강의가 조금 다르다는 것이다.

 

삭제하고 바꾸는 노드가 다르다. 책은 오른쪽에서 제일 작은애를 찾지만 위 강의는 다르다.

 

강의를 듣고 수도코드를 보면 조금 의아함이 들것이다! 삭제부분은 유의해서 듣도록 하쟈

 

 

 

 

 

그럼 다음 주차도 열🔥코🔥해보도록 하자 !