A B 트리에

Question

가능한 중복 수준의 수를 찾는 방법 :
Segmentation fault in btree implementation

가 어떻게이 (가)에서 B-트리의 레벨 수를 찾으려면 찾을 수 있습니다 다음 코드

#include<stdio.h> 
#include<stdlib.h> 
#define M 10 
struct node 
    { 
int n; /* n < M No. of keys in node will always less than order of Btree */ 
int keys[M-1]; /*array of keys*/ 
struct node *p[M]; /* (n+1 pointers will be in use) */ 
    }*root=NULL; 

    enum KeyStatus { Duplicate,SearchFailure,Success,InsertIt,LessKeys }; 
    void insert(int key); 
    void display(struct node *root,int); 
    enum KeyStatus ins(struct node *r, int x, int* y, struct node** u); 
    int searchPos(int x,int *key_arr, int n); 

    int main() 
    { 
    int key; 
    int choice; 
    int i,j,mul,count=0; 
    int mul_count[65026]={0},value[7097]; 
    for(i=1;i<=255;i++) 
    { 
      for(j=1;j<=255;j++) 
      { 
      mul = j*i; 
      mul_count[mul]++; 
      } 
    } 

     for(i=1;i<=65026;i++) 
     { 
     if(mul_count[i]!= 0 && mul_count[i]!= 2) 
      { 
      value[count]=i; 
        count++; 
      } 
     } 
     printf("Creation of B tree for node %d\n", M); 
     while(1) 
    { 
     printf("1.Insert\n"); 
     printf("2.Display\n"); 
     printf("3.Quit\n"); 
     printf("Enter your choice : "); 
     scanf("%d",&choice); 
     switch(choice) 
    { 
     case 1: 
     printf("Inserting is done automatically press 2: \n"); 
     //scanf("%d",&key); 
     for(i=0;i<count;i++) 
     { 
     key = value[i]; 
     insert(key); 
     } 
    break; 



     case 2: 
      printf("Btree is :\n"); 
     display(root,0); 
     break; 

     ase 3: 
     exit(1); 

       default: 
      printf("Wrong choice\n"); 
     break; 

      }/*End of switch*/ 

     }/*End of while*/ 
     return 0; 
      }/*End of main()*/ 



    void insert(int key) 
    { 
    struct node *newnode; 
    int upKey; 
    enum KeyStatus value; 
    value = ins(root, key, &upKey, &newnode); 
     if (value == Duplicate) 
     printf("Key already available\n"); 
     if (value == InsertIt) 
    { 
     struct node *uproot = root; 
     root=malloc(sizeof(struct node)); 
    root->n = 1; 
    root->keys[0] = upKey; 
    root->p[0] = uproot; 
    root->p[1] = newnode; 
    }/*End of if */ 
    }/*End of insert()*/ 


    enum KeyStatus ins(struct node *ptr, int key, int *upKey,struct node **newnode) 
    { 
     struct node *newPtr, *lastPtr; 
     int pos, i, n,splitPos; 
     int newKey, lastKey; 
     enum KeyStatus value; 
    if (ptr == NULL) 
     { 
    *newnode = NULL; 
    *upKey = key; 
    return InsertIt; 
    } 
    n = ptr->n; 
    pos = searchPos(key, ptr->keys, n); 
    if (pos < n && key == ptr->keys[pos]) 
    return Duplicate; 
    value = ins(ptr->p[pos], key, &newKey, &newPtr); 
    if (value != InsertIt) 
    return value; 
    /*If keys in node is less than M-1 where M is order of B tree*/ 

    if (n < M - 1) 
    { 
    pos = searchPos(newKey, ptr->keys, n); 
    /*Shifting the key and pointer right for inserting the new key*/ 
    for (i=n; i>pos; i--) 
    { 
    ptr->keys[i] = ptr->keys[i-1]; 
    ptr->p[i+1] = ptr->p[i]; 
    } 
    /*Key is inserted at exact location*/ 
    ptr->keys[pos] = newKey; 
    ptr->p[pos+1] = newPtr; 
    ++ptr->n; /*incrementing the number of keys in node*/ 
    return Success; 
    }/*End of if */ 
    /*If keys in nodes are maximum and position of node to be inserted is last*/ 
    if (pos == M - 1) 
    { 
    lastKey = newKey; 
    lastPtr = newPtr; 
    } 

    else /*If keys in node are maximum and position of node to be inserted is not last*/ 
    { 
    lastKey = ptr->keys[M-2]; 
    lastPtr = ptr->p[M-1]; 
    for (i=M-2; i>pos; i--) 
     { 
    ptr->keys[i] = ptr->keys[i-1]; 
     ptr->p[i+1] = ptr->p[i]; 
     } 

    ptr->keys[pos] = newKey; 
     ptr->p[pos+1] = newPtr; 
    } 
    splitPos = (M - 1)/2; 
    (*upKey) = ptr->keys[splitPos]; 
    (*newnode)=malloc(sizeof(struct node));/*Right node after split*/ 
    ptr->n = splitPos; /*No. of keys for left splitted node*/ 
    (*newnode)->n = M-1-splitPos;/*No. of keys for right splitted node*/ 
    for (i=0; i < (*newnode)->n; i++) 
      { 
     (*newnode)->p[i] = ptr->p[i + splitPos + 1]; 
     if(i < (*newnode)->n - 1) 
     (*newnode)->keys[i] = ptr->keys[i + splitPos + 1]; 
     else 
     (*newnode)->keys[i] = lastKey; 
     } 
    (*newnode)->p[(*newnode)->n] = lastPtr; 
    return InsertIt; 
    }/*End of ins()*/ 



    void display(struct node *ptr, int blanks) 
    { 
    int check = 0; 
    if (ptr) 
     { 
    int i; 
    for(i=1;i<=blanks;i++) 
     printf(" "); 
    for (i=0; i < ptr->n; i++) 
    { 
    //check++; 
    printf("%d ",ptr->keys[i]); 
     } 
    printf("\n"); 
    for (i=0; i <= ptr->n; i++) 
    display(ptr->p[i], blanks+10); 
     }/*End of if*/ 

    //printf("\n no of levels:%d",check); 

    }/*End of display()*/ 




     int searchPos(int key, int *key_arr, int n) 
      { 
     int pos=0; 
     while (pos < n && key > key_arr[pos]) 
    pos++; 
     return pos; 
     }/*End of searchPos()*/ 

Answer 1

그것의 당신의 display 기능과 같은 조금 :

int max(int a, int b) 
{ 
    return a > b ? a : b; 
} 

int depth(struct node *ptr) 
{ 
    int d=0; 
    if (ptr==NULL) 
     return d; 
    for (i=0; i <= ptr->n; i++) 
     d=max(d,depth(ptr->p[i])) 
    return d+1; 
}