트리 - 이진 트리

이진 트리는 각 노드의 자식 노드(차수)의 개수가 2 이하로 구성되어 있는 트리입니다.

트리의 영역에서 가장 많이 사용되는 형태입니다.

 

이진 트리의 핵심 이론

이진 트리의 종류

이진 트리에는 편향 이진 트리, 포화 이진 트리, 완전 이진 트리가 있습니다.

• 편향 이진 트리: 노드들이 한쪽으로 편향돼 생성된 이진트리
• 포화 이진 트리: 트리의 높이가 모두 일정하며 리프 노드가 꽉 찬 이진 트리
• 완전 이진 트리: 마지막 레벨을 제외하고 완전하게 노드들이 채워져 있고, 마지막 레벨은 왼쪽부터 채워진 트리

데이터를 트리 자료구조에 저장할 때 편향 이진 트리의 형태로 저장하면 탐색 속도가 저하되고 공간이 많이 낭비됩니다.

일반적으로 코딩 테스트에서 트리에 담는다고 하면 완전 이진 트리 형태를 떠올리면 됩니다.

 

이진 트리의 순차 표현

가장 직관적이면서 편리한 트리 자료구조 형태는 바로 '리스트'입니다.

이진 트리는 1차원 리스트의 형태로 표현할 수 있습니다.

 

트리의 노드와 리스트의 인덱스 사이 상관 관계

이동 목표 노드	인덱스 연산	제약 조건(N = 노드 개수)
루트 노드	index = 1
부모 노드	index = index / 2	현재 노드가 루트 노드가 아님
왼쪽 자식 노드	index = index * 2	index * 2 <= N
오른쪽 자식 노드	index = index * 2 + 1	index * 2 +1 <= N

 

위의 인덱스 연산 방식은 향후 세그먼트 트리나 LCA 알고리즘에서도 기본이 되는 연산입니다.