코린이의 개발 일지

힙이란? → 이진트리의 한 종류 (이진 힙 - binary heap 이라고도 부른다.) 루트 (root) 노드가 언제나 최댓값 또는 최솟값을 가진다. 최대 힙 (max heap) 최소 힙 (min heap) 완전 이진트리여야 함 → 재귀적으로도 정의 된다. (어느 노드를 루트로 하는 서브트리도 모두 최대 힙) → 왼쪽과 오른쪽 자식을 비교하는 기준은 없다. 이러한 개념을 바탕으로 힙 연산을 코드 구현 해보자. 먼저 연산을 정의하자면 init() - 빈 최대 힙을 생성 insert(item) - 새로운 원소를 삽입 remove() - 최대 원소 (root node) 를 반환 (그리고 동시에 이 노드를 삭제) 배열을 이용한 이진 트리의 표현 노드 번호 m을 기준으로 왼쪽 자식의 번호 : 2*m 오른쪽 자식의..

우선 이진 탐색 트리란, 모든 노드에 대해서, 왼쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 작고 오른쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 큰 성질을 만족하는 이진트리 (단, 중복되는 데이터 원소는 없는 것으로 가정) 1. 정렬된 배열을 이용한 이진 탐색과 이진 탐색 트리의 비교 이진 탐색 트리의 장점 데이터 원소의 추가, 삭제가 용이 이진 탐색 트리의 단점 공간 소요가 크다 항상 O(logn)의 탐색 복잡도를 가지는 것이 아니다. 2. 이진 탐색 트리의 추상적 자료구조 데이터 표현 - 각 노드는 (key, value) 의 쌍으로 키를 이용해서 검색 가능 보다 복잡한 데이터 레코드로 확장 가능 연산의 정의 insert (key, data) - 트리에 주어진 데이터 원소를 추가 r..

이진 트리의 추상적 자료구조 연산의 정의 size() - 현재 트리에 포함되어 있는 노드의 수를 구함 depth() - 현재 트리의 깊이를 구함 순회(travelsal) 우선 size와 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 els..

1. 트리(Trees) 트리 (Trees) 란? → node와 edge 를 이용하여 테이터의 배치 형태를 추상화한 자료구조 개념 이해를 위해 적당한 그림을 가져왔다. 위의 그림을 보면 9개의 노드, 8개의 edge Root node = A -> 가장 머리가 되는 노드 Leaf node = H, I, E, F, G -> 가장 끝에 있는 노드, 즉 자식 노드가 없는 노드 Internal node = 그외의 노드 부모 자식 관계 (parent, child) 그리고 같은 부모 아래 child 들은 sibling 관계 부모의 부모 - 조상(ancestor), 자식의 자식 - 후손(descendant) 노드의 level → Root 부터 level 0으로 지정 (그림 참조) 트리의 높이 (Height) = 최대 수..