cs/자료구조37 [Heap]28. Heap(힙) 목차 1. Heap(힙) 2. Height of a Heap(힙의 높이) 3. Heaps and Priority Queues(힙과 우선순위 큐) 1. Heap(힙) Heap(힙)은 특정한 규칙를 따르고 있는 binary tree입니다. 이 특정한 규칙은, 1) Heap-Order - 모든 internal node v에 대하여, 자식의 key값이 부모의 key값보다 항상 크거나 같아야 한다. - (단, root 제외) - key(v) >= key(parent(v)) 2) Complete Binary Tree - 이전에도 언급하였으나, heap은 complete binary tree를 따라야 한다. - 이는 모든 레벨의 node가 가득 차있어야 하며, 마지막 레벨의 node는 왼쪽으로 치우쳐있는 binary.. 2021. 2. 26. [Priority Queue]27. Priority Queue Sorting(우선순위 큐 정렬) 목차 1. Priority Queue Sorting(우선순위 큐 정렬) 2. Selection Sort 3. Insertion Sort 4. In-place Insertion Sort 1. Priority Queue Sorting(우선순위 큐 정렬) Priority Queue(우선순위 큐)가 중요한 내용을 먼저 꺼내는 ADT이니 만큼, PQ ADT는 들어온 데이터들을 key 값을 기준으로 정렬을 해야합니다. 이를 Priority Queue Sorting이라고 하며, 이를 구현할 수 있는 방법은 다양합니다. 2. Selection Sort Selection Sort(선택정렬)은 PQ-sort의 일종으로, 해당 priority queue가 정렬되지 않는 sequence와 연결되어 있는 구조를 뜻합니다. Se.. 2021. 2. 26. [Priority Queue]26. Priority Queue(우선순위 큐) 목차 1. Priority Queue ADT(우선순위 큐) 2. minPQ, maxPQ 1. Priority Queue ADT(우선순위 큐) 1) 특징 - Priority Queue ADT(우선순위 큐)는 queue의 성질을 따르지만, 필요한, 그리고 중요한 내용을 먼저 꺼내는 방식을 말합니다. 2) 주요 기능 - insert(e): e라는 element를 insert하는 함수 - removeMin(): 가장 작은 key를 지닌 값을 제거하는 함수 3) 부가 기능 - min(): 가장 작은 key를 지닌 값을 반환, 제거하지는 않는다 - size(), empty() 2. minPQ, maxPQ Priority Queue는 크게 2가지로 나뉘는데, minPQ와 maxPQ로 나뉘어집니다. 이름에서 추측할 수.. 2021. 2. 26. [Trees]25. Binary Trees Traversal(이진 트리 탐색) 목차 1. Inorder Traversal(중위 순회) 2. Print Arithmetic Expressions 3. Evaluate Arithmetic Expressions 2. Euler Tour Traversal(오일러 탐색) 1. Inorder Traversal(중위 순회) Inorder Traversal(중위 순회)는 해당 node가 external이 아니라면, 1) 왼쪽 자식의 node를 방문한 후 2) 현재 node를 print 3) 그 후 오른쪽 자식의 node를 방문함 위의 과정을 거치는 방법을 말합니다. 이는 실제로 이진 탐색 트리를 그리는 경우, 활용될 수 있습니다. - x(v) = inorder traversal 순위 - y(v) = node v의 높이 2. Print Arithme.. 2021. 2. 25. [Trees]24. Binary Trees(이진 트리) 목차 1. Binary Trees(이진 트리) 2. Arithmetic Expression Tree 3. Decision Tree 4. 이진 트리의 종류 1. Binary Trees(이진 트리) Binary tree(이진 트리)는 다음과 같은 특징들을 따르는 tree를 말합니다. 1) 각각의 internal node는 최대 두개의 children을 지닌다(proper binary tree를 위해서는 정확히 2개) 2) node의 children은 ordered pair이다. 따라서 root 한개만 보유하고 있는 tree, 혹은 하나의 root와 root의 자식 2개로 이루어져 있는 tree도 binary tree의 일종이라고 할 수 있습니다. 2. Arithmetic Expression Tree 일반적인.. 2021. 2. 25. [Trees]23. Tree Traversal(트리 순회) 구현 목차 1. class Node, class Tree 2. def pre_order, def post_order 3. main 4. 예상 출력 1. class Node, class Tree class Node, class Tree는 전 게시물 21번에 구현한 것을 사용합니다. imgzon.tistory.com/62 [Trees]21. Tree 구현 목차 1. class Node 2. class Tree 3. def insert_node 4. def del_node 5. def print_chi 6. def print_sib 7. __main__ 8. 예상 입력, 출력 1. class Node class Node: def __init__(self, e: object): self.ele.. imgzon.tis.. 2021. 2. 25. [Trees]22. Tree Traversal(트리 순회 모음) 목차 1. Recursion(재귀) 1. Preorder Traversal(전위 순회) 2. Postorder Traversal(후위 순회) 1. Recursion(재귀) Recursion(재귀)는 자신을 정의할 때, 자기 자신(함수)를 재참조하는 방법을 말합니다. 재귀 함수는 함수를 정의할 때 자기 자신이 포함되며, 따라서 재귀 함수 설계시, 무한 루프에 빠지지 않도록 주의가 필요합니다. 2. Preorder Traversal(전위 순회) Node들의 관계로 이루어져 있는 Tree를 탐색하기 위해서는, 트리의 node들을 체계적인 방법으로 방문해야 합니다. 그 중에서 자신을 우선 방문하고, 자식 node들을 순차적으로 방문하는 방식을 Preorder Traversal(전위 순회)라고 합니다. 3. Po.. 2021. 2. 25. [Trees]21. Tree 구현 목차 1. class Node 2. class Tree 3. def insert_node 4. def del_node 5. def print_chi 6. def print_sib 7. __main__ 8. 예상 입력, 출력 1. class Node class Node: def __init__(self, e: object): self.element = e self.parent = None self.child = [] def insert_child(self, n): # 해당 node에 자식을 삽입할 때 사용하는 함수 self.child.append(n) def del_child(self, n): # 현재 node의 자식 node 중 특정 node를 제거 for i in self.child: if i==n: .. 2021. 2. 25. 이전 1 2 3 4 5 다음
