자료 구조

트리(Trees)

2023.03.28

정점(node) 과 간선(edge)을 이용하여 데이터의 배치 형태를 추상화한 자료 구조 루트(root) 노드 리프(Leaf) 노드 부모(Parent) 노드와 자식(Child) 노드 노드의 수준(level) 트리의 높이(Height) = 최대수준(level) + 1, 깊이(depth) 라고도 함 부분 트리(서브 트리 - Subtree) 노드의 차수(Degree) - 자식(서브트리)의 수 이진 트리(Binary Tree) 모든 노드의 차수가 2 이하인 트리 재귀적으로 정의할 수 있음 루트 노드 + 왼쪽 서브 트리 + 오른쪽 서브트리(단, 이 떄 왼쪽과 오른쪽 서브트리 또한 이진 트리) 포화 이진 트리(Full Binary Tree) 모든 레벨에서 노드들이 모두 채워져 있는 이진 트리(높이가 k이고 노드의 개..

카테고리 없음

우선순위 큐(Priority Queue)

2023.03.28

우선순위 큐(Priority Queue) 큐가 FIFO(First In First Out) 방식을 따르지 않고 원소들의 우선순위에 따라 큐에서 빠져나오는 방식 활용 운영체제의 CPU 스케줄러 구현방식 Enqueue 할 때 우선순위 순서를 유지하도록 -> 이쪽이 약간 더 유리함 Dequeue 할 때 우선순위 높은 것을 선택 양방향 연결리스트를 이용한 우선순위 큐 구현 class Node: def __init__(self, item): self.data = item self.prev = None self.next = None class DoublyLinkedList: def __init__(self): self.nodeCount = 0 self.head = Node(None) self.tail = Node(..

트리(Trees)

우선순위 큐(Priority Queue)

티스토리툴바