이진탐색트리1

• 

  힙(Heap)과 이진탐색트리(Binary Search Tree) 힙(Heap)- 트리구조 중 하나로 우선순위 큐를 구현할 때 사용됩니다. (다익스트라에서도 사용됨.)- 우선순위 큐의 특징 : 데이터를 자유롭게 추가 가능, 꺼낼 때는 가장 작은 데이터를 꺼냅니다. - 힙은 노드들로 구성되어 있습니다.각각의 노드들은 부모와 자식으로 이루어져 있고, 부모는 최대 2개의 자식 노드를 가질 수 있습니다.- 부모 노드의 데이터가 자식 노드의 데이터보다 항상 작아야합니다. ex) 새로운 수를 힙에 추가하는 예시.1) 새로운 숫자를 힙의 가장 끝에 추가합니다.2) 만약 부모 노드가 존재한다면, 부모 노드와 데이터를 비교 후 숫자가 더 작다면 그 둘의 위치를 바꿔줍니다.3) 계속 그렇게 해서, 더 이상 부모보다 작지 않을 경우, 정렬은 종료됩니다. ex) 숫자를 하나 꺼낼때의 예시... CS 지식/자료구조_알고리즘 2025. 1. 9.