트리(tree)와 이진 트리(binary tree) 기초 개념 정리

트리(tree)란?

• 노드들의 집합
• 각 노드는 값과 다른 노드들을 가리키는 레퍼런스들로 구성

 

 

트리 관련 용어

🔸 간선(edge)

• 노드와 노드를 연결하는 선
• 구현 관점에서는 레퍼런스를 의미
• a.k.a. link, branch

🔸 루트(root) 노드

• 트리의 최상단에 있는 노드
• 트리의 시작점

🔸 자녀 노드

• 모든 노드는 0개 이상의 자녀 노드를 가짐

🔸 부모 노드

• 자녀 노드를 가지는 노드

🔸 형제 노드

• 같은 부모를 가지는 노드들

🔸 조상 노드

• 부모 노드를 따라 루트 노드까지 올라가면 만나는 모든 노드

🔸 자손 모드

• 자녀 노드를 따라 내려가며 만날 수 있는 모든 노드

🔸 내부 노드

• 자녀 노드를 가지는 노드
• a.k.a branch node, inner node

🔸 외부 노드

• 자녀 노드가 없는 노드
• a.k.a leaf node, outer node, terminal node

🔸 경로

• 한 노드에서 다른 노드 사이의 노드들의 시퀀스(sequence)

🔸 경로 길이

• 경로에 있는 노드들의 수

🔸 노드의 높이

• 노드에서 자기 자손의 리프 노드까지의 가장 긴 경로의 간선 수

🔸 트리의 높이

• 루트 노드의 높이

🔸 노드의 깊이

• 루트 노드에서 해당 노드까지 경로의 간선 수

🔸 트리의 깊이

• 트리에 있는 노드들의 깊이 중 가장 긴 깊이
• 트리 높이 = 트리 깊이

🔸 노드의 차수(degree)

• 노드의 자녀 노드 수

🔸 트리의 차수

• 트리에 있는 노드들의 차수 중 가장 큰 차수

🔸 두 노드 사이의 거리

• 두 노드의 최단 경로의 간선 수

🔸 노드의 레벨

• 노드와 루트 노드 사이의 경로에서 간선의 수

🔸 width

• 임의의 레벨에서 노드의 수

🔸 노드의 크기

• 자신을 포함한 자손 노드의 수

🔸 트리의 크기

• 트리의 모든 노드의 수

🔸 서브 트리

• 각 노드의 자녀 노드들을 재귀적으로 서브 트리를 구성한다

 

 

트리 구조의 특징

• 루트 노드는 하나만 존재
• 사이클이 존재하지 않음
• 자녀 노드는 하나의 부모 노드만 존재
• 데이터를 순차적으로 저장하지 않는 비선형(nolinear) 구조
• 트리에 서브 트리가 있는 재귀적 구조
• 계층적 구조

 

 

이진 트리(binary tree)란?

• 각 노드의 자녀 노드 수가 최대 2개인 트리
• left child, right child를 가짐

 

형체에 따른 이진 트리 종류

 

🔸 정 이진 트리 (full binary tree)

• 모든 노드는 자녀 노드가 없거나 2개인 트리

🔸 완전 이진 트리 (complete binary tree)

• 마지막 레벨을 제외한 모든 레벨에서 노드가 빠짐없이 채워져 있고 마지막 레벨은 왼쪽부터 빠짐없이 노드가 채워져 있는 트리

🔸 포화 이진 트리(perfect binary tree)

• 모든 레벨에서 노드가 빠짐없이 채워져 있는 트리

🔸 변질 이진 트리(degenerate binry tree)

• 모든 부모 노드는 하나의 자녀 노드만 가지는 트리
• left skewed binary tree
• right  skewed binary tree

🔸 균형 이진 트리 (balanced binary tree)

• 모든 노드에서 왼쪽 서브 트리와 오른쪽 서브 트리의 높이 차이가 최대 1인 트리