[트리] 이진트리(Binary)

이진 트리

각 노드의 자식의 갯수(차수)가 2 이하로 구성된 트리

 

트리는 기본적으로 그래프의 표현과 일차원 배열 표현으로 나뉜다.

그래프의 표현으로는 인접리스트를 활용한 BFS, DFS탐색 알고리즘 유형이 있으며

1차원 배열 표현으로는 인덱스 트리와 LCA 유형이 있다.

이진트리는 1차원 배열로 표현하는 인덱스 트리, LCA라고 볼 수 있다.

 

종류
편향 이진 트리	포화 이진 트리	완전 이진 트리
노드들이 한쪽으로 편향 돼 생성됨	트리의 높이 모두 일정, 리프노드가 꽉참	마지막 레벨 제외하고 노드들이 완전하게 채워짐, 마지막 레벨은 왼쪽부터 채워짐
ⓐ 　　 　　／ 　　 　  ⓑ 　　    ／ 　 　 ⓒ 　   ／  　ⓓ   ／ ⓔ	ⓐ ∧ ⓑ　ⓒ ∧　  ∧ ⓓ ⓔⓕ ⓖ	ⓐ     　 ∧  　ⓑ　ⓒ 　 ∧   ⓓ ⓔ

 

편향 이진 트리에 저장시 탐색속도 저하 및 많은 공간이 낭비된다.

따라서 일반적인 코딩테스트에서는 완전 이진트리를 사용하여 저장한다

(LCA, Index Tree)

---

순차 표현

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

 

 

트리노드와 배열 인덱스 사이의 상관 관계
이용노드	인덱스연산	제약조건(N=노드갯수)
루트노드	index = 1
부모노드	index = index / 2	현재 루트 노드가 아님
왼쪽 자식노드	index = index * 2	index * 2 ≤ N
으론쪽 자식노드	index = index * 2 + 1	index * 2 + 1 ≤ N