Red-Black Tree – 삽입 글에서 설명한 것 처럼, RB tree에서 사용하는 구조체의 그림과 코드는 다음과 같다. 위 그림에서 rb_color는 단순하게 color값을 나타내는 값인데, 4 bytes를 가지는 int 타입이다. 따라서 parent의 주소값을 가지는 rb_parent의…

만약 아래 그림과 같은 RB tree 구조가 존재했을 때, node 1을 삭제하면 다음과 같을 것이다. 위 그림과 같이 됐을 때, tree의 균형은 맞는 것 처럼 보일 수 있지만 실제 균형이 맞지 않는 것이다.…

일명 RB tree라고 부르는 Red Black Tree는 binary search tree의 종류로 모태가 되는 구조는 B tree다. RB tree는 kernel의 메모리를 찾을 때도 사용되고 scheduling 할 때도 많이 사용된다. 큰 장점은 매 새로운 노드를…