[트리] 이진 트리

✔ 이진 트리

이진 트리란?

• 각 노드의 자식 노드의 개수가 2 이하로 구성돼 있는 트리

이진 트리의 종류

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

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

이진 트리의 순차 표현

• 트리 자료 형태는 배열
• 이진 트리는 1차원 배열의 형태로 표현할 수 있음

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

• 루트 노드 : index = 1
• 부모 노드 : index = index / 2
• 왼쪽 자식 노드 : index = index * 2
• 오른쪽 자식 노드 : index = index * 2 + 1

 

Do it! 알고리즘 코딩테스트 with JAVA

https://inf.run/w9Tn