개요
선형 리스트는 포인터를 이용해서 데이터가 한 방향으로 진행하며 도중에 분기하지는 않는다. 이에 반해, 트리는 분기하면서 데이터가 뻗어나가는 형태의 데이터 구조이다. 트리는 노드와 각 노드를 잇는 링크로 구성된다. 노드는 데이터에 해당하고, 링크는 데이터와 데이터를 잇는 부모-자식 관계에 해당한다. 특정 노드에서 아래 방향으로 분기하는 링크의 끝에 있는 노드를 '자식 노드'라 하고 분기가 시작되는 노드를 '부모 노드'라 한다. 트리는 계층 구조를 표현하기에 적합하다.
수학적 정의
트리는 그래프의 특수한 분류이다. 트리는 방향그래프로, 루트에서 다른 정점으로 가는 경로가 단 하나 존재하는 그래프이다.
- G는 트리이다.
- G의 모든 두개의 정점은 하나의 경로로 연결되어 있다. (두 정점을 잇는 경로는 단 하나만 존재한다.)
- G의 정점은 모두 연결되어 있다. (Connected Graph) 그러나 E를 하나 제거하면 V는 G에서 떨어져 나간다. (G becomes disconnected)
- G는 연결 그래프이고, [math]|E|=|V|-1[/math]
- G는 Acyclic 이고 (순환 고리가 없고), [math]|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): 가장 많은 노드를 갖는 레벨의 크기