Binary Tree는 무엇인가요?

[eunjungL]

.

[PgmJun]

이진 트리란?

이진 트리(Binary Tree)란 모든 노드의 자식 노드를 최대 2개 가지는 트리를 의미

사용 목적

• 데이터 정렬: 데이터를 정렬된 순서로 저장하고 검색하는데에 사용 (ex. DB 인덱스)
• 계층 구조 표현: 상위 노드가 하위 노드를 가리키는 구조이기 때문에 파일 시스템, 조직도 등과 같은 계층적 데이터 구조를 표현하는 데에 사용

종류

포화 이진 트리 (Perfect Binary Tree)

• 설명: 모든 레벨이 완전히 채워진 이진 트리
• 특징: 모든 노드가 2개의 자식 노드를 가지며, 모든 리프 노드가 동일한 레벨에 있다.

완전 이진 트리 (Complete Binary Tree)

• 설명: 마지막 레벨을 제외한 모든 레벨이 완전히 채워진 이진 트리
• 특징: 트리의 균형을 유지하면서 배열이나 힙을 구현할 때 유용하다.

편향 이진 트리 (Skewed Binary Tree)

• 설명: 모든 노드가 한쪽 방향으로만 자식 노드를 가지는 이진 트리
• 특징: 왼쪽 또는 오른쪽으로만 자식이 있는 구조로, 노드가 한쪽 방향으로 편향된다.

정 이진 트리 (Full Binary Tree)

• 설명: 모든 노드가 0개 또는 2개의 자식 노드를 가지는 트리
• 특징: 말단 노드를 제외한 모든 내부 노드는 정확히 2개의 자식 노드를 가진다.

균형 이진 트리 (Balanced Binary Tree)

• 설명: 모든 노드의 왼쪽과 오른쪽 서브트리의 높이 차이가 일정한 범위 내에 있는 트리
• 종류:
  • AVL Tree: 높이 균형을 유지하며, 모든 노드의 서브트리 높이 차이가 1 이하
  • Red-Black Tree: 색상 규칙을 통해 균형을 유지하며, 다양한 균형 조건을 통해 트리의 높이를 보장