걸어가는 개발자

Binary Tree 아래 두가지를 만족하는 트리 1) 어떠한 노드를 기준으로 왼쪽은 기준이 되는 노드보다 전부다 작아야된다. 2) 어떠한 노드를 기준으로 오른쪽은 기준이 되는 노드보다 전부다 커야된다. 일반 배열에 비해 추가, 제거, 검색의 작업횟수가 크게 줄어든다. Heap은 완전이진트리기 때문에 배열이나 리스트로 구현했지만 이진탐색트리는 완전 이진 트리가 아니기 때문에 Node로 구현 Search 정렬되지 않은 배열의 탐색은 순차적으로 탐색하기 때문에 O(n) 이진 탐색 트리는 큰값과 작은값을 비교하면서 찾기 때문에 O(log n) 루트노드가 없는경우 nil반환 data와 노드의 왼쪽자식과 오른쪽 자식을 비교해가면서 확인 노드 반환 func search(_ data: T) -> Node? { if ..

Queue FIFO(First In First Out)형식의 자료구조 enqueue(데이터 추가)와 dequeue(데이터 추출)를 사용해 구현 swift의 reversed(시간복잡도 O(1))를 사용하여 구현 구현 코드 struct Queue { var enqueue: [T] var dequeue: [T] = [] var count: Int { return self.enqueue.count + self.dequeue.count } var isEmpty: Bool { return self.enqueue.isEmpty && self.dequeue.isEmpty } var first: T? { if self.dequeue.isEmpty { return self.enqueue.first } else { retu..

Heap 두개의 속성을 만족하는 트리 1) 형태 속성: 힙은 완전 이진트리(모든 노드가 채워져 있고 왼쪽에서 오른쪽으로 채워진 형태) 2) 힙 속성: 모든 노드의 데이터는 자식 노드들의 데이터 보다 크거나 같다 최대값과 최소값을 빠르게 찾아내도록 만들어진 자료구조(최대힙 & 최소힙) 시간복잡도는 O(logN) 배열에 넣고 최대값 & 최소값을 찾으려면 O(n)이 걸리지만 힙으로 구현할 경우 O(logN)구현 가능(우선순위 큐) 최대힙과 최소힙 최대힙 : 내 자식 노드의 값은 내 값보다 작거나 같아야 한다(Root노드 최대 값) 최소힙 : 내 자식 노드의 값은 내 값보다 크거나 같아야 한다(Root노드 최소 값) Index 계산 부모 index : 자식 index / 2 왼쪽자식: index * 2 오른쪽 ..