20장 : 그래프의 기본 (Graph Basics)

현실 세계에서 모든 사물은 다른 사물과 연관성을 갖습니다.  사람과 사람 사이도 그렇고,  도시와 도시 사이도 그렇습니다.

이런 객체와 그 연관성에 대한 모델링을 그래프(Graph)라고 합니다.  그래프는 객체의 위치는 따지지 않고 오직 연결 관계 즉 위상(Topology)만 따지는 위상수학의 범주에 속합니다.

19장 : 레드-블랙 트리 (Red-Black Tree)

어느덧 검색 알고리즘의 마지막 장입니다.  이번 장에서는 이진트리의 범주를 벗어나지 않으면서 자동으로 균형을 맞추는 알고리즘인 레드-블랙 트리(Red-Black Tree)에 대해 알아봅니다. 

자료를 이진트리로 구성하여 검색 구조로 삼는 이유는 단순한 구조이면서도 자료의 검색, 삽입, 삭제가 효율적이기 때문입니다.  하지만 균형이 맞지 않는 경우 검색 성능이 선형검색과 비슷할 정도로 비효율적입니다.

이 문제를 해결하기 위해 여러가지 알고리즘들이 연구되고 제안되어 왔습니다.  그 중 대표적인 것이 이진트리의 한계에서 벗어나 더 많은 자료를 하나의 노드에 포함하면서 균형 트리를 구현한 B-트리입니다.