코드 9-7에서 print_node 메서드는 의미 없이 단순히 노드의 컬러와 자식 노드, 그리고 부모 노드를 알아보기 쉬운 형태로 출력하는 편의 함수일 뿐입니다. 코드 9-7의 테스트 코드를 보면 레드 블랙 트리에 0부터 9까지 삽입하고 있습니다. 그리고 전위 순회로 모든 노드를 방문합니다. 실행하면 다음 결과가 출력됩니다.
****************************************************************************************************
node : 3, color : BLACK, left : 1, right : 5,
node : 1, color : BLACK, left : 0, right : 2, parent : 3
node : 0, color : BLACK, left : None, right : None, parent : 1
node : 2, color : BLACK, left : None, right : None, parent : 1
node : 5, color : BLACK, left : 4, right : 7, parent : 3
node : 4, color : BLACK, left : None, right : None, parent : 5
node : 7, color : RED, left : 6, right : 8, parent : 5
node : 6, color : BLACK, left : None, right : None, parent : 7
node : 8, color : BLACK, left : None, right : 9, parent : 7
node : 9, color : RED, left : None, right : None, parent : 8
****************************************************************************************************
실행 결과가 이렇게 나오면 잘 작동한 것입니다. 이 실행 결과를 보고 트리의 모습을 직접 그려 보세요.
이로써 레드 블랙 트리 설명을 모두 마쳤습니다. 레드 블랙 트리는 균형 이진 트리이기 때문에 빅오가 BST처럼 O(h)가 아니라 최악의 경우에도 O(log n)입니다. 삽입과 탐색, 그리고 삭제 모두 굉장히 빠른 자료 구조입니다. 다음 장에서는 BST의 변형 중 주로 메인 메모리가 아닌 하드 디스크에 상주하는, 데이터베이스에서 아주 중요한 역할을 하는 자료 구조인 B 트리를 알아보겠습니다.