이전 장에서는 다양한 유형의 선형 자료 구조를 구현하여 데이터를 저장하고 관리하는 방법에 대해 알아봤습니다. 선형 구조에서는 최대 두 가지 방향(순방향과 역방향)으로 자료를 순회할 수 있습니다. 그러나 이러한 구조는 매우 제한적이어서 복잡한 문제에는 적용하기 어렵습니다. 이 장에서는 좀 더 고수준의 문제를 다룰 것이며, 이 경우 이전 장에서 구현했던 방법들을 그대로 적용하기 어렵다는 것을 알게 될 것입니다. 그러므로 이전 장에서 배웠던 자료 구조를 확장하여 비선형 데이터를 표현할 수 있는 복잡한 자료 구조를 만들어보겠습니다.

이러한 문제를 살펴본 후, 트리 자료 구조를 사용하는 기본적인 솔루션에 대해 알아볼 것입니다. 다양한 종류의 문제를 해결하기 위해 여러 형태의 트리를 구현할 것입니다. 그리고 힙(heap)이라고 부르는 특별한 형태의 트리에 대해 알아보고, 실제 구현과 응용 방법에 대해서도 설명하겠습니다. 그러고 나서 좀 더 복잡한 형태의 자료 구조인 그래프에 대해 살펴볼 것입니다. 그래프는 두 가지 형태로 구현할 수 있습니다. 이들 구조는 실세계에서 접할 수 있는 문제를 수학적 형태로 표현합니다. 그런 다음 실제 프로그래밍을 통해 주어진 문제를 해결해보겠습니다.

트리와 그래프에 대해 제대로 이해하고 있어야 나중에 나올 더 복잡한 문제를 해결할 수 있습니다. 데이터베이스(B-트리(B-tree)), 데이터 인코딩/압축(허프만 트리(Huffman tree)), 그래프 컬러링(graph coloring), 할당 문제(assignment problem), 최소 거리 문제(minimum distance problem) 등의 많은 문제를 트리와 그래프 구조를 이용하여 해결할 수 있습니다.

그럼 우선 선형 자료 구조로 표현할 수 없는 문제들에 대해 알아보겠습니다.