자료구조 3

[Data Structure] B-tree 정의 및 장/단점

검색을 위한 자료구조 중에 잠재력이 가장 큰 것은 역시 트리이다. 그 중 이번 포스팅에서는 B-tree에 대해 알아볼 것이다. B-tree는 주로 데이터베이스에서 인덱스를 저장할 때, 많이 사용된다. 이번 포스팅을 찾은 사람 중에 인덱스 관련 글을 보던 중, B-tree에 대해 궁금해져 찾아온 사람도 있을 것이다. 그럼 B-tree에 대해 알아보자. B-tree의 정의- 모든 노드는 최대 m개의 자식들을 가진다.- 루트노드와 리프노드가 아닌 모든노드는 최소 m/2개의 자식을 가진다.- 루트노드는 최소 2개 이상의 자식을 가진다.- k개의 자식을 가진 리프노드가 아닌 노드는 k-1개의 키를 가진다.- 모든 리프노드들은 같은 높이에 있어야 한다.- 모든 노드들은 키와 자식노드에 대한 포인터로 이루어져 있다...

[Data Structure] 자료구조 (Data Structure)

자료구조 : 데이터들의 관계를 구조화한 것 자료구조의 분류선형 자료구조 : 리스트, 스택, 큐비선형 자료구조 : 트리, 그래프 ●배열(Array)-타입이 동일한 데이터들의 집합-연속된 공간의 메모리를 할당-인덱스를 통하여 자료의 순서와 위치를 표시-인덱스를 이용하여 직접적으로 자료에 접근 가능 ●리스트(List)-특정원소의 탐색-머리(Head)부터 꼬리(Tail)까지 순차탐색-i번째 원소의 삽입, 삭제 배열리스트(Array List)탐색 : 머리(Head)부터 순차탐색 가능, 인덱스를 이용한 직접 접근 가능 삽입 : 끝에 삽입하면 해당 메모리 주소에 삽입, 중간에 삽입하면 이후의 모든 데이터를 뒤로 밀고 삽입 삭제 : 끝에 있는 자료는 바로 삭제, 중간에 있는 데이터는 삭제 후에 이후의 데이터를 모두 당..

[C/C++]최대 히프, 최소 히프

알고리즘을 배우면서 히프라는 것을 많이 보고 쓰게된다. 정렬이라던지 허프만이라던지 기타등등...그래서 여기 최대히프와 최소히프를 올린다. 나도 참고하고 쓰실 분들도 참고하기 바란다. 1. HeapDefine.h 최대 사이즈가 100으로 잡혀있다. 사이즈를 늘리고 싶으면 Define 헤더에서 늘려서 쓰도록하자. #define MAX_ELEMENT 100 //히프 만들 때, 사용하는 히프노드 typedef struct { int heap[MAX_ELEMENT]; int heap_size; } HeapType; 2. MaximamHeap.h #include "HeapDefine.h" //초기화 함수 void initMaxHeap(HeapType *h) { h->heap_size = 0; } //삽입 함수 vo..

Programming/C, C++ 2012.10.14