99클럽 코테 스터디 15일차 TIL 포화이진트리

Java 자주 쓰이는 포화이진트리 수식

DFS나 BFS 문제를 풀면 포화이진트리(perfect binary tree)를 자주 볼 수 있다.

알아두면 좋은 수식을 정리해 본다.

 

• 포화이진트리(perfect binary tree)란?
  
  • 모든 노드가 꽉 찬 이진트리를 말한다.
  • node = [0, 1, 2, 3, 4, 5, 6];
  • 노드의 개수 : n = node.length;

포화이진트리 (perfect binary tree)

• level까지의 노드의 총 개수
  • 2  ^ (level + 1) - 1
• level의 노드의 개수
  • 2 ^ level
• 노드의 개수가 n 일 때, 몇 level까지 존재하는가
  • Math.log()가 double이기 때문에 오차가 존재할 것이므로 완벽한 답은 아닙니다.

int getLevel(int n) {
    return (int) (Math.log(n - 1) / Math.log(2));
}

log 계산

• level 별 index 범위
  • startIndex = 2 ^ (level + 1) - 2 ^ level - 1
  • endIndex = 2 ^ (level + 1) - 2
• node[index] 의 left 노드와 right 노드
  • left = node[index * 2 + 1]; (단, index * 2 + 1 > n 이면 null)
  • right = node[index * 2 + 2]; (단, index * 2 + 2 > n 이면 null)

728x90

느낀 점

• 위 수식들을 외워 놓으면 시간을 절약할 수 있을 것이다.

다음에 학습할 것

• 포화이진트리 구현하기

반응형

---

포화이진트리에서 많이 쓰이는 수식에 대해 알아보았다.