c 언어 B 트 리 깊이 이해
우 리 는 그것 의 결점 구 조 를 보 았 다.아래 그림 과 같다.
각 결점 에는 키워드 와 지향 자 결점 의 지침 이 저장 되 어 있어 관건 코드 보다 지침 이 하나 더 많다 는 것 을 쉽게 알 수 있다.B 나무의 정 의 를 통 해 우 리 는 그것 의 일부 특징 을 알 수 있다.1.나무 가 높 고 균형 이 잡 히 며 모든 잎 이 같은 층 에 있다.2.키 워드 는 중복 되 지 않 고 오름차 순 으로 정렬 합 니 다.부모 노드 의 키 코드 는 하위 노드 의 경계 입 니 다.3.B 트 리 는 값 이 가 까 운 관련 기록 을 같은 디스크 페이지 에 넣 고 국부 적 인 원 리 를 이용 했다.4.B 나 무 는 일정한 비율의 결점 이 꽉 차 서 공간 이 용 률 을 개선 할 수 있다.
B 나무 결점 의 크기 는 어떻게 확정 합 니까?디스크 작업 을 최소 화하 기 위해 서 는 보통 노드 크기 를 디스크 페이지 크기 로 설정 합 니 다.일반 트 리 의 높이 는 3 층 을 넘 지 않 는 다.즉,키 코드 를 찾 으 려 면 3 번 의 디스크 조작 만 하면 된다 는 것 이다.실현 할 때 저 는 의 내용 을 참조 하여 먼저 1.B 나무의 뿌리 결산 점 이 항상 메 인 저장 소 에 있 고 디스크 작업 을 읽 을 필요 가 없다 고 가정 합 니 다.단,루트 노드 가 바 뀌 면 디스크 쓰기 작업 을 한 번 해 야 합 니 다.2.모든 노드 가 매개 변수 로 전 달 될 때 디스크 를 한 번 읽 어야 합 니 다.
실현 할 때 사실은 간소화 도 했다.모든 결점 은 관건 적 인 코드 와 지침 을 포함 하 는 것 을 제외 하고 이 관건 적 인 코드 가 해당 하 는 파일 의 정 보 를 기록 해 야 한다.예 를 들 어 파일 의 오프셋,그렇지 않 으 면 어떻게 이 기록 을 찾 을 수 있 을 까?이 를 실현 할 때 이 추가 데 이 터 는 노드 에 넣 지 않 았 습 니 다.다음은 트 리 의 구 조 를 정의 합 니 다.파일 이름 은 btrees.h 이 고 내용 은 다음 과 같 습 니 다.
/* btrees.h */
# define M 2
/* B M>=2
* M-1 。 M
* 2M-1 。 2M
*/
typedef int bool ;
struct btnode{ /* B */
int keyNum; /* */
int k[2*M-1]; /* */
struct btnode * p[2*M]; /* */
bool isleaf;
};
struct searchResult{
struct btnode *ptr; /* */
int pos; /* */
};
# include <stdio.h>
# include <stdlib.h>
# include "btrees.h"
/* */
struct btnode * allocateNode( struct btnode *ptr){
int i,max;
ptr = ( struct btnode *) malloc ( sizeof ( struct btnode));
if (!ptr){
printf ( "allocated error!/n" );
exit (1);
}
max = 2*M;
for (i=0; i<max; i++)
ptr->p[i] = NULL; /* */
memset (ptr->k, 0, (max-1)* sizeof ( int )); /* */
return ptr;
}
/* B ， */
struct btnode * btreeCreate( struct btnode *root){
root = allocateNode(root);
root->keyNum = 0;
root->isleaf = 1;
return root;
}
B 나무의 삽입 은 모두 잎 결점 에서 이 루어 지 는데,B 나무의 결점 중 키 코드 의 개 수 는 제한 되 어 있 기 때문에 최소 도수 가 M 인 B 나무의 결점 개 수 는 M-1 에서 2M-1 개 이다.예 를 들 어 아래 그림 은 최소 도수 가 2 인 B 나무(2-3 나무 라 고도 함)로 다음 그림 에서 보 듯 이 그의 결점 의 개 수 는 1-3 개 이다.
은 먼저 삽입 할 위치 에 위치 하고 만약 에 잎 결점 의 관건 적 인 코드 개수 가 상한 선 에 이 르 지 못 하면 예 를 들 어 32 를 삽입 하면 비교적 간단 하고 직접 삽입 하면 된다.만약 잎 결점 의 관건 적 인 코드 수가 상한 선 에 이 르 렀 다 면 두 개의 자 결점 으로 분열 하여 중간의 관건 적 인 코드 를 부모 노드 에 위로 올 려 야 한다.그러나 극단 적 인 경우 에는 아버지의 결점 도 가득 차 서 다시 분열 해 야 하고 마지막 에 뿌리 결점 도 분열 시 켜 야 할 수도 있다.그러나 이런 알고리즘 은 실현 되 기 가 쉽 지 않다.에서 실 현 된 것 은 다른 사상 이다.바로 먼저 분열 하 는 것 이다.삽입 위 치 를 찾 는 과정 에서 가득 찬 결점 을 발견 하면 먼저 그것 을 분열 시 켰 다.이것 은 마지막 잎 결점 에 데 이 터 를 삽입 할 때 이 잎 결점 의 아버지 결점 이 항상 불만 을 가 진 다 는 것 을 보장 한다.다음은 우리 가 예 를 하나 보 자.우 리 는 점 마다 삽입 하 는 방법 으로 B 나 무 를 만 들 었 습 니 다.결산 순 서 는 각각{18,31,12,10,15,48,45,47,50,52,23,30,20}입 니 다.구체 적 인 과정 을 살 펴 보 겠 습 니 다.1.빈 B 나 무 를 만 듭 니 다.2.18 을 삽입 합 니 다.이때 꽉 찬 것 은 다음 과 같 습 니 다.
3.같은 이치 로 31 과 12 를 삽입 하 는 것 은 모두 비교적 간단 하 다.다음 과 같다.
4.10 을 삽입 할 때 뿌리 결점 이 가득 차 면 분열 해 야 한다.뿌리 결점 이 비교적 특수 하기 때문에 아버지 결점 이 없 으 면 단독으로 처리 해 야 한다.선생님 은 하나의 빈 결점 을 새로운 뿌리 결점 으로 하고 분열 을 한다.다음 과 같다.
5.15,48,45 를 다시 삽입 합 니 다.꽉 차지 않 기 때문에 직접 삽입 합 니 다.다음 과 같 습 니 다.
6.47 을 삽입 하면 이번 잎 이 꽉 차 면 먼저 분열 한 다음 에 삽입 해 야 한다.다음 과 같다.
다른 것 은 모두 같은 이치 이 므 로 군말 하지 않 겠 습 니 다.다음은 소스 코드 입 니 다.btree.c 에 가입 하고 마지막 으로 main 함수 와 넓 은 범위 에서 트 리 를 먼저 표시 하 는 방법 을 썼 습 니 다.여러분 은 스스로 결 과 를 비교 할 수 있 습 니 다.코드 의 실현 은 과 블 로 그 를 참조 하 였 습 니 다.
http://hi.baidu.com/kurt023/blog/item/4c368d8b51c59ed3fc1f10cc.html
그의 블 로그 에 서 는 이미 실현 되 었 다.다만 B 트 리 를 정의 할 때 포인터 수 와 키 코드 가 같 아서 나 는 스스로 다시 썼 다.
// ：
void btreeSplitChild( struct btnode *parent, int pos, struct btnode *child){
struct btnode *child2;
int i;
//
child2 = allocateNode(child2);
//
child2->isleaf = child->isleaf;
//
child2->keyNum = M-1;
//
for (i=0; i<M-1; i++)
child2->k[i] = child->k[i+M];
// ，
if (!child->isleaf)
for (i=0; i<M; i++)
child2->p[i] = child->p[i+M];
child->keyNum = M-1;
//
//
for (i=parent->keyNum; i>pos; i--){
parent->k[i] = parent->k[i-1];
parent->p[i+1] = parent->p[i];
}
parent->k[pos] = child->k[M-1];
parent->keyNum++;
parent->p[pos+1] = child2;
}
/* ：
* ： key B
*/
void btreeInsertNoneFull( struct btnode *ptr, int data){
int i;
struct btnode *child; //
i = ptr->keyNum;
// ，
if (ptr->isleaf){
while ((i>0) && (data<ptr->k[i-1])){
ptr->k[i] = ptr->k[i-1];
i--;
}
//
ptr->k[i] = data;
ptr->keyNum++;
}
else { // ，
while ((i>0) && (data<ptr->k[i-1]))
i--;
child = ptr->p[i];
if (child->keyNum == 2*M-1){
btreeSplitChild(ptr, i, child);
if (data > ptr->k[i])
i++;
}
child = ptr->p[i];
btreeInsertNoneFull(child, data); //
}
}
/* */
struct btnode * btreeInsert( struct btnode *root, int data){
struct btnode * new ;
/* ， ， */
if (root->keyNum == 2*M-1){
new = allocateNode( new );
new ->isleaf = 0;
new ->keyNum = 0;
new ->p[0] = root;
btreeSplitChild( new , 0, root);
btreeInsertNoneFull( new , data);
return new ;
}
else { // ，
btreeInsertNoneFull(root, data);
return root;
}
}
// ：
void btreeDisplay( struct btnode *root){
int i, queueNum=0;
int j;
struct btnode *queue[20];
struct btnode *current;
//
queue[queueNum] = root;
queueNum++;
while (queueNum>0){
//
current = queue[0];
queueNum--;
//
for (i=0; i<queueNum; i++)
queue[i] = queue[i+1];
//
j = current->keyNum;
printf ( "[ " );
for (i=0; i<j; i++){
printf ( "%d " , current->k[i]);
}
printf ( "] " );
//
if (current!=NULL && current->isleaf!=1){
for (i=0; i<=(current->keyNum); i++){
queue[queueNum] = current->p[i];
queueNum++;
}
}
}
printf ( "/n" );
}
int main()
{
struct btnode *root;
int a[13] = {18, 31, 12, 10, 15, 48, 45, 47, 50, 52, 23, 30, 20};
int i;
root = btreeCreate(root);
for (i=0; i<13; i++){
root = btreeInsert(root, a[i]);
btreeDisplay(root);
}
return 0;
}
：
B ， 4 [1，2，3，4] ， 2 3 ； 。
， Linux 。 
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
c 언어 간단한 파일 r/w 조작 방법데이터의 입력과 출력은 거의 모든 C 언어 프로그램과 수반된다. 입력이란 원본에서 데이터를 얻는 것이다. 출력은 단말기에 데이터를 쓰는 것으로 이해할 수 있다.이곳의 원본은 키보드, 마우스, 하드디스크, 시디, 스캐...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
