학과공부/자료구조13 Heap 개요 노드에 키를 저장하는 이진트리로, 다음 두 가지 성질을 만족한다. Heap order: 루트를 제외한 모든 노드 v에 대해 key(n) ≥ key( parent(n) ) Complete binary tree: 깊이 i [0 : h)에 노드 총 2i개. 특히 i = h-1에서 internal nodes are to the left of the external nodes 라고 하는데 잘 모르겠다. Last node 최대 깊이 h에서 가장 오른쪽에 있는 노드 트리의 높이 O(log n) 이다. 깊이 i [0 : h)에 2i개의 노드가 있고, h에 최소 한 개의 노드가 있다. 식으로 쓰면 n ≥ 1 + 2 + ... + 2h-1 + 1 = 2h 이다. 즉 n ≥ 2h 이다. 양변에 로그를 취하면 log n.. 2020. 12. 3. Priority Queue 개요 Entry를 담는 ADT로, Entry는 보통 key를 우선순위로 하는 { key, value } 쌍이다. 우선순위에 따라 정렬되는 Queue로, Entry 간 Total order relation이 성립한다. Priority Queue 대표적인 operation은 insert, removeMin이 있고, 추가로 min, size, empty 등을 지원할 수 있다. List-based 구현으로 sorted list를 이용하는 방법과 unsorted list를 이용하는 방법이 있다. Total order relation 전순서라고 하며, Reflexive property ( x ≤ x ) Antisymmetric property ( x ≤ y and y ≤ x then x = y ) Transitiv.. 2020. 12. 3. Queue 개요 한 쪽 끝에선 삽입, 다른 쪽 끝에선 삭제가 일어나는 자료구조 Queue의 성질 First-in First-out (FIFO), 즉 선입선출 방식으로 객체를 담는다. rear에 삽입하고 front에서 삭제한다. Queue 대표적인 operation은 enqueue, dequeue가 있고, 추가로 front, size, empty 등을 지원할 수 있다. Array 또는 Linked List로 구현할 수 있다. Array의 크기를 변경하기 곤란하다는 점을 고려하여 환형으로 구성하면 시간복잡도를 낮출 수 있다. 배열에서 큐의 시작점, 끝점, 크기를 기억하는 변수를 만들어서 구현할 수 있다. 아래는 Array기반 큐의 구현 예시이다. (Linked list 기반 큐는 SLL과 똑같다.) struct Arr.. 2020. 10. 26. Stack 개요 한 쪽 끝에서만 삽입 삭제가 일어나는 자료구조 Stack의 성질 Last-in First-out (LIFO), 즉 후입선출 방식으로 객체를 담는다. 삽입과 삭제에 쓸 위치를 알고 있어야 한다. Stack 대표적인 operation은 push, pop이 있고, 추가로 top, size, empty 등을 지원할 수 있다. Array 또는 Linked List로 구현할 수 있다. 아래는 각각에 대한 예시이다. struct ArrayStack { int* stack; int maxSize, sz; ArrayStack(int ms) { maxSize = ms; sz = 0; stack = new int[maxSize]; } void push(int data); int pop(); } struct Node {.. 2020. 10. 26. Doubly Linked List와 Iterator 개요 노드의 sequence를 담은 자료구조. 더 일반화 된 List ADT를 구현할 수 있다. DLL의 성질 각 노드는 이전 노드와 다음 노드에 대해 양방향으로 연결한다. 두 더미 노드 trailer, header를 활용하면 구현에 용이하다. Node SLL에 추가로 이전 노드의 주소를 가진다. 아래는 앞으로 사용할 노드의 예시이다. struct Node { int data; Node* next; Node* prev; } Doubly Linked List SLL보다 일반적인 함수 구현에 유리하다. 예를 들면, 다음과 같은 ADT를 구성할 수 있다. struct DLL { Node* head; Node* tail; Iter it; void insert(Node* target, int e); void er.. 2020. 10. 26. Singly Linked List 개요 노드의 sequence를 담은 자료구조. Array의 단점인 유연하지 못한 크기 조절을 해소한다. SLL의 성질 각 노드는 다음 노드를 연결하여 단방향 순차 접근이 가능하다. Node 각 노드는 값 (element)과 다음 노드의 주소를 가진다. 아래는 int형 element (data)와 다음 노드의 주소 (next)를 가지는 노드의 예시이다. struct Node { int data; Node* next; } Singly Linked List SLL은 ADT로서 데이터 (노드), Operation (함수)를 가진다. 아래는 노드의 시작 주소 (head)와 간단한 함수들을 가지는 SLL의 예시이다. struct SLL { Node* head; int at(int); bool empty(); voi.. 2020. 10. 26. 이전 1 2 3 다음
