C/자료구조와 알고리듬16 Chapter 12. 힙(Heap) Def) 힙(Heap) 완전 이진 트리의 한 분류로서, 힙 속성을 만족하는 자료구조. 이진 힙(Binary Heap) Note) 힙 속성(Heap Property) - 최대 힙 속성(Max Heap Property) 부모 노드의 키 값은 항상 자식 노드의 키 값보다 크거나 같다. - 최소 힙 속성(Min Heap Property) 부모 노드의 키 값은 항상 자식 노드의 키 값보다 작거나 같다. Note) 힙의 특징 - 루트 노드는 항상 최댓값 또는 최솟값을 갖음. - 부모 - 자식 사이의 크기 관계만 있고, 왼쪽 자식 - 오른쪽 자식 사이의 크기 관계는 없음. - 완전 이진 트리이기 때문에 트리의 높이 h = [log2N] - 힙의 응용 분야 힙 정렬, 우선순위 큐, 다익스트라 알고리즘 등 힙 이진 탐색.. 2021. 11. 25. Chapter 11. 이진 탐색 트리(Binary Search Tree) Def) 이진 탐색 트리(BST, Binary Search Tree) 자료의 효율적인 관리(삽입, 탐색, 삭제)를 위한 이진 트리 기반의 자료구조. 자료의 계층적인 구조를 표현하기 위해 트리를 사용하는 것이 아님. Note) 이진 탐색 트리의 특징 - 모든 노드 N에 대해, 왼쪽 서브 트리에 있는 모든 노드의 키값은 노드 N의 키값보다 작음. - 오른쪽 서브 트리에 있는 모든 노드의 키값은 노드 N의 키값보다 큼. - 자료의 탐색, 삽입, 삭제가 모두 O(logN)의 시간 복잡도로 동작. - 중위 순회시, 오름차순으로 정렬된 값을 얻을 수 있음. Note) 이진 탐색 트리 구현 코드(삽입, 탐색) #define _CRT_SECURE_NO_WARNINGS #include #include #include #.. 2021. 11. 21. Chapter 10. 트리(Tree) Def) 트리(Tree) 계층적인 구조를 나타내는 자료구조. 보통 Root가 위, Branch와 Leaf이 아래로 자라는 형태로 표현. Def) 노드(Node, Vertex) 트리의 데이터를 저장하는 원소 단위. 정점. Def) 엣지(Edge, Link) 노드와 노드를 연결하는 선. 간선 트리의 엣지는 부모-자식 계층 관계만을 나타냄. 즉, 엣지의 위에 있는 것이 부모, 아래가 자식. 노드의 개수가 N이면 항상 N - 1개의 엣지가 존재 즉, 두 개의 노드를 연결하는 엣지는 항상 유일함. Note) 트리 관련 용어 트리를 제대로 이해하기 위해선, 관련 용어 숙지가 필수. 루트(Root) 트리의 최상단 노드 부모 - 자식 관계(Parent - Child) 엣지로 연결되어 있는 두 노드의 상대적 관계 루트의.. 2021. 11. 19. Chapter 09. 해시 테이블(Hash Table) Chapter 06. 목차. 6.1 아이디어 6.2 해시 셋 6.3 해시 함수와 해시 값. 6.4 해시 테이블 With 배열 6.5 해시 테이블 With Doubly Linked list 6.1 탄생 배경과 구현 방법 - 우리의 뇌가 어떤 기억을 상기시키는 메커니즘을 생각해보자. 자신이 살아온 모든 기억을 선형 탐색하며 찾진 않음. 마치 어떤 Key가 있고, 해당 Value를 순식간에 찾아냄. - 병원에가도 마찬가지임. 주민번호를 읊으면 순식간에 5천만명중 정확하게 내 정보만 나오게 됨. 만약 선형 탐색한다면? 탐색하다 사망할 수도 있음. 이진 탐색은? 정렬되어 있지 않아서 사용 불가. 5천만개의 자료를 정렬하는데도 오래걸림. - 우체통도 각 가구마다 번호가 적혀 있어서 편하게 가져갈 수있음. 그러나 큰.. 2021. 11. 12. 이전 1 2 3 4 다음
