zzugest1

최대 힙에서의 삭제 연산은 제일 큰 값인 루트 노드 삭제 연산만 존재한다. 방법은 다음과 같다. 위와 같은 트리가 있을 때 루트 노드 20을 삭제한다고 가정하면 트리의 가장 마지막 노드인 4를 루트 노드와 맞바꾼다. 4의 자식 노드인 6과 12를 비교했을 때 더 큰 값을 가지는 쪽과 맞바꾼다. 그럼 최대힙의 성질을 만족 할 수 있다. 이러한 삭제 연산 또한 삽입 연산의 시간복잡도와 같은 O(logn)이다. 이를 구현한 코드는 다음과 같다. class MaxHeap: def __init__(self): self.data = [None] def remove(self): if len(self.data) > 1: self.data[1], self.data[-1] = self.data[-1], self.data[..

힙이란 이진 트리의 한 종류로 루트 노드가 언제나 최댓값 또는 최솟값을 가지는 완전 이진 트리이다. 또한 어느 노드를 루트 노드로 하는 서브트리도 모두 최대 힙이여야 한다. (재귀적으로도 정의됨) 이진 탐색 트리와 최대힙을 비교하자면 이진 탐색 트리에서는 원소들이 완전히 크기 순서대로 정렬되어 있다. 따라서 중위 순회를 하면 데이터를 정렬된 순서로 뽑아낼 수 있다. 하지만 최대 힙은 완전히 크기 순서대로 정렬되어 있지는 않다. 따라서 트리를 순회함으로써 데이터를 정렬할 수는 없다. 또한, 이진 탐색 트리에서는 루트 노드로부터 시작하여 특정 원소를 빠르게 검색할 수 있는 반면, 최대 힙은 이러한 탐색 연산을 제공할 수 없다는 특징이 있다. 최대 힙은 완전 이진 트리여야 한다는 조건이 있기 때문에 데이터 원..

이진 탐색 트리란 모든 노드에 대해서(중복되는 데이터 원소는 없는 것으로 가정) - 왼쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 작고 - 오른쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 큰 두 성질을 만족하는 이진 트리이다. 그 중 삭제 연산은 다음과 같이 실행된다 키 (key)를 이용해서 노드를 찾는데 해당 키의 노드가 없으면 삭제할 것이 없는 경우고, 만약 존재한다면 그 노드를 제거하고도 이진 탐색 트리 성질을 만족하도록 트리의 구조를 정리해야한다. 삭제되는 노드가 다음 세가지 경우로 나뉜다. 1. 리프 노드인 경우 2. 자식을 하나 가지고 있는 경우 3. 자식을 둘 가지고 있는 경우 먼저 삭제되는 노드가 리프 노드인 경우부터 살펴보면 이 경우는 그냥 그 노드를 없애면 된다. 위 ..

이진 탐색 트리란 모든 노드에 대해서(중복되는 데이터 원소는 없는 것으로 가정) - 왼쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 작고 - 오른쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 큰 두 성질을 만족하는 이진 트리이다. 이진 트리의 예시로 다음과 같이 들 수 있다. 루트 노드 5를 기준으로 했을 때 왼쪽 서브트리는 모두 5보다 작고, 오른쪽 서브트리는 모두 5보다 크다. 이러한 성질 덕분에 트리안에 특정 원소를 찾는 과정이 매우 쉬워진다. 만약 6을 찾는다고 가정하면 6은 루트노드 5보다 크므로 오른쪽으로, 그 다음 8보다 작으므로 왼쪽으로 가기만 하면 된다. 배열을 이용한 이진 탐색과 비슷한 원리를 가지고 있다. 이진 탐색 트리의 탐색 과정 또한 시간 복잡도가 O(logn)이 ..

이진 트리의 순회 연산에는 깊이, 넓이 우선 순회 연산이 있다. 이번엔 넓이 우선 순회 연산에 대해 소개하겠다. 넓이 우선 순회의 원칙 수준(Level)이 낮은 노드를 우선으로 방문 같은 수준의 노드들 사이에는 부모 노드의 방문 순서에 따라 방문하고, 왼쪽 자식노드를 오른쪽 자식노드보다 먼저 방문한다. 그림으로 표현하면 다음과 같다. 쉽게 설명하면 같은 수준의 노드를 왼쪽부터 아래로 순회한다고 보면 된다. 위 트리의 순회 순서는 알파벳순으로 A~I가 된다. 이러한 알고리즘을 코드로 구현하기 위한 설계는 큐를 이용해 설명할 수 있다. 1. 맨 처음 루트 노드 A를 읽고 자식노드 B,C를 왼쪽 노드부터 빈 큐에 enqueue()한다. 2. 다음 B 노드를 읽을 때 B를 큐에서 dequeue()하고 순회 리스..

이진 트리란 트리에 포함되는 모든 노드의 차수가 2이하인 트리를 말한다. 이진 트리를 추상적 자료구조로 구현하기 위한 연산에는 세 가지가 있다. size() : 현재 트리에 포함되어 있는 노드의 수를 구함 depth() : 현재 트리의 깊이(또는 높이)를 구함 traversal() : 트리의 각 노드를 정해진 순서로 방문하는 연산 이진 트리를 구현하기 위한 코드는 다음과 같다. class Node: # 빈 노드 생성 def __init__(self, item): self.data = item self.left = None self.right = None class BinaryTree: # 이진 트리의 루트 노드 생성 def __init__(self, r): self.root = r size() 연산을 구..

트리란 정점(Node)와 간선(edge)를 이용하여 데이터의 배치 형태를 추상화한 자료구조를 말한다. 위 트리는 10개의 노드와 9개의 간선을 가진다. 트리에 대한 용어들을 정리하자면 루트(Root) 노드 : 트리의 맨 위에 있는 시작점 노드를 뜻한다. 위 트리에서 루트 노드는 A이다. 리프(Leaf) 노드 : 더 이상 아래로 간선을 가지지 않는 트리의 맨 아래에 있는 노드를 뜻한다. 위 트리에서 리프 노드는 G,H,I,E,J이다. 내부(Internal) 노드 : 루트, 리프 노드가 아닌 중간에 있는 노드를 뜻한다. 위 트리에서 내부 노드는 B,C,D,F이다. 부모,자식 노드 : 한 간선으로 연결된 두 노드를 기준으로 위에 있는 노드를 부모 노드, 아래에 있는 노드를 자식 노드라고 한다. 노드 D는 G,..

우선순위 큐란 기존의 선입선출의 특성을 따르지 않고, 원소들의 우선순위에 따라 큐에서 빠져나오는 방식을 가진 큐이다. 큐의 원소가 3,6,8,5로 무작위 순서로 구성되있을 우선순위를 숫자가 작은 원소가 먼저 빠져나온다 가정하면 3,5,6,8 식으로 빠져나올 것이다. 우선순위 큐를 구현할 때 두가지 경우가 가능한데 1. enqueue할 때 우선순위를 유지하도록 2. dequeue할 때 우선순위 높은 것을 선택하도록 이 두 방법 중 시간적 측면에서 유리한 방법은 첫번째이다. 그 이유는 두번 째 경우는 삭제할 원소를 찾으려면 모든 원소를 들여다봐야하기 때문에 큐의 길이에 비례하는 시간을 가진다. 하지만 첫번 째 경우는 삽입 시 모든 원소를 들여다볼 필요는 없기 때문에 조금 더 유리하다. 큐를 구현할 때 배열 ..

환형 큐란 정해진 개수의 저장 공간을 원형으로 돌려가며 사용하는 큐이다. 그림과 같은 환형큐가 있고, 시작점이 A 위치일 때 enqueue(A)를 하면 위와 같이 삽입이 된다. 그 후 위와 같은 방향으로 enqueue(B),enqueue(C)를 하면 B,C가 삽입이 된다. 큐의 삭제 연산 dequeue()를 실행하면 먼저 삽입된 A는 삭제될 것이다. 그 후 연산으로 위와 같은 그림이 되었을 때 데이터를 삽입하는 부분은 rear, 데이터를 꺼내는 부분은 front라는 포인터를 가진다. 환형 큐는 정해진 개수의 저장 공간을 이용하므로 큐가 가득 차있다면 삽입 연산을 실행할 수 없다. 이러한 특성이 반영된 환형 큐의 핵심 연산은 다음과 같다. size() : 큐에 들어 있는 원소 개수 추출 isEmpty() ..

큐란 자료를 보관할 수 있는 선형구조이며, 단 데이터를 넣을때에는 한 쪽 끝에서 밀어 넣어야하고 꺼낼 때에는 반대쪽에서 꺼내야 하는 제약이 있다. 이러한 특성을 선입선출(first-in first-out)이라 한다. 그림을 통해 설명하면 위와 같이 아래쪽 방향으로 A를 집어넣으면 앞으로 데이터는 같은 방향으로만 넣을 수 있다. 다음 B를 넣으면 위와 같이 A위에 위치하게 된다. 이러한 큐의 삽입 연산을 enqueue()라고 한다. 데이터를 삭제하면 먼저 삽입된 A가 먼저 삭제되고 기존 A의 위치에는 B가 자리잡게 된다. 즉 큐에서 데이터가 삭제되면 맨 앞 데이터가 삭제되고 나머지 데이터는 한 칸씩 앞으로 가게된다. 이러한 큐의 삭제 연산을 dequeue()라고 한다. 큐의 핵심연산은 5가지가 있다. si..