본문 바로가기

B-트리 #4. 변수 및 함수 선언 처음부터 끝까지 직접 구현해보고 싶었지만 교재의 부록으로 소스가 올려져 있었다. 그래서 열심히 베끼기!!! 물론! 이 소스가 완벽하지 않아서 개인적으로 손을 대긴했다. 그리고, 커다란 문제 발견!! 삭제 과정에서 무한 루프가 발생함. 이 부분은 이번 주말에 느긋하게 확인해보기로 하고 소스를 공개한다. #define DEGREE 5 // m차 B-트리 #define MAX_ELEMENTS 1000 // 입력되는 key의 최대 수 #define DELETE_COUNT 10 // 삭제시 빼줄 원소 수 /* global variables */ FILE* pInputStream; // input 파일의 핸들 FILE* pOutputStream; // output 파일의 핸들 typedef struct NODE {..
B-트리 #2. 삭제 삽입 검색 알고리즘에 이어 삭제 알고리즘을 알아보자. 삭제가 수행된 B-트리가 계속 B-트리의 성질을 유지하기 위해서는 키가 삭제된 뒤에도 최소한의 키 수가 되는지를 확인해야 된다. 만일 해당 노드가 최소한으로 유지해야 될 키 수보다 작게 되는 경우에는 적절한 조치를 취해줘야 한다. 삭제를 위해서는 삽입에서와 같이 먼저 삭제하려는 키 값이 들어있는 노드를 탐색한다. 만일 삭제하려는 키 값이 내부 노드에 있다면 리프 노드에 있는 이 키 값의 후행(Successor) 키 값과 교환을 한 뒤에 리프 노드에서 삭제한다. 삭제 후 노드가 유지해야 될 최소 키 값의 수가 만족하지 않으며 재분배(Redistribution)나 합병(Merge) 방법을 이용하여 최소 키 값 수를 유지하도록 해야 한다. ▣ 재분배(Red..
B-트리 #1. 소개 및 검색/삽입 B-트리는 인덱스를 조직하는 트리 구조로 가장 많이 사용되는 것으로써 Bayer와 McCreight에 의해 제안되었다. 이것은 m-원 균형 탐색 트리로서 효율적인 균형 알고리즘을 제공한다. 이어지는 내용에서 이해하기 쉽게 설명하기 위해 노력하겠지만 일단 위키피디아의 B-트리 링크를 제공하겠다. 위키피디아 B-트리 보기 특성 : m-원 탐색트리이다. 각 노드가 적어도 반 이상이 키 값으로 채워져 있어야 한다. 트리가 공백이 아닌 이상 처음부터 분기해야 한다. 트리가 균형을 유지해야 한다. ▣ 검색과 삽입 ◇ 검색 : B-트리의 검색은 m-원 탐색 트리의 직접 검색과 똑같은 과정을 거치게 된다. serchBT(key) // m-원 탐색 트리의 검색 알고리즘 // key : 키의 값 // x : 노드 // r..
다익스트라(Dijkstra) 알고리즘 정의 및 살펴보기 이 게시글은 강원대학교 컴퓨터정보통신공학전공에서 2010년 봄학기 알고리즘 강의시간에 참고한 서적의 정보를 기반으로 작성되었습니다. 이 알고리즘은 1959년 다익스트라(Dijkstra)가 고안하였다. 이것은 어떠한 간선도 음수 값을 가지지 않는 방향그래프에서 주어진 출발점과 도착점 사이의 최단 경로 문제를 푸는 알고리즘!! 예를 들어, 그래프의 점들이 각각 지하철 역을 나타내고 연결선들이 지하철 노선을 의미한다면 이 알고리즘은 지하철 역간의 최단 경로를 구하게 된다. 아래 알고리즘에서 u := Extract_Min(Q)는 점의 집합 Q에서 가장 작은 d[u]값을 찾은 다음 그 점 u를 Q에서 제거한 후 반환하는 함수를 가리킨다.function Dijkstra(G, w, s)for each vertex v..