Computer Science/Data Structure
-
[자료구조] B-Tree, B*Tree, B+TreeComputer Science/Data Structure 2023. 2. 28. 23:02
B-Tree 데이터베이스와 파일 시스템에서 사용되는 트리 자료구조의 일종으로, 이진 트리가 자식 노드를 최대 2개만 가질 수 있지만 B-tree는 자식 노드의 개수가 2개 이상인 트리입니다. 또한 노드 내의 데이터가 1개 이상일 수 있습니다. 노드 내 최대 데이터 수가 2개라면 2차 B-Tree, 3개라면 3차 B-Tree 라고 합니다. 하나의 노드에 여러 정보를 담게 되고, 여러 자식을 가질 수 있게 되면서 "차수"라는 개념이 등장합니다. 최대 M개의 자식을 가질 수 있는 B-Tree를 M차 B-Tree라고 부릅니다. 이렇게 하나의 노드에 여러 자료를 배치하게 되면서 이진 트리보다 훨씬 많은 데이터를 효율적으로 저장소에 담을 수 있게 되었습니다. 하드디스크, SSD와 같은 외부 기억장치(비휘발성 메모리..
-
[자료구조] 레드-블랙 트리(Red-Black Tree)Computer Science/Data Structure 2023. 2. 27. 16:47
Red-Black Tree 자가 균형 이진 탐색 트리(self-balancing binary search tree) 로서, 대표적으로 연관 배열 등을 구현하는 데 쓰이는 자료구조입니다. 트리에 N개의 원소가 있을 때 O(log N)의 시간 복잡도를 삽입, 삭제, 검색을 할 수 있습니다. 레드-블랙 트리는 복잡한 자료구조이지만, 실 사용에서 효율적이고, 최악의 경우에도 일정한 실행 시간을 보장하여 실시간 처리와 같은 실행 시간이 중요한 경우에 유용하게 사용됩니다. 특성 Red-Black Tree는 각각의 노드가 Red, Black 두가지의 색상 속성을 가지고 있는 이진 탐색 트리입니다. 각 구성 원소는 in-order traversal(중위순회) 연산을 수행합니다. - in-order traversal(중..
-
[자료구조] Heap & Priority Queue 구현Computer Science/Data Structure 2023. 2. 12. 19:40
Priority_queue Heap성질을 가진 자료구조입니다. Java에서 priority_queue 의 기본 정렬 구현은 Min Heap입니다. C++에서 priority_queue 의 기본 정렬 구현은 Max Heap입니다. Heap 힙(Heap) 은 특정 연산을 빠르게 수행하기 위한 이진 트리 자료구조로 부모 노드와 자식 노드간의 일련의 규칙을 통해 일관성있는 결과를 도출해내기 위한 자료구조입니다. Min Heap은 부모가 자식보다 작은 이진 트리를 구성하여 루트 노드가 전체 데이터의 최솟값이 됩니다. Max Heap은 부모가 자식보다 큰 이진 트리를 구성하여 루트 노드는 전체 데이터의 최댓값이 됩니다. Binary Heap 구현은 이진 트리의 Root노드부터 단일 Leaf노드까지의 순회 비용만 가..
-
[자료구조] Linked list (연결리스트)Computer Science/Data Structure 2022. 9. 23. 21:11
Linked List 란? node라는 객체로 이루어져 있다. 여러개의 node를 연결함으로써 데이터 표현 가능 시작(주소) - 연결(link) - 끝(null pointer or circular) 코드로 아래와 같이 구현할 수 있다. typedef struct Node{ int data; Node *next; }Node; Linked list 장점 동적으로 메모리 사용가능 메모리 효율적 사용 데이터 재구성 용이 대용량 데이터 처리 적합 Linked list 단점 특정 위치 데이터 검색 느림 메모리를 추가적으로 사용해야 함 Singly Linked list Circularly Linked list : 마지막 노드가 다시 처음 노드를 가리킴.
-
[자료구조] Array(배열) , dynamic arrayComputer Science/Data Structure 2022. 9. 5. 17:17
Array Array 란? 배열은 연속된 메모리 공간에 순차적으로 저장된 데이터 모음입니다. 메모리상에 연속적이며 순차적으로 미리 할당된 크기만큼 저장합니다. 배열을 구성하는 각각의 값을 요소(element)라고 하며, 배열의 위치를 가르키는 숫자를 index라고 합니다. Array 특징 고정된 저장 공간 순차적인 데이터 저장 배열에 각 요소에 접근하는 시간은 O(1)로 모두 동일 - 기본위치 + offset(요소크기 * index)연산으로 모든 요소에 접근 가능 연속된 메모리에 단일 블록화하여 데이터를 저장 - 낭비되는 공간이 거의 없음 - 큰 배열일 경우, 필요 메모리 할당이 불가능할 수 있음 실제 메모리 상에서 물리적으로 데이터가 순차적으로 저장되고, indexing, slicing 가능 Array..