트리 (자료 구조)

모델에 대해서는 트리 구조 (모델) 문서를 참고하십시오.

컴퓨터 과학에서 트리'(tree, 문화어: 나무)는 연결된 노드 집합을 가진 계층적 트리 구조를 나타내는 널리 사용되는 추상 자료형이다. 트리의 각 노드는 많은 자식에 연결될 수 있지만(트리 유형에 따라 다름) 루트 노드를 제외하고는 정확히 하나의 부모에 연결되어야 한다.^[1][2] (즉, 루트 노드는 트리 계층 구조에서 가장 상위 노드이다.) 이러한 제약 조건은 순환이나 "루프"가 없으며(어떤 노드도 자신의 조상이 될 수 없음) 각 자식을 자신의 서브트리의 루트 노드처럼 취급할 수 있음을 의미하므로 재귀는 트리 순회에 유용한 기술이다. 선형 자료 구조와 달리 많은 트리는 단일 직선(두 인접 노드 간의 에지 또는 링크라고 함)에서 인접 노드(해당 노드의 부모 및 자식 노드, 존재하는 경우) 간의 관계로 표현할 수 없다.

이 정렬되지 않은 트리는 고유하지 않은 값(예: 단일 노드에만 존재하는 것이 아니라 다른 노드에 존재하는 값 2)을 가지며 이진 트리가 아니다(이진 트리에서는 부모 노드당 최대 두 개의 자식 노드만 존재). 가장 상위(여기서는 값 2)에 있는 루트 노드는 트리 계층 구조에서 가장 높기 때문에 부모가 없다.

이진 트리는 일반적으로 사용되는 유형으로, 각 부모의 자식 수를 최대 두 개로 제한한다. 자식의 순서가 지정되면 이 자료 구조는 그래프 이론의 정렬된 트리에 해당한다. 트리의 모든 노드 또는 때로는 자식 노드가 없는 리프 노드에만 값 또는 다른 데이터에 대한 포인터가 연결될 수 있다.

추상 자료형(ADT)은 자식에 대한 포인터가 있는 부모 목록, 부모에 대한 포인터가 있는 자식 목록 또는 노드 목록과 별도의 부모-자식 관계 목록(인접 리스트의 특정 유형)을 포함하여 여러 가지 방식으로 표현될 수 있다. 표현은 성능을 위해 인덱스 또는 조상 목록을 사용하는 등 더 복잡할 수도 있다.

컴퓨팅에 사용되는 트리는 나무 그래프, 나무, 서술 집합론의 트리와 같은 수학적 구성과 유사하지만 다를 수 있다.

용어

노드는 데이터와 다른 노드에 대한 연결을 포함할 수 있는 구조로, 때로는 에지 또는 링크라고도 한다. 트리의 각 노드에는 트리의 아래에 있는 0개 이상의 자식 노드가 있다(관례적으로 트리는 자손이 아래로 내려가도록 그려진다). 자식을 가진 노드를 자식의 부모 노드(또는 상위)라고 한다. 모든 노드는 정확히 하나의 부모를 가지며, 가장 상위의 루트 노드는 부모가 없다. 노드는 부모의 부모와 같은 많은 조상 노드를 가질 수 있다. 같은 부모를 가진 자식 노드는 형제 노드이다. 일반적으로 형제는 순서가 있으며, 첫 번째는 관례적으로 왼쪽에 그려진다. 일부 정의는 트리에 노드가 전혀 없을 수도 있다고 허용하는데, 이 경우 빈 트리라고 한다.

내부 노드(또는 이너 노드, 줄여서 아이노드 또는 브랜치 노드)는 자식 노드를 가진 트리의 모든 노드를 말한다. 마찬가지로 외부 노드(또는 아우터 노드, 리프 노드 또는 터미널 노드)는 자식 노드를 가지지 않는 모든 노드를 말한다.

노드의 높이는 해당 노드에서 리프까지의 가장 긴 하향 경로의 길이이다. 루트의 높이는 트리의 높이이다. 노드의 깊이는 루트까지의 경로(즉, 루트 경로)의 길이이다. 따라서 루트 노드의 깊이는 0이고, 리프 노드의 높이는 0이며, 단일 노드만 있는 트리(따라서 루트이자 리프)의 깊이와 높이는 0이다. 관례적으로 빈 트리(노드가 없는 트리, 허용되는 경우)의 높이는 -1이다.

각 비루트 노드는 자신과 모든 자손을 포함하는 자신만의 서브트리의 루트 노드로 취급될 수 있다.^[a][3]

트리와 함께 사용되는 다른 용어:

이웃

부모 또는 자식 노드.

조상

자식에서 부모로 반복적으로 진행하여 도달할 수 있는 노드.

자손

부모에서 자식으로 반복적으로 진행하여 도달할 수 있는 노드. 서브차일드(subchild)라고도 한다.

차수

주어진 노드의 자식 수. 리프는 정의상 차수가 0이다.

트리의 차수

트리의 차수는 트리에서 노드의 최대 차수이다.

거리

두 노드 사이의 최단 경로를 따라 있는 에지의 수.

레벨

노드의 레벨은 해당 노드와 루트 노드 사이의 고유한 경로를 따라 있는 에지의 수이다.^[4] 이는 깊이와 같다.

너비

한 레벨의 노드 수.

폭

리프의 수.

완전 트리

마지막 레벨을 제외하고 모든 레벨이 채워진 트리.

숲

하나 이상의 서로소 트리의 집합.

순서 트리

각 정점의 자식에 대한 순서가 지정된 루트 트리.

트리의 크기

트리의 노드 수.

일반적인 연산

• 모든 항목 열거
• 트리의 특정 부분 열거
• 항목 검색
• 트리의 특정 위치에 새 항목 추가
• 항목 삭제
• 가지치기: 트리의 전체 섹션 제거
• 접목: 트리에 전체 섹션 추가
• 어떤 노드의 루트 찾기
• 두 노드의 최소 공통 조상 찾기

순회 및 검색 방법

 이 부분의 본문은 트리 순회입니다.

부모와 자식 간의 연결을 통해 트리의 항목을 단계별로 탐색하는 것을 트리 워킹이라고 하며, 그 행동을 트리의 워크라고 한다. 종종 포인터가 특정 노드에 도달하면 작업이 수행될 수 있다. 각 부모 노드가 자식보다 먼저 순회되는 워크를 선위 순회라고 한다. 자식이 해당 부모보다 먼저 순회되는 워크를 후위 순회라고 한다. 노드의 왼쪽 서브트리, 그 다음 노드 자체, 마지막으로 오른쪽 서브트리가 순회되는 워크를 중위 순회라고 한다. (정확히 두 개의 서브트리, 왼쪽 서브트리와 오른쪽 서브트리를 참조하는 이 마지막 시나리오는 특히 이진 트리를 가정한다.) 레벨 순서 워크는 트리 전체에 대해 효과적으로 너비 우선 탐색을 수행한다. 노드는 레벨별로 순회되며, 루트 노드가 먼저 방문되고, 그 다음으로 직접적인 자식 노드와 그 형제 노드, 그 다음으로 손자 노드와 그 형제 노드 등이 트리의 모든 노드가 순회될 때까지 순서대로 방문된다.

표현

트리를 표현하는 방법에는 여러 가지가 있다. 작업 메모리에서 노드는 일반적으로 동적으로 할당된 레코드로, 자식, 부모 또는 둘 모두에 대한 포인터와 관련 데이터가 포함된다. 고정 크기인 경우 노드는 목록에 저장될 수 있다. 노드와 노드 간의 관계는 별도의 특별한 유형의 인접 리스트에 저장될 수 있다. 관계형 데이터베이스에서는 노드가 일반적으로 테이블 행으로 표현되며, 인덱싱된 행 ID가 부모와 자식 간의 포인터를 용이하게 한다.

노드는 배열의 항목으로 저장될 수도 있으며, 노드 간의 관계는 배열 내의 위치에 따라 결정된다(이진 힙과 같이).

이진 트리는 리스트의 리스트로 구현될 수 있다. 리스트의 헤드(첫 번째 항의 값)는 왼쪽 자식(서브트리)이고, 테일(두 번째 이후 항의 리스트)은 오른쪽 자식(서브트리)이다. 이는 Lisp S-표현식과 같이 값도 허용하도록 수정될 수 있으며, 여기서 헤드(첫 번째 항의 값)는 노드의 값이고, 테일의 헤드(두 번째 항의 값)는 왼쪽 자식이고, 테일의 테일(세 번째 이후 항의 리스트)은 오른쪽 자식이다.

순서 트리는 예를 들어 자연수로 유한 시퀀스로 자연스럽게 인코딩될 수 있다.^[5]

트리 및 비트리 예시

트리가 아님: 두 개의 비-연결된 부분, A→B 및 C→D→E. 루트가 하나 이상이다.

트리가 아님: 무방향 순환 1-2-4-3. 4는 부모가 하나 이상이다(인바운드 에지).

트리가 아님: 순환 B→C→E→D→B. B는 부모가 하나 이상이다(인바운드 에지).

트리가 아님: 순환 A→A. A는 루트이지만 부모도 있다.

각 선형 목록은 사소하게 트리이다.

유형 이론

추상 자료형으로서, 특정 유형 E의 값을 가진 추상 트리 유형 T는 추상 숲 유형 F(트리 목록)를 사용하여 다음 함수로 정의된다.

value: T → E

children: T → F

nil: () → F

node: E × F → T

다음 공리를 가진다.

value(node(e, f)) = e

children(node(e, f)) = f

유형 이론의 관점에서 트리는 nil(빈 숲)과 node(주어진 값과 자식을 가진 루트 노드가 있는 트리) 생성자에 의해 정의된 귀납적 유형이다.

수학적 용어

전체적으로 볼 때 트리 자료 구조는 일반적으로 각 노드에 값이 연결된 순서 트리이다. 구체적으로 말하면 (비어 있지 않아야 하는 경우):

• "루트에서 멀리 떨어진" 방향을 가진 근원 트리 (더 좁은 용어는 "아보레선스")를 의미한다.
  • 유향 그래프,
  • 기본 무향 그래프는 트리이다 (두 정점은 정확히 하나의 단순 경로로 연결된다).^[6]
  • 특정된 루트를 가진다 (하나의 정점이 루트로 지정된다),
  • 에지의 방향을 결정한다 (화살표는 루트에서 멀리 떨어진 방향을 가리킨다. 에지가 주어지면 에지가 가리키는 노드는 부모라고 불리고 에지가 가리키는 노드는 자식이라고 불린다), 다음을 포함한다.
• 주어진 노드의 자식 노드에 대한 순서, 그리고
• 각 노드의 값 (일부 자료형).

종종 트리는 고정된 (더 정확히는 경계가 있는) 가지치기 계수 (아웃디그리)를 가지며, 특히 항상 두 개의 자식 노드(비어 있을 수 있으므로 최대 두 개의 비어 있지 않은 자식 노드)를 가지므로 "이진 트리"가 된다.

빈 트리를 허용하면 일부 정의가 더 간단해지고 일부는 더 복잡해진다. 근원 트리는 비어 있지 않아야 하므로, 빈 트리가 허용되는 경우 위 정의는 대신 "빈 트리 또는 그러한 루트 트리가 ..."가 된다. 반면에 빈 트리는 고정 가지치기 계수를 정의하는 것을 단순화한다. 빈 트리가 허용되는 경우 이진 트리는 모든 노드가 정확히 두 개의 자식을 가지는 트리이며, 각 자식은 트리(비어 있을 수 있음)이다.

응용

트리는 다음과 같은 응용 프로그램에서 계층적 데이터를 표현하거나 조작하는 데 일반적으로 사용된다.

• 파일 시스템:
  • 하위 디렉터리와 파일을 구성하는 데 사용되는 디렉터리 구조 (심볼릭 링크는 동일한 파일 또는 디렉터리에 대한 여러 하드 링크와 마찬가지로 비트리 그래프를 생성함)
  • 저장 장치에서 데이터 블록을 할당하고 연결하는 데 사용되는 메커니즘
• 객체 지향 프로그래밍에서 클래스 간의 관계를 보여주는 클래스 계층 구조 또는 "상속 트리" (다중 상속은 비트리 그래프를 생성함)
• 컴퓨터 언어의 추상 구문 트리
• 자연어 처리:
  • 파스 트리
  • 생성문법에서 발화 모델링
  • 대화 생성을 위한 대화 트리
• XML 및 HTML 문서의 문서 객체 모델("DOM 트리")
• 탐색 트리는 트리 순회를 통해 효율적인 검색 알고리즘을 가능하게 하는 방식으로 데이터를 저장한다.
  • 이진 탐색 트리는 이진 트리의 한 유형이다.
• 데이터의 정렬된 목록 표현
• 컴퓨터 생성 이미지:
  • 공간 분할, 이진 공간 분할법 포함
  • 디지털 합성
• 은하계 시뮬레이션에 사용되는 반스-헛 트리 저장
• 힙 구현
• 중첩 집합 컬렉션
• [[분류학 (일반)#응용|점점 더 구체적인 섹션이 있는 듀이 십진분류법과 같은 계층적 분류법.]]
• 계층적 시간 메모리
• 유전 프로그래밍
• 계층적 군집화

트리는 다음과 같은 다양한 수학적 구조를 표현하고 조작하는 데 사용될 수 있다.

• 임의의 노드-및-에지 그래프(다중 그래프 포함)를 통한 경로(여러 경로에 사용된 각 그래프 노드에 대해 트리에서 여러 노드를 만들어)
• 모든 수학적 계층 구조

트리 구조는 다음과 같은 것들 간의 관계를 매핑하는 데 종종 사용된다.

• 분해도에서 시각화할 수 있는 구성 요소 및 하위 구성 요소
• 재귀적이지 않게 프로그램에서 다른 서브루틴을 호출하는 서브루틴을 식별하는 데 사용되는 서브루틴 호출
• 진화에 의한 종 간의 DNA 상속, 소프트웨어 프로젝트에 의한 소스 코드 상속(예: 리눅스 배포판 타임라인), 다양한 유형의 자동차 디자인 등
• 계층적 이름공간의 내용

JSON 및 YAML 문서는 트리로 생각할 수 있지만 일반적으로 중첩된 리스트 및 딕셔너리로 표현된다.

같이 보기

• 힙
• 연결 리스트
• 그래프 이론
• 분류:트리 구조