완전 이진 트리

 

https://www.acmicpc.net/problem/9934

 

자식 노드의 인덱스

부모 노드의 인덱스를 i라고 할 때,

1. 왼쪽 자식의 인덱스 : 2i + 1

2. 오른쪽 자식의 인덱스 : 2i + 2

 

부모 노드의 인덱스

자식 노드의 인덱스를 i라고 할 때

1. 부모의 인덱스 : ⌊(i - 1) / 2⌋

 소수점은 버린다.

 

높이가 k개 일 때 노드의 개수

2^(k + 1) - 1

 

완전 이진트리의 노드가 n 개일 때 높이

h=⌊log2​(n)⌋