트리(이진트리)

트리는 정점(Vertex) 과 간선(Edge) 으로 구성된 비선형 자료구조입니다. 그래프의 한 종류이며, 사이클이 없고 모든 노드가 하나의 연결 요소로 이어져 있는 구조입니다. 계층적인 구조를 가지며 상위-하위 관계를 표현하기에 적합합니다.

 

트리의 특징

1. 계층 구조
   • 트리는 부모-자식 관계로 연결된 계층 구조를 가집니다.
   • 루트에서 리프까지 내려가는 방향성 있는 관계입니다.
2. 사이클 없음 (Acyclic)
   • 순환이 존재하지 않으며, 임의의 두 노드 사이의 경로는 유일합니다.
3. 간선의 개수 = 정점의 수 - 1 (V - 1 = E)
   • 트리는 N개의 정점을 가지면 항상 N - 1개의 간선을 가집니다.

트리의 기본 용어

용어	설명
루트 노드 (Root)	트리의 최상위 노드. 유일하게 부모가 없음
부모 노드 (Parent)	다른 노드를 직접 연결하는 상위 노드
자식 노드 (Child)	부모로부터 직접 연결된 하위 노드
형제 노드 (Sibling)	같은 부모를 공유하는 노드
리프 노드 (Leaf)	자식이 없는 종단 노드
내부 노드 (Internal Node)	자식 노드가 있는 노드 (리프가 아닌 노드)
서브트리 (Subtree)	특정 노드를 루트로 하는 하위 트리
깊이 (Depth)	루트에서 특정 노드까지 도달하기 위한 간선의 수
높이 (Height)	특정 노드에서 가장 멀리 있는 리프 노드까지의 거리
레벨 (Level)	노드의 깊이를 표현한 값. 루트는 0 혹은 1로 시작

트리의 집합적 표현

• 숲 (Forest)
  트리들의 집합을 숲이라 합니다. 하나의 트리에서 루트 노드를 제거하면 숲이 됩니다.

이진 트리 (Binary Tree)

이진 트리는 모든 노드가 최대 2개의 자식 노드만 가질 수 있는 트리입니다.
자식 노드는 일반적으로 왼쪽(left) 과 오른쪽(right) 으로 구분됩니다.

 

이진 트리의 용도

• 트리 기반 탐색 (예: 이진 탐색)
• 수식 표현 (Expression Tree)
• 우선순위 큐 (Heap)
• 정렬 및 검색 알고리즘에 활용

이진 트리의 분류

종류	설명
정 이진 트리 (Full Binary Tree)	각 노드가 자식 노드를 0개 또는 2개만 가지는 트리
완전 이진 트리 (Complete Binary Tree)	마지막 레벨을 제외하고 모두 채워져 있으며, 마지막 레벨은 왼쪽부터 채워진 트리
포화 이진 트리 (Perfect Binary Tree)	모든 리프 노드가 같은 레벨에 있고, 모든 내부 노드가 자식 노드를 2개씩 가짐
편향 이진 트리 (Skewed Binary Tree)	모든 노드가 한쪽 자식만 가짐 (왼쪽 또는 오른쪽에만 자식이 있는 트리)
균형 이진 트리 (Balanced Binary Tree)	모든 노드에 대해 왼쪽과 오른쪽 서브트리의 높이 차이가 1 이하인 트리

균형 이진 트리의 대표적인 예로 AVL 트리, 레드-블랙 트리 등이 있습니다. 이러한 구조는 삽입/삭제 시 트리를 자동으로 재구성하여 균형을 유지합니다.

 

 

이진 탐색 트리 (Binary Search Tree, BST)

이진 탐색 트리는 이진 트리의 특수한 형태로, 노드들이 정렬된 방식으로 구성되어 있어 탐색이 효율적입니다.

 

BST의 규칙

• 왼쪽 서브트리에는 현재 노드보다 작은 값만 존재
• 오른쪽 서브트리에는 현재 노드보다 큰 값만 존재
• 서브트리도 모두 이진 탐색 트리의 조건을 만족해야 함

이진 트리와 탐색 트리의 차이

항목	이진 트리	이진 탐색 트리
자식 수	최대 2개	최대 2개
값의 정렬	무관	정렬 규칙 존재 (왼쪽 < 루트 < 오른쪽)
사용 목적	표현 구조	탐색 효율성