[알고리즘] 알고리즘 공부 2일차

힙(Heap)과 이진 트리(Binary Tree)는 둘 다 트리 구조를 기반으로 하지만, 그 목적과 특징에서 차이가 있습니다.
아래에 주요 차이점을 정리해 보았습니다.

 

1. 구조적인 차이

• 힙(Heap)

• 완전 이진 트리(Complete Binary Tree)로 구성됩니다.

• 즉, 마지막 레벨을 제외한 모든 레벨이 꽉 차 있으며, 마지막 레벨도 가능한 왼쪽부터 노드가 채워져 있습니다.

• 부모와 자식 간의 우선순위 조건을 만족해야 합니다.

• 최대 힙(Max Heap): 부모 노드의 값이 자식 노드의 값보다 크거나 같다.

• 최소 힙(Min Heap): 부모 노드의 값이 자식 노드의 값보다 작거나 같다.

• 이진 트리(Binary Tree)

• 노드당 자식 노드가 최대 2개인 트리입니다.

• 구조적으로 완전 이진 트리일 수도 있고 아닐 수도 있습니다.

• 이진 탐색 트리(Binary Search Tree, BST)와 같이 특정 조건을 만족하는 경우도 있지만, 일반적으로 특별한 우선순위 조건은 없습니다.

 

2. 사용 목적

• 힙(Heap):

• 주로 **우선순위 큐(Priority Queue)**와 같은 데이터 구조를 구현하는 데 사용됩니다.

• 최댓값 또는 최솟값을 빠르게 찾거나 삭제하는 작업에서 효율적입니다.

• 시간 복잡도:

• 삽입 및 삭제:

• 최댓값/최솟값 조회:

• 이진 트리(Binary Tree):

• 주로 데이터를 정렬하거나 탐색하는 데 사용됩니다.

• 이진 탐색 트리(BST)로 구현되면 정렬된 데이터를 저장하고, 검색, 삽입, 삭제 작업에서 의 시간 복잡도를 가집니다.

• 힙처럼 특정 값(최댓값/최솟값)만 빠르게 찾는 용도는 아님.

 

3. 삽입과 삭제 규칙

• 힙(Heap):

• 삽입 시 항상 마지막 노드 위치에 삽입한 후, 부모와 값을 비교하여 Heapify(재정렬) 과정을 거칩니다.

• 삭제 시 최상위 노드(루트 노드)를 제거하고, 마지막 노드를 루트로 옮긴 후 다시 Heapify합니다.

• 이진 트리(Binary Tree):

• 일반적인 이진 트리는 삽입 위치나 삭제 방법에 대한 엄격한 규칙이 없습니다.

• 이진 탐색 트리(BST)의 경우, 왼쪽 서브트리에는 현재 노드보다 작은 값, 오른쪽 서브트리에는 큰 값을 유지하도록 삽입/삭제합니다.

 

4. 예제

 

힙:

• 최대 힙의 경우:

 

      10

     /  \

    9    8

   / \  / \

  7  6 5  4

 

항상 부모 노드가 자식 노드보다 크거나 같음.

 

이진 탐색 트리:

• 정렬된 형태를 유지:

 

      8

     / \

    3   10

   / \    \

  1   6    14

     / \   /

    4   7 13

 

왼쪽은 작고, 오른쪽은 큼.

 

요약

• 힙: 특정 우선순위를 유지하며, 완전 이진 트리 구조.

• 이진 트리: 일반적인 트리 구조로, 데이터 정렬 및 탐색 목적.

• 이진 탐색 트리는 정렬 조건을 추가로 만족.

• 힙은 이진 탐색 트리가 아님.