트리3

• 

  힙 정렬(Heap Sort), 병합 정렬(Merge Sort), 퀵 정렬(Quick Sort) 이번에는 정렬 중에서도 시간 복잡도가 조금 더 빠른 정렬들을 가지고 왔습니다. 힙 정렬, 병합 정렬, 퀵 정렬이렇게 총 3가지 정렬을 설명 드리겠습니다. 힙 정렬(Heap Sort)- 아래의 링크에 있는 힙에 대해 공부하고 오면 이해하기 매우 편하십니다.https://naknak.tistory.com/123 힙(Heap)과 이진탐색트리(Binary Search Tree)힙(Heap)- 트리구조 중 하나로 우선순위 큐를 구현할 때 사용됩니다. (다익스트라에서도 사용됨.)- 우선순위 큐의 특징 : 데이터를 자유롭게 추가 가능, 꺼낼 때는 가장 작은 데이터를 꺼냅니다. -naknak.tistory.com  - 힙은 트리 형태의 구조로, 우선순위 큐를 구현하는데 주로 사용됩니다.- 보통의 힙은 꺼낼 때 가장 작.. CS 지식/자료구조_알고리즘 2025. 1. 12.

• 

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

• Tree Tree Tree(트리) 데이터들을 나무를 뒤집은 형태로 저장한다. 부모와 자식 노드들로 이루어진다. 차수 : 어떠한 노드가 가지고 있는 자식 노드들의 개수 이진 트리 : 차수가 2인 트리 ex) 인덱스 트리 : 자식 노드들의 구간 합이 부모 노드에 저장된 값 정렬 상태를 유지할 수 있다. Heap 구조의 트리이다. (저장된 값 중 최소/최대 값을 리턴하고, 나머지를 정렬하여 저장한다.) 시간복잡도 : 트리의 높이만큼 걸린다. O(Log(N)) KEY WORD : 이진 트리, 노드, 부모 노드, 자식 노드, O(Log(N)) CS 지식/자료구조_알고리즘 2022. 6. 24.