B-트리 #2. 삭제

삽입 검색 알고리즘에 이어 삭제 알고리즘을 알아보자.
삭제가 수행된 B-트리가 계속 B-트리의 성질을 유지하기 위해서는 키가 삭제된 뒤에도 최소한의 키 수가 되는지를 확인해야 된다. 만일 해당 노드가 최소한으로 유지해야 될 키 수보다 작게 되는 경우에는 적절한 조치를 취해줘야 한다.

삭제를 위해서는 삽입에서와 같이 먼저 삭제하려는 키 값이 들어있는 노드를 탐색한다.
만일 삭제하려는 키 값이 내부 노드에 있다면 리프 노드에 있는
이 키 값의 후행(Successor) 키 값과 교환을 한 뒤에 리프 노드에서 삭제한다.

삭제 후 노드가 유지해야 될 최소 키 값의 수가 만족하지 않으며 재분배(Redistribution)나 합병(Merge) 방법을 이용하여 최소 키 값 수를 유지하도록 해야 한다.

▣ 재분배(Redistribution) : 해당 노드의 오른쪽이나 왼쪽 형제 노드에 최소 키 값 수보다
                                     많은 키 값들이 있는 노드를 선택하여 그 노드로부터 한 개의
                                     키 값을 차출하여 이동시키는 것.
                                     이 방법은 부모 노드에 있던 키 값을 해당 노드로 이동시키고
                                     이 부모 노드에 있던 키 값 자리에 차출된 형제 노드의 키 값을
                                     이동시킨다.
▣ 합병(Merge) : 형제 노드들이 최소의 키 값만을 가지고 있으면 재분배 방법을 사용할 수
                        없으므로 합병을 하게 된다. 
                        해당 노드의 형제 노드에 있는 키 값들과 이 두 노드를 분리시키는
                        부모 노드의 키 값을 모두 모으는 작업으로써 합병 결과로 공백이 된
                        노드는 제거한다. 합병이 수행되면 트리 구조가 변경된다.

/* 알고리즘에서 사용된 변수는 다음과 같다.
     Finished : 삭제가 완료되었음을 나타내는 플래그
     Tempnode : 재분배를 위해 사용되는 정상 노드보다 50% 큰 노드
     Sibling : 인접 형제 노드
     D-key : B-트리에서 삭제될 키
*/
search tree for D-key forming stack of node addresses;
// 자세한 것은 삽입 알고리즘 참조

if( D-key is not in terminal node ){
     search for successor key of D-key at terminal level (stacking node addresses);
     copy seccessor over D-key;
     terminal node successor now becomes the D-key;
}
/* 키를 삭제하고 트리를 재조정한다. */
Finished = FALSE;
do{
     remove D-key;
     if( current node is root or is not too small)
          Finished = TRUE;
     else if( redistribution possible){
          /* Sibling > minimum이 성립할 때 재분배 가능
              재분배 실행 */
          copy "best" Sibling, intermediate parent key, and
          current (too-small0 node into Tempnode;
          copy keys and pointers from Tempnode to "best"
               Sibling, parent, and current node so Sibling and
               from the parent;
          discard rightmost of the two nodes;
          intermediate key in parent now becomes D-key;
     }
}while( !Finished );

if( no keys in root){
     // 트리의 레벨이 하나 감소된다.
     new root is the node pointed to by the current root;
     discard old root;
}