트리 개념

선형 자료 구조(linear data structure): 자료들이 선형으로 나열되어 있는 구조

- 리스트, 스택, 큐 등

- 자료가 계층적인 구조(hierarchical structure)를 가지고 있다면 선형 자료 구조로 표현 부적합

- 트리: 계층적인 자료를 표현하는 데 적합한 자료구조

---

트리 용어

 

트리는 노드와 간선으로 구성

 

- 노드(node): A~J와 같은 각 항목

- 트리는 한 개 이상의 노드로 이루어진 유한 집합

- 루트(root) 노드: 계층 구조에서 가장 높은 곳에 있는 노드

- 서브 트리(subtree): 루트 노드에서 나누어지는 노드들({B, E, F, G}, {C, H}, {D, I, J})

- 서브 트리에도 다시 루트와 서브 트리가 존재함(B - {E}, {F}, {G})

- 간선(edge): 루트와 서브트리를 잇는 선

 

노드들 간에 부모, 형제, 조상과 후손 관계 존재

- 레벨(level): 트리의 각 층에 매겨진 번호로, 루트의 레벨은 1이고 한 층씩 내려갈수록 1씩 증가

- 트리의 높이(height): 트리가 가지고 있는 최대 레벨

- 차수(degree): 어떤 노드가 가지고 있는 자식 노드의 개수

- 트리의 차수: 트리가 가지고 있는 노드의 차수 중에서 가장 큰 값

- 부모 노드(parent node): 어떤 노드의 루트 노드

- 자식 노드(children node): 어떤 노드의 하위 노드

- 조상 노드(ancestor node): 루트 노드에서 임의의 노드까지의 경로를 이루고 있는 노드들

- 후손 노드(descendent node): 임의의 노드 하위에 연결된 모든 노드들

- 어떤 노드의 서브 트리에 속하는 모든 노드들은 후손 노드

- 단말 노드(terminal node/leaf node): 자식 노드가 없는 노드(차수=0)

- 비단말 노드(nonterminal node): 자식 노드가 있는 노드

- 트리들의 집합을 포레스트(forest)라 함

---

트리의 종류

- 트리를 컴퓨터 메모리상에서 표현하는 가장 일반적인 방법은 각 노드가 데이터를 저장하는 데이터 필드와 자식 노드를 가리키는 링크 필드를 가지게 하는 것

- 일반적인 트리에서 각 노드들은 서로 다른 개수의 자식 노드를 가짐

- 노드의 크기가 고정되지 않음(일정하지 않음)

→ 프로그램이 복잡해짐

- 앞으로는 자식 노드의 개수가 2개인 이진 트리를 주로 다룰 예정