C Data Structure - 이진 탐색 트리 1

오늘은 이진 탐색 트리이다. 

이전까지는 선형 자료 구조를 공부했었다. 뭐 예를 들어, 일반 배열 리스트, 연결 리스트, 스택, 큐 등의 선형 구조만 포스팅했는데, 드디어! 비 선형 자료 구조이다. 

데이터가 선형으로 연속되지 않는만큼 삽입, 삭제, 탐색 연산에 신경쓸게 더 많다. 그래도 이렇게 선형을 끝내고 비선형을 진행하는게 뿌듯하긴 하지만 이게 들이는 시간에 비해 결과가 그렇게 크지 않아서 비선형 자료구조를 여러 가지의 예제로 다양하게 진행하지는 못할 것 같고, 핵심만 파악할 수 있는 그런 알찬 예제로 기록을 해 둘 것이다.

나중에 다시 봐도 아~ 이게 트리지 할 수 있도록.

일단은 나는 연결 리스트 기반의 이진 탐색 트리를 구현할 것이며, 데이터의 삽입, 삭제, 탐색(레벨 순회, 전위 순회, 중위 순회, 후위 순회)까지 구현할 것이다. 

배열 기반의 이진 트리는 Heap 자료 구조에서 구현이 될 것인데, 아래의 링크에서 Heap 구조를 알 수 있다. 기본은 Heap이지만 내용은 거의 우선 순위 큐이다. 다만, 큐 형태로 Wrapping만 하지 않았을 뿐...

C Data Structure - Heap ( Priority Queue, 우선 순위 큐 ) 개념 및 코드 구현

특이사항이라면,

이전과 마찬가지로 메모리 관리는 기존에 공부했던 배열 기반 스택을 통해 이루어진다. 
레벨 순회를 위해서 배열 기반 원형 큐를 이용한다.

트리를 제외하고 부가적으로 자료구조를 이용할 때에는 메모리를 할당하지 않는 배열 기반으로 

그렇다면 군말없이 바로 시작해보자!

트리란? 

먼저 트리의 구조나 용어를 설명한다. 트리는 이러하다.

트리는 다음과 같이 여러 형태의 트리들이 올 수 있지만

그 중에 이진 탐색 트리에 대해서 기록할 것이다. 위 그림에서 가운데에 있는 트리 구조가 가장 이진 탐색 트리를 잘 나타낸 이진 탐색 트리의 모형이라고 보면 된다.

그러면 이진 트리란?

이진 트리에 논하기에 앞서, 가장 작은 단위인 노드부터 자세히 살펴보면 다음과 같은 구조로 되어 있다.

이런 노드를 요리조리 이용하면 트리를 완성시킬 수 있는데, 노드가 이렇게 최대 두 개의 자식을 가질 수 있는 형태로 이루어져 있으며, 이러한 노드들로 구성되어 있는 트리를 이진 트리라고 한다.

그러면 이진 탐색 트리는 또 무엇인가? 이진 탐색 트리는 이진 트리이긴 한데, 탐색이 가능한 트리라서 이진 탐색 트리라고 한다! 그러기 위해선 일정 조건들이 추가 되어야 하는데 조건은 다음과 같다.

위와 같은 조건을 가지고 있는 이진 트리가 이진 탐색 트리가 될 수 있다.

다음 포스팅은 삽입, 삭제, 탐색을 적절히 나눠서 여러 차례 포스팅한다.