이진 트리

• 이진 트리는 각 노드의 자식 노드(차수)의 개수가 2 이하로 구성된 트리를 말한다.
• 트리 영역에서 가장 많이 사용되는 형태

트리가 코딩테스트에서 나오는 유형 2가지

1. 그래프의 표현 → 인접 리스트로 트리를 구성한 후 → BFS,DFS로 문제풀기
2. 1차원 배열 표현 → 인덱스 트리, LCA
   • 여기서 이진트리가 1차원 배열로 표현하는 트리로 사용할 때 쓰는 기본적인 틀
   • 1차원 배열로 표현하려면 무조건 이진 트리여야함
   • 인덱스 트리, LCA도 이진트리로 구성된다.

이진 트리의 핵심 이론

이진 트리의 종류

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

• 데이터를 트리 자료구조에 저장할 때 편향 이진 트리의 형태로 저장하면 탐색 속도가 저하되고 공간이 많이 낭비되는 단점이 있다.
• 일반적으로 코딩 테스트에서 데이터를 트리에 담는다고 하면 완전 이진 트리 형태를 떠올리면 된다.

이진 트리의 순차 표현

• 가장 직관적이면서 편리한 트리 자료구조 형태는 배열

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

출처 - 하루코딩