Skip to content

Project2_Milestone1_1

Yeonguk Go edited this page Oct 8, 2021 · 1 revision

Analysis of functions

Index

  1. license_notice
  2. print_license
  3. usage_1
  4. usage_2
  5. usage_3
  6. enqueue
  7. dequeue
  8. print_leaves
  9. height
  10. path_to_root
  11. print_tree
  12. find_and_print
  13. find_and_print_range
  14. find_range
  15. find_leaf
  16. find
  17. cut
  1. make_record
  2. make_node
  3. make_leaf
  4. get_left_index
  5. insert_into_leaf
  6. insert_into_leaf_after_splitting
  7. insert_into_node
  8. insert_into_node_after_splitting
  9. insert_into_parent
  10. insert_into_new_root
  11. start_new_tree
  12. insert
  1. get_neighbor_index
  2. remove_entry_from_node
  3. adjust_root
  4. coalesce_nodes
  5. redistribute_nodes
  6. delete_entry
  7. delete
  8. destroy_tree_nodes
  9. destroy_tree
void license_notice( void )

void print_license( int license_part )

void usage_1( void )

void usage_2( void )

void usage_3( void )

void enqueue( node * new_node )

node * dequeue( void )

void print_leaves( node * root )

9. height

int height( node * root )

int path_to_root( node * root, node * child )

void print_tree( node * root )

void find_and_print(node * root, int key, bool verbose)

void find_and_print_range( node * root, int key_start, int key_end,
        bool verbose )

int find_range( node * root, int key_start, int key_end, bool verbose,
        int returned_keys[], void * returned_pointers[])

node * find_leaf( node * root, int key, bool verbose )

현재 tree에서 입력받은 key를 포함하는 범위의 leaf node를 탐색한다.

  • 인자
    • root (node 포인터) : 현재 tree의 root node.
    • key (int) : 탐색할 key.
    • verbose (bool) : 함수 실행 시 상세 정보 출력 여부. 여기서는 설명하지 않음.
  • 반환 : (record 포인터)
    • 현재 tree에서 입력받은 key를 포함하는 범위의 leaf node.

  1. 탐색할 tree가 비었는지 확인한다. 비어있을 경우, 인자로 받은 root node 포인터를, 즉 NULL을 반환한다.
  2. root node부터 시작해서 입력받은 key를 포함하는 범위의 node를 탐색해나가며, 최종적으로 해당 key를 포함하는 범위의 leaf node를 찾아 그 포인터를 반환한다.

16. find

record * find( node * root, int key, bool verbose )

현재 tree에서 입력받은 key를 가지는 record를 탐색한다.

  • 인자
    • root (node 포인터) : 현재 tree의 root node.
    • key (int) : 탐색할 key.
    • verbose (bool) : 함수 실행 시 상세 정보 출력 여부. 여기서는 설명하지 않음.
  • 반환 : (record 포인터)
    • 현재 tree에서 입력받은 key를 가지는 record.

  1. find_leaf 함수를 call하여 현재 tree에서 입력받은 key를 포함하는 범위의 leaf node를 탐색한다. 존재하지 않을 경우, NULL을 반환한다.
  2. 해당 leaf node에서 입력받은 key를 가지는 record를 탐색한다. 존재하지 않을 경우, NULL을 반환한다.
  3. 해당 record를 반환한다.

17. cut

int cut( int length )

노드를 분할할 적절한 위치를 찾는다.

  • 인자
    • length (int) : 분할할 노드의 최대 key 개수. (order-1).
  • 반환 : (int)
    • 인자로 받은 length를 가지는 노드를 분할할 적절한 위치.


record * make_record(int value)

입력받은 value를 가지는 record를 생성한다.

  • 인자
    • value (int) : 생성할 record가 가질 value.
  • 반환 : (record 포인터)
    • 인자로 받은 value를 가지는 새로운 record.

  1. record 포인터 변수를 선언한 후 동적할당한다. 할당과 할당 실패 시 처리 과정에서 stdio.h에 존재하는 perror 함수, stdlib.h에 존재하는 malloc, exit 함수가 call된다. 할당 실패 시, 오류 메시지를 출력하고 프로그램을 강제종료한다.
  2. 해당 record 구조체에 입력받은 value를 저장한 후 이를 반환한다.

node * make_node( void )

leaf node / internal node로 사용될 수 있는 일반적인 node를 생성한다.

  • 인자 : 없음
  • 반환 : (node 포인터)
    • 생성한 node.

  1. node 포인터 변수를 동적할당하고, 해당 구조체의 keys 멤버 변수와 pointers 멤버 변수도 동적할당한다. 할당과 할당 실패 시 처리 과정에서 stdio.h에 존재하는 perror 함수, stdlib.h에 존재하는 malloc, exit 함수가 call된다. 할당 실패 시, 오류 메시지를 출력하고 프로그램을 강제종료한다.
  2. 해당 node 구조체를 초기화한 후 이를 반환한다.

node * make_leaf( void )

leaf node를 생성한다.

  • 인자 : 없음
  • 반환 : (node 포인터)
    • 생성한 leaf node.

  1. node 포인터 변수를 선언한 후, make_node 함수를 call하여 새로 생성한 node를 저장한다.
  2. 해당 node 구조체의 멤버 변수의 값을 변경하여 leaf로 설정한 후 이를 반환한다.

int get_left_index(node * parent, node * left)

부모 node에서 left node의 index를 확인한다.

  • 인자
    • parent (node 포인터) : left node의 부모 node.
    • left (node 포인터) : index를 확인할 node.
  • 반환 : (int)
    • 부모 node의 pointers에서 left node의 index.

  1. 부모 node의 pointers에서 left node가 몇 번째 index에 삽입되어 있는지 확인하고, 그 값을 반환한다.

node * insert_into_leaf( node * leaf, int key, record * pointer )

leaf node에 record를 삽입한다.

  • 인자
    • leaf (node 포인터) : 해당 record를 삽입할 leaf node.
    • key (int) : 삽입할 record의 key.
    • pointer (record 포인터) : 삽입할 record의 value를 가지고 있는 record 구조체.
  • 반환 : (node 포인터)
    • 삽입을 완료한 leaf node.

  1. leaf node에 이미 존재하는 record들 사이에서 입력받은 key가 삽입될 적절할 위치를 찾는다.
  2. 해당 위치를 비우기 위해 그 위치부터 그 이후의 record들을 한 칸씩 미루는 작업을 수행한다.
  3. 비운 위치에 입력받은 key와 pointer를 삽입한 후 leaf node를 반환한다.

node * insert_into_leaf_after_splitting(node * root, node * leaf, int key, record * pointer)

leaf node를 분할한 후 record를 삽입한다.

  • 인자
    • root (node 포인터) : 현재 tree의 root node.
    • leaf (node 포인터) : 해당 record를 삽입할 leaf node. 분할될 node.
    • key (int) : 삽입할 record의 key.
    • pointer (record 포인터) : 삽입할 record의 value를 가지고 있는 record 구조체.
  • 반환 : (node 포인터)
    • 분할과 삽입을 완료한 현재 tree의 root node.

  1. make_leaf 함수를 call하여 새로운 leaf node, new_leaf를 생성한다.
  2. record와 key값들을 저장할 임시 변수들을 동적할당한다. (node 구조체 형태는 아니나, 기본값보다 order가 1만큼 큰 1개 leaf node로 생각할 수 있다.) 할당과 할당 실패 시 처리 과정에서 stdio.h에 존재하는 perror 함수, stdlib.h에 존재하는 malloc, exit 함수가 call된다. 할당 실패 시, 오류 메시지를 출력하고 프로그램을 강제종료한다.
  3. leaf node에 이미 존재하는 record들 사이에서, 입력받은 record가 삽입될 적절한 위치를 찾는다.
  4. leaf node의 record와 key값들을 임시 변수에 복사하되, 위에서 찾은 위치를 비우고 해당 위치부터 그 이후 record와 key값들은 한 칸씩 뒤로 복사한다.
  5. 인자로 받은 record 포인터와 key를 임시 변수의 해당 위치에 삽입한다.
  6. cut 함수를 call하여 leaf node를 분할할 적절한 위치를 확인한다.
  7. 임시 변수로부터 분할될 왼쪽 절반 record와 key들을 leaf node로 복사한다.
  8. 임시 변수로부터 분할될 오른쪽 절반 record와 key들을 new_leaf(새로 생성한 leaf node)로 복사한다.
  9. stdlib.h에 존재하는 free 함수를 call하여 임시 변수를 할당 해제한다.
  10. new_leaf와 현재 leaf node가 가지는 값들을 최신화한다.
  11. insert_into_parent 함수를 call하여 new_leaf(새로 생성한 leaf node)를 부모 node에 삽입하고 그 결과를 반환한다.

node * insert_into_node(node * root, node * n, 
        int left_index, int key, node * right)

분할로 생성된 node를 부모 node에 삽입한다.

  • 인자
    • root (node 포인터) : 현재 tree의 root node.
    • n (node 포인터) : 삽입하려는 node의 부모 node.
    • left_index (int) : 삽입하려는 node의 왼쪽에 위치할 node가 부모 node에서 가지는 index.
    • key (int) : 삽입하려는 node와 그 왼쪽에 위치할 node 사이의 key.
    • right (node 포인터) : 삽입하려는 node.
  • 반환 : (node 포인터)
    • 삽입을 완료한 현재 tree의 root node.

  1. right node와 key가 삽입될 위치를 비우기 위해 해당 위치부터 그 이후 node와 key들을 한 칸씩 뒤로 미루는 작업을 수행한다.
  2. 해당 위치에 right node와 key를 삽입한 후, 현재 tree의 root node를 반환한다.

node * insert_into_node_after_splitting(node * root, node * old_node, int left_index, 
        int key, node * right)

부모 node를 분할하고 right node를 적절한 위치에 삽입한다.

  • 인자
    • root (node 포인터) : 현재 tree의 root node.
    • old_node (node 포인터) : 삽입하려는 node의 부모 node. 분할될 node.
    • left_index (int) : 삽입하려는 node의 왼쪽에 위치할 node가 부모 node에서 가지는 index.
    • key (int) : 삽입하려는 node와 그 왼쪽에 위치할 node 사이의 key.
    • right (node 포인터) : 삽입하려는 node.
  • 반환
    • 삽입을 완료한 현재 tree의 root node.

  1. 자녀 node와 key 값들을 저장할 임시 변수들을 동적할당한다. (node 구조체 형태는 아니나, 기본값보다 order가 1만큼 큰 1개 node로 생각할 수 있다.) 할당과 할당 실패 시 처리 과정에서 stdio.h에 존재하는 perror 함수, stdlib.h에 존재하는 malloc, exit 함수가 call된다. 할당 실패 시, 오류 메시지를 출력하고 프로그램을 강제종료한다.
  2. old_node의 자녀 node와 key들을 임시 변수에 복사하되, 삽입할 node와 key를 위한 공간을 비우고 해당 위치부터 그 이후 자녀 node와 key들은 한 칸씩 뒤로 복사한다.
  3. 인자로 받은 right node와 key를 임시 변수의 해당 위치에 삽입한다.
  4. cut 함수를 call하여 부모 node를 분할할 적절할 위치를 확인한다.
  5. make_node 함수를 call하여 새로운 node, new_node를 생성한다.
  6. 임시 변수로부터 분할될 왼쪽 절반 child와 key들을 old_node로 복사한다.
  7. 임시 변수로부터 분할될 오른쪽 절반 child와 key들을 new_node(새로 생성한 node)로 복사한다.
  8. stdlib.h에 존재하는 free 함수를 call하여 임시 변수를 할당 해제한다.
  9. new_node와 그 child들이 가지는 값들을 최신화한다.
  10. insert_into_parent 함수를 call하여 new_node(새로 생성한 node)를 old_node의 부모 node에 삽입하고 그 결과를 반환한다.

node * insert_into_parent(node * root, node * left, int key, node * right)

분할로 추가 생성된 node를 부모 node에 삽입한다.

  • 인자
    • root (node 포인터) : 현재 tree의 root node.
    • left (node 포인터) : 분할된 첫 번째 node. 이미 부모 node가 갖고 있음.
    • key (int) : 2개 node 사이의 key.
    • right (node 포인터) : 분할된 두 번째 node. 삽입할 node.
  • 반환 : (node 포인터)
    • 삽입을 완료한 현재 tree의 root node.

  1. 부모 node가 존재하지 않을 경우, 즉 root node가 분할된 상태일 경우, insert_into_new_root 함수를 call하여 새로운 root node를 생성하고 2개 node를 그에 삽입한다. 생성된 root node를 반환한다.
  2. get_left_index 함수를 call하여 부모 node에서 left node의 index를 확인한다.
  3. 부모 node에 right node가 삽입될 여유 공간이 있을 경우, insert_into_node 함수를 call하여 삽입을 수행하고 그 결과를 반환한다.
  4. 부모 node에 여유 공간이 없을 경우, 즉 분할이 필요할 경우, insert_into_node_after_splitting 함수를 call하여 부모 node의 분할을 동반한 삽입을 수행하고 그 결과를 반환한다.

node * insert_into_new_root(node * left, int key, node * right)

새로운 root node를 생성하고 분할된 2개 node(subtree)를 삽입한다.

  • 인자
    • left (node 포인터) : 분할된 첫 번째 node.
    • key (int) : 2개 node 사이의 key.
    • right (node 포인터) : 분할된 두 번째 node.
  • 반환 : (node 포인터)
    • 새롭게 생성하고 2개 node(subtree)의 삽입을 완료한 root node.

  1. make_node 함수를 call하여 새로운 node를 생성한다.
  2. node를 초기화하고 인자로 받은 2개 node(subtree)를 삽입한 후 이를 반환한다.

node * start_new_tree(int key, record * pointer)

처음 입력된 record를 가지는 새로운 tree를 생성한다.

  • 인자
    • key (int) : 삽입할 record의 key.
    • pointer (record 포인터) : 삽입할 record의 value를 담고 있는 record 구조체.
  • 반환 : (node 포인터)
    • 새롭게 생성하고 입력된 record의 삽입을 완료한 leaf node (root node).

  1. make_leaf 함수를 call하여 새로 만든 leaf node, root를 생성한다.
  2. root 구조체를 초기화하며 인자로 받은 record와 key값을 저장한 후, 이를 반환한다.

12. insert

node * insert( node * root, int key, int value )

현재 tree에 입력받은 record를 삽입한다.

  • 인자
    • root (node 포인터) : 현재 tree의 root node.
    • key (int) : 삽입할 record의 key.
    • value (int) : 삽입할 record의 value.
  • 반환 : (node 포인터)
    • 삽입을 완료한 현재 tree의 root node.

  1. find 함수를 call하여 입력받은 key와 동일한 key를 가진 record가 tree에 이미 존재하는지 여부를 확인한다. 존재할 경우, 삽입 작업을 중단하고 입력받은 tree의 root node 포인터를 그대로 반환한다. (즉, 중복 key를 허용하지 않는다.)
  2. make_record 함수를 call하여 입력받은 value를 가지는 새 record를 생성한다.
  3. 삽입할 tree가 비었는지 확인한다. 비어있을 경우, start_new_tree 함수를 call하여 입력받은 key와 새로 생성한 record를 가지고 새로운 tree를 생성한 후 이를 반환한다.
  4. find_leaf 함수를 call하여 입력받은 key를 포함하는 범위의 leaf node를 찾는다.
  5. 해당 leaf node에 key/record가 들어갈 여유 공간이 있는지 확인한다. 있을 경우, insert_into_leaf 함수를 call하여 해당 leaf node에 key/record를 삽입한 후, 현재 tree의 root node를 반환한다.
  6. 없을 경우, 즉 분할이 필요할 경우, insert_into_leaf_after_splitting 함수를 call하여, 해당 leaf node의 분할을 동반한 삽입을 수행하고 그 결과를 반환한다.


int get_neighbor_index( node * n )

입력받은 node의 왼쪽 형제 node의 index를 확인한다.

  • 인자
    • n (node 포인터) : 왼쪽 형제 node를 확인할 node.
  • 반환 : (int)
    • 입력받은 node의 왼쪽 형제 node의 index.

  1. 입력받은 node의 부모 node에서 입력받은 node의 index를 확인하고, (해당 index) - 1, 즉 해당 node의 왼쪽 형제 node의 index을 반환한다. (해당 node가 가장 왼쪽 node였을 경우 -1이 반환된다.)
  2. 확인에 실패했을 경우, 오류 메시지를 출력하고 프로그램을 강제종료한다. 강제종료 시 stdlib.h에 존재하는 exit 함수가 call된다.

node * remove_entry_from_node(node * n, int key, node * pointer)

node n에서 입력받은 key와 포인터를 삭제한다.

  • 인자
    • n (node 포인터) : 삭제할 것들이 들어있는 node.
    • key (int) : 삭제할 key.
    • pointer (node 포인터) : 삭제할 포인터.

  1. 삭제할 key와 포인터 이후의 key와 포인터들을 한 칸씩 당겨서 덮어씨운다.
  2. node n의 정보를 최신화한 후 반환한다.

node * adjust_root(node * root)

삭제가 발생한 root node를 조정한다.

  • 인자
    • root (node 포인터) : 조정할 root node.
  • 반환 : (node 포인터)
    • 조정 완료한 root node.

  1. root node가 비었는지 확인한다. 비어있지 않을 경우, 그대로 반환한다.
  2. root node가 leaf node인지 확인한다. leaf node가 아닐 경우 단 하나 있는 첫 번째 자녀 node를 새로운 root node로 둔다.
  3. leaf node일 경우 새로운 root node를 NULL로 둔다.
  4. stdlib.h에 존재하는 free 함수를 call하여 기존의 root node와 그 멤버 변수들을 할당 해제한다.
  5. 새로운 root node를 반환한다.

node * coalesce_nodes(node * root, node * n, node * neighbor, int neighbor_index, int k_prime)

node n과 형제 node를 병합한다.

  • 인자
    • root (node 포인터) : 현재 tree의 root node.
    • n (node 포인터) : 병합할 node.
    • neighbor (node 포인터) : node n과 함께 병합할 형제 node.
    • neighbor_index (int) : neighbor의 index.
    • k_prime (int) : 두 node 사이의 key.
  • 반환 : (node 포인터)
    • 병합을 완료한 현재 tree의 root node.

  1. 형제 node가 node n의 오른쪽 형제 node일 경우, 서로 포인터 값을 바꾼다. 즉, 서로 병합할 node 2개 중 왼쪽 node는 형제 node 포인터에, 오른쪽 node는 n node 포인터에 저장되도록 한다.
  2. 두 node가 leaf node가 아닐 경우, 두 node 사이의 key인 k_prime을 형제 node가 가진 key들 제일 끝에 삽입하고, 이후 n node의 key와 포인터들을 형제 node로 옮긴다. 형제 node가 가진 포인터들이 형제 node를 부모 node로 가리키도록 최신화한다.
  3. 두 node가 leaf node일 경우, n node의 key와 포인터들을 형제 node로 옮긴다. n node가 다음 node로 가리키던 node를 형제 node가 다음 node로 가리키도록 한다.
  4. delete_entry 함수를 call하여, n node를 삭제하고 반환된 root node를 현재 tree의 root node에 저장한다.
  5. stdlib.h에 존재하는 free 함수를 call하여 n node와 그 멤버 변수들을 할당 해제한다.
  6. 현재 tree의 root node를 반환한다.

node * redistribute_nodes(node * root, node * n, node * neighbor, int neighbor_index, 
        int k_prime_index, int k_prime)
  • 인자
    • root (node 포인터) : 현재 tree의 root node.
    • n (node 포인터) : 최소 key 개수에 미달하여 재분배가 필요한 node.
    • neighbor (node 포인터) : node n과 함께 재분배를 실시할 형제 node.
    • neighbor_index (int) : neighbor의 index.
    • k_prime (int) : 두 node 사이의 key.
  • 반환 : (node 포인터)
    • 재분배를 완료한 현재 tree의 root node.

  1. 형제 node가 node n의 왼쪽일 경우, 형제 node의 가장 오른쪽 끝의 key/pointer 쌍을 node n의 가장 왼쪽 끝으로 옮긴다.
  2. node n이 가장 왼쪽 node, 즉 형제 node가 node n의 오른쪽일 경우, 형제 node의 가장 왼쪽 끝의 key/pointer 상을 node n의 가장 오른쪽 끝으로 옮긴다.
  3. node n과 형제 node의 정보를 최신화한 후 현재 tree의 root node를 반환한다.

node * delete_entry( node * root, node * n, int key, void * pointer )

현재 tree에서 입력받은 record/node를 삭제한다.

  • 인자
    • root (node 포인터) : 현재 tree의 root node.
    • n (node 포인터) : 삭제할 record/node를 가진 node.
    • key (int) : 삭제할 record/node의 key.
    • pointer (void) : 삭제할 record/node 포인터.
  • 반환 : (node 포인터)
    • 삭제를 완료한 현재 tree의 root node.

  1. remove_entry_from_node 함수를 call하여 node n에서 입력받은 record/node를 삭제한다.
  2. node n이 현재 tree의 root node일 경우, adjust_root 함수를 call하여 root node를 조정하고 그대로 반환한다.
  3. node n의 key 개수가 현재 order에 따른 최소 key 개수 이상인지 확인한다. 확인 과정에서 cut 함수를 call하여 이용하며, key 개수가 최소 key 개수 이상일 경우 현재 root node를 그대로 반환한다.
  4. 병합하기에 적절한 형제 node를 찾는다. 이 과정에서 get_neighbor_index 함수를 call하여 사용한다. 병합해도 최대 key 개수를 넘지 않는 형제 node를 찾았을 경우, coalesce_nodes 함수를 call하여 병합을 실행하고 그 결과를 반환한다.
  5. 형제 node가 병합하기에 적절하지 않을 경우, redistribute_nodes 함수를 call하여 재분배를 실행하고 그 결과를 반환한다.

7. delete

node * delete(node * root, int key)

현재 tree에서 입력받은 key를 가지는 record를 삭제한다.

  • 인자
    • root (node 포인터) : 현재 tree의 root node.
    • key (int) : 삭제할 record의 key.
  • 반환 : (node 포인터)
    • 삭제를 완료한 현재 tree의 root node.

  1. find 함수를 call하여 현재 tree에서 입력받은 key를 가진 record를 저장한다.
  2. find_leaf 함수를 call하여 현재 tree에서 입력받은 key를 포함하는 범위의 leaf node를 저장한다.
  3. 현재 tree에서 입력받은 key를 가진 record와 이 record를 가진 leaf node가 정상적으로 존재하는지 확인한다. 존재할 경우, delete_entry 함수를 call하여, 해당 record를 삭제하고 반환된 root node를 현재 tree의 root node에 저장한다.
  4. stdlib.h에 존재하는 free 함수를 call하여 해당 record를 할당 해제한다.
  5. 현재 tree의 root node를 반환한다.

void destroy_tree_nodes(node * root)

node * destroy_tree(node * root)

Clone this wiki locally