Ahn9807: 새 문서: 분류: 자료 구조 == 개요 == 선형 리스트는 포인터를 이용해서 데이터가 한 방향으로 진행하며 도중에 분기하지는 않는다. 이에 반해, 트리는 분기하면서 데이터가 뻗어나가는 형태의 데이터 구조이다. 트리는 노드와 각 노드를 잇는 링크로 구성된다. 노드는 데이터에 해당하고, 링크는 데이터와 데이터를 잇는 부모-자식 관계에 해당한다. 특정 노드에서 아래 방...

2023-02-25T11:04:00Z

새 문서: 분류: 자료 구조 == 개요 == 선형 리스트는 포인터를 이용해서 데이터가 한 방향으로 진행하며 도중에 분기하지는 않는다. 이에 반해, 트리는 분기하면서 데이터가 뻗어나가는 형태의 데이터 구조이다. 트리는 노드와 각 노드를 잇는 링크로 구성된다. 노드는 데이터에 해당하고, 링크는 데이터와 데이터를 잇는 부모-자식 관계에 해당한다. 특정 노드에서 아래 방...

새 문서

[[분류: 자료 구조]]

== 개요 ==
선형 리스트는 포인터를 이용해서 데이터가 한 방향으로 진행하며 도중에 분기하지는 않는다. 이에 반해, 트리는 분기하면서 데이터가 뻗어나가는 형태의 데이터 구조이다. 트리는 노드와 각 노드를 잇는 링크로 구성된다. 노드는 데이터에 해당하고, 링크는 데이터와 데이터를 잇는 부모-자식 관계에 해당한다. 특정 노드에서 아래 방향으로 분기하는 링크의 끝에 있는 노드를 '자식 노드'라 하고 분기가 시작되는 노드를 '부모 노드'라 한다. 트리는 계층 구조를 표현하기에 적합하다.

== 수학적 정의 ==
트리는 그래프의 특수한 분류이다. 트리는 방향그래프로, 루트에서 다른 정점으로 가는 경로가 단 하나 존재하는 그래프이다.

# G는 트리이다.
# G의 모든 두개의 정점은 하나의 경로로 연결되어 있다. (두 정점을 잇는 경로는 단 하나만 존재한다.)
# G의 정점은 모두 연결되어 있다. (Connected Graph) 그러나 E를 하나 제거하면 V는 G에서 떨어져 나간다. (G becomes disconnected)
# G는 연결 그래프이고, <math display="inline">|E|=|V|-1</math>
# G는 Acyclic 이고 (순환 고리가 없고), <math display="inline">|E|=|V|-1</math>
# G는 Acyclic 이고, 만약 엣지가 추가되면 G는 cyclic 이 된다.

== 용어 ==
*노드(node): 트리를 구성하는 기본 원소
*루트 노드(Root Node): 트리에서 부모가 없는 최상위 노드
*부모 노드(Parent Node): 로트 노드 방향으로 직접 연결된 노드
*자식 노드(Child Node): 부모와 연결된 노드
*형제 노드(Siblings Noe): 같은 부모 노드를 갖는 노드
*리프 토드(Leaf Node): 자식이 없는 노드
*경로(Path): 한 노드에서 다른 한 노드에 이르는 길 사이에 있는 노드들의 순서
*길이(Length): 출발 노드에서 도착 노드까지 거치는 노드의 갯수. 특히 시작점과 출발점이 같은 경로의 길이는 0이다. (시작점과 도착점 사이의 에지의 개수)
*깊이(Depth): 루트 노드에서 자기자신까지 가는 경로의 길이이다. 루트노드는 0이다.
*레벨(Level): 루트 노드 부터 노드까지 연결된 엣지 수의 합 + 1 (깊이 + 1)
*높이(Height): 가장 긴 루트 경로의 길이
*차수(Degree): 각 노드의 자식의 갯수
*크기(SIze): 노드의 갯수
*너비(Width): 가장 많은 노드를 갖는 레벨의 크기

== 종류 ==
#[[이진 트리]]
#[[B-Tree]]
#[[포레스트]]
#[[트라이]]

트리 - 편집 역사