문서 편집 권한이 없습니다. 다음 이유를 확인해주세요: 요청한 명령은 다음 권한을 가진 사용자에게 제한됩니다: 사용자. 문서의 원본을 보거나 복사할 수 있습니다. [[분류: 자료 구조]] == 개요 == 선형 리스트는 포인터를 이용해서 데이터가 한 방향으로 진행하며 도중에 분기하지는 않는다. 이에 반해, 트리는 분기하면서 데이터가 뻗어나가는 형태의 데이터 구조이다. 트리는 노드와 각 노드를 잇는 링크로 구성된다. 노드는 데이터에 해당하고, 링크는 데이터와 데이터를 잇는 부모-자식 관계에 해당한다. 특정 노드에서 아래 방향으로 분기하는 링크의 끝에 있는 노드를 '자식 노드'라 하고 분기가 시작되는 노드를 '부모 노드'라 한다. 트리는 계층 구조를 표현하기에 적합하다. == 수학적 정의 == 트리는 그래프의 특수한 분류이다. 트리는 방향그래프로, 루트에서 다른 정점으로 가는 경로가 단 하나 존재하는 그래프이다. # 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]] #[[포레스트]] #[[트라이]] 트리 문서로 돌아갑니다.