[DE 데브코스] 04.13 TIL - Queue, PQ, Tree, Binary Tree, BST, Heap

큐(Queue)

• FIFO의 형태를 가지고 있는 자료구조
• 운영체제의 Ready Queue, TCP 계층에서 송/수신 buffer에 Queue 구조를 사용하는 등 시스템 구성에서 많이 이용
• 특히 서큘라 큐(Circular Queue)의 경우 수신 buffer 구현에 이용하면 좋을 듯 하다.
• Python에서는 from collections import deque로 덱을 이용하여 큐를 쉽게 구현할 수 있다.

 

우선순위 큐(Priority Queue)

• 원소들의 우선순위에 따라 큐에서 빠져나오는 자료구조
• 운영체제의 CPU 스케쥴러 등에서 사용한다.
• Enqueue할 때 우선순위 순서를 유지하도록 정렬하면 Dequeue할 때 해당 순서대로 pop할 수 있을 것이다.
• 연결 리스트를 이용하여 구현하면 시간적 측면에서 유리하다.

 

트리(Tree)

• 트리는 Node와 Edge를 이용하여 데이터의 배치 형태를 추상화한 자료 구조다.
• 마지막으로 위치한 노드를 Leaf Node라고 지칭한다.
• 특정 레벨의 노드보다 상위 레벨의 Node를 Parent Node, 하위 레벨의 Node를 Child Node라고 한다.
• 부모의 부모 이상은 조상 노드, 자식의 자식 이상은 후손 노드라고 한다.
• 루트 노드는 Level 0(혹은 1) 이라고 정의하며, 그 자식 노드로 갈때마다 리프 노드까지 level은 1씩 추가된다.
• 트리의 높이(height)는 최대 수준(level) + 1으로 정의하며, 깊이(depth)라고 한다.
• 노드의 차수(Degree)는 자식의 수를 지칭한다. 리프 노드의 차수는 당연히 0일 것이다.
• Binary Tree는 모든 노드의 차수가 2 이하인 트리를 가리킨다.
• 포화 이진 트리(Full Binary Tree)는 모든 레벨에서 노드들이 모두 채워져 있는 이진 트리다. 높이가 k이고 노드의 개수가 2^k-1인 이진 트리다.
• 완전 이진 트리는 레벨 k-2까지 모든 노드가 2개의 자식을 가진 포화 이진트리를 가리킨다.

 

이진 트리(Binary Tree)

• 이진 트리의 추상적 자료구조 연산에는 size(), depth(), traversal 등이 있다.
• 트리의 Node는 data가 포함되고, left child, right child를 가리키는 포인터가 포함된다.
• size()와 depth()를 구하는 것은 재귀를 이용한 방법으로 쉽게 구할 수 있다.
• 이진 트리의 순회는 깊이 우선 순회, 넓이 우선 순회로 구분된다.
• 깊이 우선 순위에는 중위 순회, 전위 순회, 후위 순회로 구분된다. ( 루트를 전, 중, 후 에서 언제 방문하느냐로 구분 )
• 넓이 우선 순회의 경우, 부모 노드 -> 왼쪽 노드 -> 오른쪽 자식 노드 순서로 방문한다는 것을 기억하자.
• 넓이 우선 순회의 경우, 재귀가 아닌 Queue를 이용해서 방문 처리를 하면 될 것이다.
• depth 구현의 경우 다음과 같이 진행한다.

class Node:

    def __init__(self, item):
        self.data = item
        self.left = None
        self.right = None


    def size(self):
        l = self.left.size() if self.left else 0
        r = self.right.size() if self.right else 0
        return l + r + 1


    def depth(self):
        l = self.left.depth() if self.left else 0
        r = self.right.depth() if self.right else 0
        return max(l,r)+1

class BinaryTree:

    def __init__(self, r):
        self.root = r

    def size(self):
        if self.root:
            return self.root.size()
        else:
            return 0


    def depth(self):
        if self.root:
            return self.root.depth()
        else:
            return 0

• 각 Node class에 size, depth method를 구현하였으며, BinaryTree Class의 size, depth는 root node에서만 동작할 수 있게 구현했다. ( 루트 노드에서 시작해야 트리 전체의 사이즈, 높이를 구할 수 있기 때문이다. )
• 어차피 size나 depth의 재귀적 실행의 경우, 노드 클래스에서 재귀가 돌아갈 수 있도록 구현하면 된다.

 

이진 탐색 트리(Binary Search Tree)

• 이진 탐색 트리는 모든 노드에 대해서, 왼쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 작고,
• 오른쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 큰 성질을 만족하는 이진 트리를 가리킨다.
• 항상 O(log n)의 탐색 시간 복잡도를 가지지는 않는다.
• 삽입의 경우 다음과 같이 재귀를 이용하여 구현한다.

    def insert(self, key, data):
        if key == self.key:
            raise KeyError
        else:
            if key < self.key:
                if self.left:
                    self.left.insert(key, data)
                else:
                    self.left = Node(key, data)
            elif key > self.key:
                if self.right:
                    self.right.insert(key, data)
                else:
                    self.right = Node(key, data)

 

Heap

• Heap은 이진 트리의 한 종류다.
• (1) 루트 노드가 언제나 최대값(max heap) 혹은 최소값(min heap)을 가진다.
• (2) 완전 이진 트리여야 한다.
• (3) 재귀적으로도 정의된다. ( 어느 노드를 루트로 하는 서브트리도 모두 최대 or 최소 heap이다. )
• Python에서는 heapq 모듈로 특정한 리스트를 최소 힙처럼 사용할 수 있다. heapq의 사용법은 다음과 같다.

import heapq

heap = [] # heap용 리스트

heapq.heappush(heap, 4) # heap push
heapq.heappush(heap, 1)
heapq.heappush(heap, 7)
heapq.heappush(heap, 3)
print(heap) # [1,3,7,4]

# heappush, heappop : O(log(n))
heapq.heappop(heap) # [3,7,4] # 힙 루트노드 삭제

#최소값 삭제하지 않고 얻기(Peak처럼)
print(heap[0]) # 3

#기존 리스트를 힙으로 변환
heapq.heapify(heap)

#최대 힙 사용법

nums = [4,1,7,3,8,5]
heap = []

for num in nums:
	heap.heappush(heap, (-num, num)) # 우선순위, 값
    
while heap:
	print(heap.heappop(heap)[1]) # index 1

 

 

오늘 공부하며 어려웠던 내용

• 어려웠던 내용은 딱히 없었다.
• 옛날 생각이 많이 났다. 예전 2학년 자료구조 시간에 C++로 트리 구조 짜고, 프리오더+인오더+포스트오더 함수를 구현하여 과제로 제출했던 기억이 났다. C++로 한 번 짜본 덕분에 파이썬으로 함수를 짜는건 익숙했다.