B트리 삽입 삭제 알고리즘 구현 및 분석

소개

B Tree에 대한 삽입 삭제 알고리즘을 구현하고

분석하는 과제입니다.

목차

Internet Explorer

본문내용

/* B-트리 삽입 알고리즘 */
/* 알고리즘에서 사용되는 변수는 다음과 같다.
In-key : B-트리에 삽입될 키
Finished : 삽입이 완료되었음을 나타내는 플래그
Found : B-트리에서 레코드가 발견되었음을 나타내는 플래그
P : 노드에 대한 포인터
TOOBIG : 오버플로 노드를 위한 변수
N : 키 카운터 */

/* 노드의 주소를 스택에 저장하면서 In-key가 삽입될 위치를 탐색한다. */
Found = false; /* B-트리에서 레코드가 발견되었음을 나타내는 플래그에 거짓이라는 값으로 초기화한다. */
read root; /* B-트리의 루트를 읽어 들인다. */

do{
N = number of keys in current node;
/* 해당노드 안에 킷값들의 개수를 N이라는 키 카운터에 넣는다. */
if(In-key == key in current node) Found = true;
/* B-트리에 삽입될 키와 해당노드속의 키가 같으면 B-트리에서 레코드가
발견되었음을 알려주는 플래그가 참이 된다. */

else if (In-key < key1) P = PO;
/* 위의 if문의 조건이 거짓이면 삽입될 키와 key1를 비교하여 key1보다
작다면 노드에 대한 포인터(P)에 PO라는 값을 넣어 왼쪽의 노드를 가리킨다. */
else if (In-key > keyN) P = PN;
/* 위 두 if문의 조건에 맞지 않는다면 삽입될 키와 keyN을 비교하여 삽입될 키가 크다면 노드에 대한 포인터(P)에 PN이라는 값을 넣어 오른쪽 노드를 가리킨다. */
else P = Pi-1;/* for some I where keyi-1< In-key <keyi */
/* In-key의 범위가 노드의 왼쪽 오른쪽 키값의 가운데 범위일 때 노드에
대한 포인터에 Pi-1이라는 값을 넣는다. */
if (P != null) { /* 노드에 대한 포인터가 null이 아닐 경우 */
push onto stack address of current node;
/* 해당노드의 주소가 스택에 삽입된다. 이는 후에 삽입 되었을 때

참고자료

· 없음