이진 탐색 트리 이진 탐색 트리란? - 모든 노드에 대해서 왼쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 작고 - 오른쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 큰 성질을 만족하는 이진트리 - 이진 탐색 알고리즘과 비슷함 (이진 탐색 알고리즘 : 이미 정렬된 선형 배열을 대상으로 절반씩 잘라가면서 찾고자 하는 원소를 탐색) - 중복 데이터(원소) 는 없는 것으로 가정 이진 탐색 트리 삽입 연산 구현해 보기 - 연산의 정의 insert(key, data) - 트리에 주어진 데이터 원소를 추가 remove(key) - 특정 원소를 트리로부터 삭제 lookup(key - 특정 원소를 검색 (Ologn) inorder() - 키의 순서대로 데이터 원소를 나열 min(), max() - 최대,..
이진 트리의 넓이 우선 순회 넓이 우선 순회(Breadth First Trabersal) 원칙 - 수준(level)이 낮은 노드를 우선으로 방문 - 같은 수준의 노드들 사이에는, 부모 노드의 방문 순서에 따라 방문, 왼쪽을 먼저 방문 한 노드를 방문했을 때, 나중에 방문할 노드(자식노드) 순서를 기록해 둬야 함 (큐를 이용해야 함) 넓이 우선 순회 알고리즘 구현해보기 알고리즘 순서 1. traversal에 빈 리스트, q에 빈 큐를 초기화 2. 빈 트리가 아니면, root node를 큐에 추가 (enqueue) 3. q가 비어 있지 않는 동안 3.1. q에서 원소를 추출 및 node에 저장 (dequeue) 3.2. node를 방문처리 (traversal에 append) 3.3. node의 왼쪽, 오른쪽..
트리(trees) 트리란? - 정점(node)과 간선(edge)을 이용하여 데이터의 배치 형태를 추상화한 자료 구조 - 최상단은 root node, 최 하단은 leaf node, 중간에는 내부 노드(internal nodes)라고 부름 이진 트리(Bynary Trees) 연산의 정의 size() - 현재 트리에 포함되어 있는 노드의 수를 구함 depth() - 현재 트리의 깊이 (또는 높이; height)를 구함 traversal - 순회 넓이 우선 순회 (breadth first traversal) 깊이 우선 순회 (depth first traversal) - 중위 순회 : left subtree -> 자기 자신 -> right subtree - 전위 순회 : 자기 자신 -> Left subtree -..
우선순위 큐(Priority Queues) 특징 - 큐가 FIFO 방식을 따르지 않고 원소들의 우선순위에 따라 큐에서 빠져나오는 방식 - 대표적으로 운영체제의 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..
환형 큐 - 정해진 개수의 저장 공간을 빙 돌려가며 이용하는 자료구조 - 큐가 가득 차면 더 이상 원소를 넣을 수 없음 (큐 길이를 기억해 활용해야 함) - 저장 공간을 한정하여 공간 낭비를 줄일 수 있음 환형 큐 구현해보기 - 연산의 정의 size() - 현재 큐에 들어 있는 데이터 원소 수 구하기 isEmpty() - 현재 큐가 비어 있는지 판단 isFull() - 큐에 데이터 원소가 꽉 차 있는지를 판단 enqueue(x) - 데이터 원소 x를 큐에 추가 dequeue() - 큐의 맨 앞에 저장된 데이터 원소 제거 (또한, 반환) peek() - 큐 맨 앞의 저장된 데이터 원소 반환 (제거x) class CircularQueue: def __init__(self, n): self.maxCount =..
큐 (Queues) - 선입선출(Firts In First Out) 특징을 가지는 선형 자료구조 (ex.영화관에서 줄서기) 큐의 활용 - 자료를 생성 및 이용하는 작업이 비동기적(asynchronously)으로 일어나는 경우 - 자료를 생성하는 작업이 여러 곳에서 일어나는 경우 - 자료를 처리하여 새로운 자료 생성 후 나중에 해당 자료를 또 처리해야 하는 작업의 경우 양방향 연결 리스트를 이용해 큐 구현해보기 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 = Nod..
