CS/자료구조 (2) 썸네일형 리스트형 [자료구조] 트리(Tree) 트리(Tree) 계층적인 구조를 표현할 때 사용 루트 노드 : 부모가 없는 최상위 노드 단말 노드 : 자식이 없는 노드 크기 : 트리에 포함된 모든 노드의 개수 깊이 : 루트 노드부터의 거리 높이 : 깊이 중 최댓값 차수 : 각 노드의 간선 개수 트리의 크기가 N일 때, 전체 간선의 개수는 N - 1개 이진 탐색이 동작에 효율적임 이진 탐색 트리의 특징 : 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드 (부모 노드보다 왼쪽 자식 노드가 작음, 부모 노드보다 오른쪽 자식 노드가 큼) 트리 순회 방법 전위 순회 : 루트 먼저 방문 중위 순회 : 왼쪽 자식 방문 뒤 루트 방문 후위 순회 : 왼쪽 - 오른쪽 - 루트 class Node: def __init__(self, data, left_node, ri.. [자료구조] 우선순위 큐(Priority Queue)와 힙(Heap) 우선순위 큐(Priority Queue) 우선순위 큐 : 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조 - 데이터를 우선순위에 따라 처리하고 싶을 때 사용 자료구조 추출되는 데이터 스택(Stack) 가장 나중에 삽입된 데이터 큐(Queue) 가장 먼저 삽입된 데이터 우선순위 큐(Priority Queue) 가장 우선순위가 높은 데이터 우선순위 큐(Priority Queue) 구현 방법 - 리스트 이용하여 구현 - 힙(heap)을 이용하여 구현 - 데이터의 개수가 N개일 때, 구현 방식에 따른 시간 복잡도 우선순위 큐 구현 방법 삽입 시간 삭제 시간 리스트 O(1) O(N) 힙(Heap) O(logN) O(logN) N개의 데이터를 힙에 넣었다가 모두 꺼내는 작업은 정렬과 동일 (힙 정렬) _.. 이전 1 다음
