이번에는 기타 이진 트리와 분할 정복에 관해 알아봅시다.
트리는 용도에 따라 매우 다양한 형태를 지닙니다. 여기에서는 힙 정렬 알고리즘을 소개하면서 힙 트리를 다루고 수식 계산기에 사용하는 수식 파서 트리를 살펴볼게요. 그리고 문제를 분할한 후에 작은 문제를 해결하는 과정을 통해 전체 문제를 정복해 나가는 병합 정렬 알고리즘을 살펴볼 거예요. 병합 정렬 알고리즘에서 정렬할 배열을 분리하는 부분은 재귀적인 방법을 사용할 수 있어 분할 정복 알고리즘은 재귀 알고리즘으로 분류할 수 있습니다.
힙 트리는 완전 이진 트리로 노드를 이용하여 구현하는 것보다 배열을 이용하여 구현하는 것이 효과적입니다. 여기서는 자신의 부모 인덱스와 자식 인덱스를 계산할 수 있어야 하는데 이들에 대해서도 다룰 거예요.
그리고 연산자 우선 순위에 맞게 수식을 계산하기서는 연산자를 피연산자 사이에 표현하는 중위 표기법이 아닌 연산자를 뒤에 표현하는 후위 표기법으로 나타내야 계산할 수 있습니다. 이를 스택을 이용하여 표현할 수도 있지만 파서 트리를 통해 운행 방법에 따라 원하는 표기법에 맞게 배치할 수 있어요. 여기에서는 수식 파서 트리를 이용하는 방법을 다룰 거예요.
이 책에서는 다루지 않지만 이진 탐색 트리 중에서 왼쪽 자식과 오른쪽 자식이 없을 때 링크를 순회하기 쉽게 이용하는 스레드 이진 탐색 트리가 있습니다. 왼쪽 자식이 없을 때는 중위 순회 운행에서의 이전 노드를 가리키게 하고 오른쪽 자식이 없을 때 중위 순회 운행에서의 이후 노드를 가리키게 합니다. STL의 map처럼 반복자를 제공하여 순차적으로 접근하는 기능을 제공하는 이진 탐색 트리를 구현할 때 스레드 이진 탐색 트리로 구현할 수 있습니다.
그리고 이진 탐색 트리에 자료를 보관하는 순서에 따라 한 쪽으로 기울어지는 편향 트리(혹은 사향 트리) 형태를 지니면 탐색 속도가 O(N)으로 나빠질 수 있습니다. 이러한 문제를 해결하기 위해 균형을 맞추면서 트리의 높이를 작게 만드는 다양한 트리와 알고리즘들이 있으며 대표적으로 AVL 트리가 있습니다. AVL 트리에서는 왼쪽 서브 트리의 높이와 오른쪽 서브 트리의 높이 차인 균형 값(Balanced Value)을 노드마다 갖고 있고 균형 값의 절대 값이 1보다 작거나 같게 유지합니다.
여기에서는 힙 트리와 파서 트리를 소개할 것이며 탐욕 알고리즘을 다룰 때 최소 신장 트리도 다룰 거예요. 이 외에도 B트리, B* 트리, B+트리, 2-3 트리, 빨강 검정 트리 등이 있습니다.
