힙(Heap)

• 목적: 힙은 최대값 또는 최소값을 빠르게 찾기 위해 설계된 구조입니다. 따라서 최대 힙에서는 루트 노드가 가장 큰 값을, 최소 힙에서는 루트 노드가 가장 작은 값을 가집니다.
• 속성: 힙은 완전 이진 트리의 형태를 가지며, 각 노드는 자신의 자식 노드보다 크거나(최대 힙의 경우) 작거나(최소 힙의 경우) 같습니다. 이러한 속성은 힙 전체에 걸쳐 유지됩니다.
• 중복 허용 여부 : 중복 허용
• 삽입 및 삭제: 새로운 요소가 추가될 때, 힙은 먼저 완전 이진 트리를 유지하는 형태로 요소를 추가한 다음, 힙 속성을 만족시키기 위해 상향 조정(up-heap) 또는 하향 조정(down-heap) 과정을 거칩니다.
• 용도: 우선순위 큐 구현, 힙 정렬 등에 사용됩니다.

이진 탐색 트리(Binary Search Tree, BST)

• 목적: 이진 탐색 트리는 데이터를 정렬된 순서로 저장하고 관리하기 위해 설계되었습니다. 이를 통해 효율적인 검색, 삽입, 삭제 작업을 수행할 수 있습니다.
• 속성: BST에서는 각 노드가 유일한 키를 가지며, 모든 노드는 다음과 같은 이진 탐색 속성을 만족합니다: 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 해당 노드의 키보다 작고, 오른쪽 서브트리에 있는 모든 노드의 키는 해당 노드의 키보다 큽니다.
• 중복 허용 여부 : 중복을 허용하지 않음
• 삽입 및 삭제: 새로운 요소가 추가되거나 삭제될 때, BST는 이진 탐색 속성을 유지하도록 요소를 추가하거나 제거합니다. 이 과정에서 트리의 구조가 변경될 수 있으며, 경우에 따라 트리의 균형을 재조정하기 위한 작업이 필요할 수 있습니다.
• 용도: 데이터베이스 인덱스, 탐색 알고리즘 등에 사용됩니다.