트리

트리는 그래프의 특수한 형태로, 사이클이 존재하지 않는 연결 그래프이다. 즉, 임의의 두 노드 사이에 정확히 하나의 경로만 존재하며, 이를 통해 계층적 관계를 명확하게 표현할 수 있다. 이 구조는 1857년 아서 케일리가 화학 이성질체의 수를 세기 위한 수학적 모델로 처음 도입하였다.

트리의 기본 구성 요소는 노드와 간선이다. 가장 상위에 위치한 노드를 루트 노드라 하며, 이 노드는 부모 노드를 가지지 않는다. 루트 노드를 제외한 모든 노드는 정확히 하나의 부모 노드를 가지며, 부모 노드 아래에 연결된 노드를 자식 노드라고 한다. 자식 노드가 없는 노드는 리프 노드 또는 단말 노드라고 부른다. 같은 부모를 가지는 노드들은 형제 노드 관계에 있다.

트리는 방향성에 따라 방향 트리와 무향 트리로 구분된다. 또한 각 노드가 가질 수 있는 자식 노드의 수에 따라 일반 트리와 이진 트리 등으로 분류할 수 있다. 이진 트리는 각 노드의 자식 노드가 최대 두 개인 트리 구조로, 이진 탐색 트리나 힙과 같은 다양한 변형 구조의 기초가 된다.

이러한 계층적 특성 덕분에 트리는 파일 시스템의 디렉토리 구조, 의사 결정 트리 모델링, 데이터베이스의 인덱싱, 네트워크 라우팅 프로토콜 등 컴퓨터 과학의 광범위한 분야에서 핵심적인 자료구조로 활용된다.

트리는 그래프의 특수한 형태로서, 여러 가지 고유한 용어를 사용하여 그 구조를 설명한다. 가장 기본이 되는 용어로는 루트 노드가 있다. 이는 트리의 최상위에 위치하며, 부모 노드를 가지지 않는 유일한 노드이다. 루트 노드에서 아래 방향으로 연결된 노드들은 모두 그 자식 노드들이며, 이 연결 관계를 에지 또는 링크라고 부른다. 자식 노드를 하나도 가지지 않는 노드는 리프 노드 또는 단말 노드라고 한다.

트리 내에서 특정 노드의 상위에 위치한 모든 노드들을 그 노드의 조상 노드라고 하며, 반대로 특정 노드의 하위에 위치한 모든 노드들은 그 노드의 자손 노드라고 한다. 같은 부모 노드를 공유하는 노드들 사이의 관계는 형제 노드 관계이다. 또한, 어떤 노드의 자식 노드 개수를 그 노드의 차수라고 정의하며, 루트 노드에서 특정 노드에 도달하기까지 거쳐야 하는 에지의 수를 그 노드의 레벨 또는 깊이라고 한다. 트리 전체에서 가장 큰 레벨 값을 트리의 높이라고 한다.

이러한 용어 체계는 트리의 계층적 특성을 명확히 기술하는 데 필수적이다. 예를 들어, 파일 시스템에서 디렉토리와 파일의 관계나, 조직도에서 상사와 부하 직원의 관계를 표현할 때, 루트, 부모, 자식, 리프 등의 개념이 직관적으로 적용된다. 트리의 각 구성 요소와 관계에 대한 표준화된 용어는 자료구조와 알고리즘을 논의하고 설계하는 데 있어 공통된 기초를 제공한다.

트리는 그 특성과 용도에 따라 다양한 종류로 분류된다. 가장 기본적인 분류는 간선의 방향성에 따른 것으로, 모든 간선에 방향이 없는 무향 트리와 간선에 방향이 지정된 방향 트리가 있다. 방향 트리에서는 특정 노드가 루트 노드로 지정되며, 이는 계층 구조의 시작점이 된다.

노드가 가질 수 있는 자식 노드의 수에 따라 구분하기도 한다. 이진 트리는 각 노드가 최대 두 개의 자식 노드를 가지는 구조로, 이진 탐색 트리와 같은 특수한 형태의 기초가 된다. 이진 탐색 트리는 왼쪽 서브트리의 모든 노드 값이 부모 노드보다 작고, 오른쪽 서브트리의 모든 노드 값이 부모 노드보다 크다는 순서 속성을 가져 데이터 검색 속도를 높인다.

효율적인 연산을 보장하기 위해 고안된 특수 트리도 있다. 균형 트리는 삽입과 삭제 시 트리의 높이를 자동으로 조정하여 균형을 유지하며, AVL 트리나 레드-블랙 트리가 대표적이다. 힙은 부모 노드와 자식 노드 간에 특정 순서 관계(최대 힙 또는 최소 힙)를 만족하는 완전 이진 트리로, 우선순위 큐 구현에 주로 사용된다.

이 외에도 여러 자식을 가질 수 있는 m-ary 트리, 공통 조상을 빠르게 찾기 위한 유니온 파인드 자료구조에 사용되는 분리 집합의 트리 표현, 공간 분할에 사용되는 쿼드트리와 옥트리 등 응용 분야에 맞춘 다양한 트리 구조가 존재한다.

트리의 순회란 트리에 속하는 모든 노드를 정해진 순서에 따라 한 번씩 방문하는 작업을 말한다. 순회는 트리 구조에 저장된 데이터를 체계적으로 접근하는 기본 연산으로, 트리의 종류와 응용 목적에 따라 다양한 방법이 사용된다.

가장 일반적인 트리 순회 방법은 깊이 우선 탐색과 너비 우선 탐색으로 크게 나눌 수 있다. 깊이 우선 탐색은 한 루트 노드에서 시작하여 가능한 한 깊이 내려간 후, 다시 돌아와 다른 가지를 탐색하는 방식이다. 이진 트리의 경우, 전위 순회 (루트 → 왼쪽 서브트리 → 오른쪽 서브트리), 중위 순회 (왼쪽 서브트리 → 루트 → 오른쪽 서브트리), 후위 순회 (왼쪽 서브트리 → 오른쪽 서브트리 → 루트)라는 세 가지 주요 방법이 있다. 각 방법은 수식 트리의 계산이나 파일 시스템의 구조 출력 등 특정 작업에 적합하다.

너비 우선 탐색은 레벨 순서 순회라고도 하며, 루트 노드에서 시작하여 같은 깊이(레벨)에 있는 모든 노드를 왼쪽에서 오른쪽으로 방문한 후, 다음 레벨의 노드들을 방문하는 방식을 취한다. 이 방법은 큐 자료구조를 사용하여 구현되며, 계층적 구조를 수평적으로 탐색해야 하는 경우, 예를 들어 가계도의 세대별 조회나 네트워크의 최단 경로 탐색에 유용하게 적용된다.

순회 방법의 선택은 알고리즘의 효율성과 결과의 형태에 직접적인 영향을 미친다. 따라서 트리를 활용하는 컴파일러, 데이터베이스 인덱스, 인공지능의 의사결정나무 등 다양한 응용 분야에서는 처리해야 할 작업의 성격에 맞는 적절한 순회 방식을 채택한다.

트리는 메모리 상에서 구현할 때 주로 배열이나 연결 리스트를 기반으로 한 자료 구조를 사용하여 표현한다. 가장 일반적인 표현 방식은 노드와 포인터를 이용하는 연결 구조이다. 각 노드는 저장할 데이터와 함께, 자식 노드들을 가리키는 포인터를 포함한다. 이진 트리의 경우, 각 노드는 왼쪽 자식과 오른쪽 자식을 가리키는 두 개의 포인터를 가지는 것이 일반적이다.

배열을 이용한 표현 방법도 널리 사용된다. 특히 완전 이진 트리나 힙과 같은 특정 형태의 트리를 구현할 때 효율적이다. 이 방식에서는 트리의 노드를 레벨 순서대로 배열에 저장하며, 인덱스 간의 수학적 관계를 통해 부모와 자식 노드의 위치를 빠르게 계산할 수 있다. 예를 들어, 인덱스 i에 위치한 노드의 왼쪽 자식은 2*i, 오른쪽 자식은 2*i + 1 인덱스에 위치하게 된다.

트리의 표현 방식은 수행하려는 연산의 종류와 효율성 요구 사항에 따라 선택된다. 연결 구조는 트리의 동적인 확장과 축소에 유리하며, 배열 기반 구조는 메모리 접근의 지역성으로 인한 성능 향상과 구현의 단순함이 장점이다. 파일 시스템이나 데이터베이스 인덱스와 같은 실제 응용에서는 이러한 기본 표현을 바탕으로 더 복잡한 B-트리나 AVL 트리와 같은 구조가 활용된다.

트리 구조에서 수행되는 기본 연산은 트리의 생성, 조회, 갱신, 삭제를 포함한다. 이러한 연산은 트리의 종류와 구현 방식에 따라 세부적인 동작이 달라질 수 있다.

가장 기본적인 연산으로는 노드의 삽입과 삭제가 있다. 이진 트리에서는 새로운 노드를 특정 위치에 추가하거나, 기존 노드를 제거하면서 남은 자식 노드들을 재배치하는 작업이 필요하다. 이진 탐색 트리의 경우 삽입과 삭제 연산 후에도 키 값의 정렬 순서가 유지되어야 하며, 균형 트리에서는 추가적으로 트리의 높이 균형을 맞추기 위한 회전 연산이 동반된다. 힙에서는 삽입 시 업힙 연산, 삭제 시 다운힙 연산을 통해 자료 구조의 속성을 유지한다.

다른 핵심 연산으로는 특정 노드를 찾는 탐색과 트리의 모든 노드를 체계적으로 방문하는 트리 순회가 있다. 탐색은 이진 탐색 트리에서 효율적으로 수행될 수 있으며, 순회에는 전위, 중위, 후위 순회 등의 방법이 있다. 또한, 트리의 높이를 계산하거나, 서브트리의 크기를 구하거나, 두 노드 사이의 경로를 찾는 등의 조회 연산도 빈번히 사용된다. 이러한 기본 연산들은 자료구조와 알고리즘의 기초를 이루며, 더 복잡한 트리 조작 및 응용의 토대가 된다.