[자료구조] 트리 용어

트리(Tree)는 나무를 뒤집어 놓은 모습과 같은 비선형이며 계층적인 구조이다.

 

• 부모-자식 관계의 노드들로 구성
• 컴퓨터 디스크의 디렉토리 구조 또한 트리이다.

 

트리의 용어

• 노드(node) : 트리의 구성요소
• 루트(root) : 부모가 없는 노드 ( 젤 위의 노드를 뜻함, A )
• 서브 트리(sub tree) : 하나의 노드와 그 노드의 자손들로 이루어진 트리
• 단말 노드(terminal node) : 자식이 없는 노드 (E,F,G,H,I,J)
• 비 단말 노드 : 적어도 하나의 자식을 가지는 노드 (A,B,C,D)

 

• 자식, 부모, 형제, 조상, 자손 노드
• 차수(degree) : 노드가 가지고 있는 자식 노드의 개수
• 레벨(level) : 트리의 각층의 번호
• 높이(height) : 트리의 최대 레벨(3)

 

 

아래의 그래프를 기준으로

• A는 루트 노드이다.
• B는 D와 E의 부모 노드이다.
• C는 B의 형제 노드이다.
• D와 E는 B의 자식 노드이다.
• B의 차수(degree)는 2이다.
• 위의 트리의 높이는 4이다.

이진 트리(binary tree)

• 모든 노드가 최대 2개의 서브 트리를 가지고 있는 트리
• 서브 트리는 공집합일 수 있다. ( 공집합도 집합이다. )
• 이진 트리의 노드에는 최대 2개까지의 자식 노드가 존재
• 모든 노드의 차수가 2 이하이다.
• 노드의 개수가 n개이면 간선의 개수는 n-1이다.
• 높이가 h인 이진트리의 경우, 최소 h개의 노드를 가지며, 최대 (2^h)-1개의 노드를 가진다.

 

• n개의 노드를 가지는 이진트리의 최대 높이는 n, 최소 높이는 아래와 같다.

 

포화 이진 트리 (full binary tree)

: 트리의 각 레벨에 노드가 꽉 차있는 이진 트리

높이가 k일 때 전체 노드 개수는 (2^k)-1로 구할 수 있다.

 

완전 이진 트리(complete binary tree)

: 레벨 1부터 k-1까지는 노드가 모두 채워져 있고

마지막 레벨 k에서는 왼쪽부터 오른쪽으로 노드가 순서대로 채워져 있는 이진 트리.