BST (Binary Search Tree)
속성: 각 노드의 왼쪽 서브트리에는 노드의 값보다 작은 값들이, 오른쪽 서브트리에는 노드의 값보다 큰 값들이 위치합니다.
탐색 유용: BST는 탐색과 정렬에 유용합니다.
시간 복잡도: 일반적으로 O(logn)의 시간 복잡도를 가지지만, 최악의 경우 O(n)이 될 수 있습니다.
균형 유무: 균형이 잡히지 않은 BST는 효율성이 떨어질 수 있습니다. 이를 해결하기 위해 AVL 트리, 레드-블랙 트리 등의 균형 이진 탐색 트리가 사용됩니다.
BST 삭제과정
자녀 없는 경우 그냥 삭제
자녀 하나인 경우 삭제대상의 부모와 삭제대상의 자녀를 연결
자녀 둘인 경우 오른쪽 자녀중에서 가장 큰 대상을 삭제대상과 교체후 삭제
힙 (Heap)
속성: 최소 힙에서는 부모 노드의 값이 자식 노드의 값보다 작거나 같아야 하며, 최대 힙에서는 부모 노드의 값이 자식 노드의 값보다 크거나 같아야 합니다.
최소/최대 값 찾기 유용: 힙은 최소값 또는 최대값을 빠르게 찾는 데 유용합니다.
시간 복잡도:
O(logn)의 시간 복잡도를 가집니다.
완전 이진 트리: 힙은 완전 이진 트리이므로 배열을 사용해 효율적으로 구현할 수 있습니다.
두 자료구조는 각각 다른 목적과 특성을 가지고 있으므로, 사용하는 상황에 따라 적절한 자료구조를 선택해야 합니다.
완전 이진 트리 (Complete Binary Tree)는 다음과 같은 특성을 가집니다
모든 레벨이 꽉 차 있음: 완전 이진 트리의 모든 레벨 (마지막 레벨 제외)은 완전히 채워져 있어야 합니다.
마지막 레벨은 왼쪽부터 채워져 있음: 마지막 레벨의 노드는 왼쪽부터 차례대로 채워져 있어야 합니다.
힙의 삽입과정
마지막 위치에 삽입: 새로운 값을 트리의 가장 마지막 위치에 삽입합니다. 이렇게 하면 완전 이진 트리의 속성이 유지됩니다.
Heapify Up: 삽입된 노드와 그 부모 노드를 비교합니다. 삽입된 노드가 부모 노드보다 작다면, 두 노드의 위치를 바꿉니다. 이 과정을 루트 노드에 도달하거나, 부모 노드가 더 작을 때까지 반복합니다.
최소 힙에서의 삭제 (Deletion)
루트 노드 제거: 루트 노드를 제거합니다. 이 노드가 최소값을 가집니다.
마지막 노드를 루트로 이동: 트리의 가장 마지막 노드 (가장 아래, 가장 오른쪽 노드)를 루트로 이동시킵니다. 이렇게 하면 완전 이진 트리의 속성이 유지됩니다.
Heapify Down: 이동한 루트 노드를 자식 노드와 비교합니다. 루트 노드가 자식 노드보다 크다면, 두 노드의 위치를 바꿉니다. 이 과정을 힙 속성을 만족할 때까지 반복합니다.
공통점
트리 구조: 둘 다 이진 트리를 기반으로 하고 있습니다.
로그 시간 복잡도: 둘 다 삽입과 삭제 연산이 일반적으로
O(logn)의 시간 복잡도를 가집니다.
재귀적 연산: 둘 다 재귀적인 알고리즘을 사용하여 삽입, 삭제, 탐색 등의 연산을 수행합니다.
힙 속성과 BST 속성: 둘 다 특정 속성을 유지하기 위해 설계되었습니다. (힙 속성은 부모-자식 간의 관계, BST 속성은 왼쪽-오른쪽 자식 간의 관계)
차이점
용도: BST는 탐색을 위해 설계되었고, 힙은 우선순위 큐 구현이나 최소/최대 값을 빠르게 찾기 위해 설계되었습니다.
속성: BST는 노드 값의 왼쪽은 더 작고, 오른쪽은 더 크다는 속성을 가지고 있습니다. 힙은 부모가 자식보다 작거나 크다는 속성만을 가집니다.
균형성: BST는 균형을 유지하는 추가적인 알고리즘이 필요할 수 있습니다 (예: AVL, 레드-블랙 트리). 힙은 자연스럽게 완전 이진 트리로 균형을 유지합니다.
구현: 힙은 배열을 통해 효율적으로 구현할 수 있습니다. BST는 일반적으로 노드 기반의 구조로 구현됩니다.
두 자료구조는 각각 다른 문제를 해결하기 위해 설계되었지만, 트리라는 공통의 기반 구조 위에서 다양한 문제에 적용될 수 있습니다.
