트리2 [C++/자료구조] 힙(Heap) Heap : 힙 - 특징 1) 완전 이진 트리 형태 2) 부모 노드와 자식 노드 간의 대소관계가 정해진 완전 이진 트리 구조 3) 루트 노드는 항상 최솟값 또는 최대값을 가진다 4) 최소 힙 또는 최대 힙이 있다. - 최소 힙 : 부모 노드의 값이 자식 노드의 값보다 작은 경우 - 최대 힙 : 부모 노드의 값이 자식 노드의 값보다 큰 경우 - 장점 1) 최소값 또는 최대값을 상수시간 O(1)에 찾을 수있다. 2) 정렬, 우선순위 큐 등에서 유용하게 사용 3) 이진 탐색 트리보다 간단하고 빠르게 구현할 수 있다. - 단점 1) 중복된 값의 처리가 어렵다. 2) 삽입, 삭제, 연산에 시간 복잡도가 O(log n)이 소모된다. Heap.h #pragma once void DoHeap(); class Heap .. 2023. 7. 15. [C++/자료구조] 이진트리(Binary Tree) Tree : 트리 - 특징 1) 루트 노드를 제외한 모든 노드는 부모 노드가 있다 2) 하나의 루트 노드를 가진다 3) 노드는 0개 이상의 자식 노드를 가진다 4) 순환 구조를 가지지 않는다 - 장점 1) 계층적인 구조를 표현할 수 있으며, 검색과 삽입, 삭제가 용이하다 - 단점 1) 불균형한 트리는 탐색 시간이 느려진다 Complete Binary Tree : 완전 이진 트리 - 특징 1) 모든 노드가 꽉 찬 이진 트리 2) 마지막 레벨을 제외한 모든 레벨이 꽉 차있어야 한다 3) 마지막 레벨은 왼쪽부터 차레로 채워진다 4) 모든 노드는 왼쪽에서 오른쪽으로 채워져야 한다 - 장점 1) 배열로 구현할 때 간단하게 구현할 수 있다 - i번째 노드의 왼쪽 자식 노드는 2i 번째 노드 - i번째 노드의 오른쪽.. 2023. 7. 8. 이전 1 다음
