이진 트리

개념

이진 트리는 각 노드의 자식 노드의 개수가 2개 이하로 구성된 트리

트리 영역에서 가장 많이 사용되는 형태

종류

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

① ① ①

② ② ③ ② ③

③ ④ ⑤ ⑥ ⑦ ④ ⑤

④

⑤

데티러를 트리 자료 구조에 저장할 때 편향 이진 트리의 형태로 저장하면 탐색 속도가 저하되고 공간이 많이 낭비되는 단점이 있다. 일반적으로는 완전 이진 트리 형태(LCA, 인덱스트리)를 사용한다.

이진 트리의 순차 표현

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

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

예시 - 위의 완전 이진 트리

5번 부모 노드 인덱스 → 5/2 = 2

2번 왼쪽 자식 노드 인덱스 → 2 * 2 = 4

2번 오른쪽 자식 노드 인덱스 → 2*2+1 = 5

참고

그냥 하자