하향식1 Top down Approach 하향식(Top-Down) 방식은 노드가 ✔ ↓ 의 방향으로 먼저 간 다음, ✔ → 의 방향으로 채워진다. 이 두 순서로 노드가 채워지게 된다. 즉 위에서부터 채워나가되, 각 레벨에서의 삽입은 왼쪽에서 오른쪽 순서로 하게 된다. 이러기 위해선 두 가지 조건이 필요하다. 1. 각 노드에 저장된 값이 두 자식 노드에 저장된 값보다 크거나 같아야 한다. 작거나 같다는 조건으로 바꿔도 된다. 크기가 자식 노드보다 크거나 같은 경우를 Max heap이라 하고, 작거나 같은 경우를 Min heap이라고 한다. 2. 트리는 완전 균형 상태여야 하고, 마지막 레벨에 있는 leaf 노드들은 모두 트리의 가장 왼쪽 부분부터 채워져야 한다. 따라서 트리의 높이는 O(log n)이 된다. 이 두 조건은 자료구조 '힙'의 성질이.. 2017. 4. 20. 이전 1 다음