[ 자료구조 ] 트리 용어 정리

트리(Tree)는 원소들이 부모-자식의 관계로 저장되는 노드(nodes)들의 집합이다. 비순환적으로 연결되어 있는 그래프로 이해해도 무관하다. 트리를 공부하기 전에 트리와 관련된 용어를 정리할 필요가 있어서 이 글에서는 트리 용어만 다룬다. 

 

트리에는 여러 종류의 노드가 존재한다. 노드란 트리의 꼭지점을 의미한다. 노드의 특성에 따라 이름이 부여되는데, 우리가 살펴볼 노드는 아래와 같다. 각각 어떤 특성이 존재하는지 하나씩 알아보자. 

부모 노드, 자식 노드, 루트 노드, 리프 노드(외부 노드), 중간 노드(내부 노드), 조상 노드, 자손 노드

 

노드(Node) 종류

1. 부모-자식 노드

직접 연결된 두 꼭지점은 부모-자식 관계를 가진다. 여기서 위에 위치한 노드를 ‘부모 노드’, 아래에 위치한 노드를 ‘자식 노드’라고 한다. 참고로 노드끼리의 연결선을 ‘엣지’ 또는 ‘링크’라고 한다. 

 

 

2. 형제 노드

같은 부모를 가진 노드. 

 

3. 루트 노드

트리의 최상위 노드. 모든 노드의 '조상'이 되는 노드.

 

4. 리프 노드(외부 노드)

자식 노드가 없는 말단 노드

 

5. 중간 노드(내부 노드)

자식을 하나 이상 가지는 노드. 루트 노드와 리프 노드를 제외한 모든 노드. 루트 노드를 중간 노드에 포함시켜도 되는데 나는 그냥 둘을 구별했다. '루트 노드는 중간 노드' 명제는 참이다. 

 

6. 조상 노드

어떤 노드로부터 루트 노드까지의 최단경로상에 위치한 모든 노드. 아래 그림은 시작 노드의 조상 노드를 나타낸 그림이다. 

 

7. 자손 노드

어떤 노드의 하위 모든 노드. 아래 그림은 시작 노드의 자손 노드를 나타낸 그림이다. 

추가 용어 설명

1. 서브 트리

트리의 부분집합을 말한다. 트리는 아래 그림과 같이 다시 여러 개의 트리로 나뉠 수 있는데, 이렇게 트리로부터 파생되는 모든 트리를 ‘서브 트리’라고 한다. 

 

2. 깊이(레벨), 높이

어떤 노드의 조상 수. 루트 노드는 깊이가 0, 아래 층으로 갈수록 깊이는 1씩 증가하게 된다. 깊이의 최대값을 트리의 '높이'라고 한다.

3. 차수

어떤 노드의 자손 노드 개수. 아래 그림에서 모든 노드의 차수를 적어놨다. 부모 노드의 차수는 (자식 노드 차수합 + 자식노드 수) 를 유도할 수 있다. 

트리의 성질

• 두 노드간 최단경로는 유일하다
• 노드가 N개인 트리는 항상 (N-1)개의 링크를 가진다

 

 

트리 용어 정리는 이렇게 마무리한다. 다음 글의 주제는 '이진 트리'가 될 것 같다.