알고리즘 코딩테스트 핵심이론 강의 - 이진트리

https://www.youtube.com/watch?v=ebp6xyrArKo&list=PLFgS-xIWwNVX-zm4m6suWC9d7Ua9z7fuT&index=36

📌 이진트리

• 각 노드의 자신 노드(차수)의 개수가 2개 이하로 구성된 트리
• 트리 영역에서 가장 많이 사용

 

◾ 이진트리의 종류

• 편향 이진트리 : 노드들이 한쪽으로 편향되어 있음
  → 탐색속도 저하, 공간 낭비 多
• 포화 이진트리 : 트리의 높이가 모두 일정, 리프 노드가 모두 꽉 차 있음
• 완전 이진트리 : 마지막 레벨을 제외하고 노드들이 채워져있고 마지막 레벨은 왼쪽부터 채워진 트리
  → 코딩테스트에서 일반적으로 사용

 

◾ 이진트리의 순차 표현 (배열로 표현)

◾ 배열과 인덱스간의 상관관계

이동 목표 노드인덱스 연산제약조건 (N=노드개수)

루트 노드	index = 1
부모 노드	index = index /2	현재 노드가 투르가 아님
왼쪽 자식 노드	index = index *2	index * 2 <= N
오른쪽 자식 노드	index = index *2 +1	index *2 +1 <=N