자료구조 프로그래밍 Lab09) Patricia 만들기

자료구조 프로그래밍 Lab09) Patricia 만들기

문제

해결

구현 알고리즘은 탐색 / 삽입 두가지로 나뉜다

탐색.

0) t tree가 NULL 이면 탐색 실패

1) tree의 nextNode에 lch를 가져오고 current node에 현재 트리 t를 가져온다

2) bitNumber가 더 클 동안 계속 이동한다(bitNumber가 0이면 왼쪽, 값이 있으면 오른쪽 으로 이동)

3) nextnode를 반환

삽입.

0) t tree가 NULL이면 해당 노드에 값을 할당 후 종료

1) tree를 search 해서 값이 똑같으면 삽입 실패(이미 존재하는 값)

2) tree를 탐색하는 알고리즘을 통해서 탐색을 한 다음

3) 새로운 노드를 할당한 후에, 현재 노드가 부모 노드의 lch라면 부모노드의 lch에 새노드 할당,

 rch라면 부모노드의 rch에 새노드 할당

 
//구조체 정의
typedef struct element {
    unsigned key;
}element;
typedef struct patriciaTree * patricia;
typedef struct patriciaTree {
    int bitNumber;
    element data;
    patricia leftChild, rightChild;
}patriciaTree;
 
patricia root;
 
// 탐색 함수 주어진 key 값을 찾는다
patricia search(patricia t, unsigned k)
{
    patricia currentNode, nextNode;
 
    // 루트가 비어있으면 에러처리
    if (!t) return NULL; /*empty tree */
 
    // 다음 노드 가지고와서
    nextNode = t->leftChild;
    currentNode = t;
    
    // 찾을때까지 가서 비교한번 후 반환
    while (nextNode->bitNumber > currentNode->bitNumber) {
        // 다음 노드 이동
        currentNode = nextNode;
        nextNode = (bit(k, nextNode->bitNumber)) ?
            nextNode->rightChild : nextNode->leftChild;
    }
    // 찾은 노드 반환
    return nextNode;
}
 
void insert(patricia *t, element theElement)
{ /* insert theElement into the Patricia tree *t  */
    patricia current, parent, lastNode, newNode;
    int i;
 
    // 트리가 비어있다면
    if (!(*t)) {
        // 할당 후 첫 노드
        *t = (patricia)calloc(1,sizeof(patriciaTree));
        (*t)->bitNumber = 0; (*t)->data = theElement;
        (*t)->leftChild = *t; // lch는 자기 자신
        return;
    }
    
    // 만약 값이 있을 경우
    lastNode = search(*t, theElement.key);
    if (theElement.key == lastNode->data.key) {
        fprintf(fp2, "해당 키가 이미 존재합니다!\n");
        success = 0;
        return;
    }
 
    // 처음으로 다른 비트값의 위치 찾아오기
    for (i = 1; bit(theElement.key, i) == bit(lastNode->data.key, i); i++);
    
    // 탐색을 위한 세팅
    current = (*t)->leftChild; 
    parent = *t;
 
    // 탐색
    while (current->bitNumber > parent->bitNumber && current->bitNumber < i) {
        parent = current;
        current = (bit(theElement.key, current->bitNumber)) ?
            current->rightChild : current->leftChild;
    }
    // 새로운 노드를 할당한 후
    newNode = (patricia)calloc(1,sizeof(patriciaTree));
    newNode->data = theElement; 
    newNode->bitNumber = i; // 위에서 체크한 값
    newNode->leftChild = (bit(theElement.key, i)) ? current : newNode;
    newNode->rightChild = (bit(theElement.key, i)) ? newNode : current;
    
    // 어디 연결할지 체크 후 연결
    if (current == parent->leftChild)
        parent->leftChild = newNode;
    else 
        parent->rightChild = newNode;
}
 
// 해당 key 값에서 bitNumber번 째 값 반환
int bit(unsigned key, int bitNumber) {
    
    unsigned a = 1<< length - 1; // 1000 
    unsigned b = a >> bitNumber - 1; // 몇번쨰 비트인가
 
    // 해당 bit값 반환
    return key & b;    
}