[알고리즘]B-Tree Deletion

□ B-Tree의 Deletion의 법칙

1.  underflow 안일어날때

    : 그냥 하나씩 삭제해서 밀어넣어주면 됨

2. underflow 일어날때

   1) " underflow가 일어난 노드의 형제 노드의 수 > 최소한 가져야 하는 레코드 수" 라면 Redistribution 

       Redistribution : 부모에서 underflow 노드 채우고 다른 형제 노드에서 나간 자리에 채우기

   2) "underflow가 일어난 형제 노드의 수 < 최소한 가져야 하는 레코드 수 " 라면 Merge

       Merge : 부모가 내려오면서 부모에 딸린 노드들을 다 합침 

 

 

 

□ B-Tree의 Deletion 구현 (파이썬) 

int B_tree_deletion(char* out_key) {
	nodeptr  curr, r_sibling, l_sibling, father, Pt, leftptr, rightptr;
	int i, j, k, r_OK, l_OK, found = 0, finished = 0;
	curr = root;

	// Step (0): search for a record (to be deleted) whose key equals out_key.
	do {
		for (i = 0; i < curr->fill_cnt; i++) {
			if (strcmp(out_key, curr->rec[i].name) < 0)
				break;
			else if (strcmp(out_key, curr->rec[i].name) == 0) {
				found = 1;
				break;
			}
		}
		if (found == 1)
			break;  // 주의: 변수 i에 찾은 위치가 들어 있음.
		else {      // curr에 없다. child로 내려 가야 한다.
			Pt = curr->ptr[i];
			if (Pt) {
				push(curr);
				curr = Pt;
			}
			else
				break;
		}
	} while (!found);
	if (!found) {
		return 0;
	}

	// Comes here when the key is found. It is in curr's node. i has index of rec to delete.
	// Step (1):  find successor of d_rec.
	if (curr->ptr[0]) {   // curr node is not a leaf node  
	   // We need to find successor of out_key ;
		Pt = curr->ptr[i + 1];
		push(curr);
		// 가장 왼쪽 포인터를 따라내려 간다.
		while (Pt->ptr[0]) {
			push(Pt);
			Pt = Pt->ptr[0];
		}

		curr->rec[i] = Pt->rec[0];
		curr = Pt;
		strcpy(out_key, Pt->rec[0].name);
		i = 0;
	} //end if

	// curr 노드에서 index 가 i 인 레코드와 그 우측 포인터를 삭제하여야 한다.
	finished = false;
	do {
		// Step (2):
		//Remove record of index i and a pointer to its right from curr's node; 
		for (j = i + 1; j < curr->fill_cnt; j++) {
			curr->rec[j - 1] = curr->rec[j];
			curr->ptr[j] = curr->ptr[j + 1];
		}
		curr->fill_cnt = curr->fill_cnt - 1;

		// Step (3):
		if (curr == root) {
			if (curr->fill_cnt == NULL) {
				root = root->ptr[0];
				free(curr);
			}
			return 1; // deletion succeeded.
		}

		// Step (4):
		// curr is not the root. 
		if (curr->fill_cnt >= HALFK) { return 2; } // Finish deletion with success.

		// Now, curr violates minimum capacity constraint.
		// Step (5):
		father = pop(); // bring father of curr.
		// r-sibling = pointer to right sibling of curr' node; 
		// l-sibling = pointer to left sibling of curr's node;
		for (j = 0; j <= father->fill_cnt; j++) {
			if (father->ptr[j] == curr) // find ptr of father which goes down to curr.
				break;
		}
		if (j >= 1)
			l_sibling = father->ptr[j - 1];
		else
			l_sibling = NULL;
		if (j < father->fill_cnt)
			r_sibling = father->ptr[j + 1];
		else
			r_sibling = NULL;

		// 주의: father 의 ptr[j] 가 curr 과 같음
		//  r_sibling or l_sibling  중 하나가 d 보다 많은 레코드 가지면 재분배 가능함!
		r_OK = 0;  l_OK = 0;
		if (r_sibling && r_sibling->fill_cnt > HALFK)
			r_OK = 1;
		else if (l_sibling && l_sibling->fill_cnt > HALFK)
			l_OK = 1;

		if (r_OK || l_OK) {
			//if (r_sibling has more than d keys) {
			if (r_OK) {
				redistribution(father, curr, r_sibling, 'R', j);
			}
			else if (l_OK) {
				redistribution(father, l_sibling, curr, 'L', j);
			}
			printf("Redistribution has been done.\n");
			return 3; // Deletion succeeded with redistribution.
		}
		else {   //  Step 6: merging (합병이 필요함)
		   //  Let leftptr be a pointer to left one of curr and sibling chosen to merge ;
		   //  Let rightptr point to the right one of curr and sibling chosen to merge ;
			if (r_sibling) {
				leftptr = curr;
				rightptr = r_sibling;
			} // r_sibling exists.
			else {
				leftptr = l_sibling;
				rightptr = curr;
			} // surely l_sibling exists.

			//   아래 빈 곳은 leftptr, rightptr 두 형제를 leftptr 형제로 합병하는 부분이 와야 함!! 
			//   주의: 변수 i 가 두 형제 사이의 father 내의 중간 레코드를 가리키게 해 놓아야 함.
			for (i = 0; i < father->fill_cnt; i++) {
				if (father->ptr[i] == leftptr) {
					break;
				}
			}
			j = leftptr->fill_cnt;
			leftptr->rec[j] = father->rec[i];
			j++;
			for (k = 0; k < rightptr->fill_cnt; k++, j++) {
				leftptr->ptr[j] = rightptr->ptr[k];
				leftptr->rec[j] = rightptr->rec[k];
			}
			leftptr->ptr[j] = rightptr->ptr[k];
			//leftptr->fill_cnt += 1 + rightptr->fill_cnt;
			leftptr->fill_cnt = j;
			free(rightptr);


			curr = father;
			// Note that i has index of record in father to be deleted. 
			// Deletion of this record and pointer to its right will be done at start of next iteration.
		} // else.
	} while (!finished);  // end of do-while 문.

} // B_tree_deletion