[C]B-TREE(3)

次に、ノードのマージと削除の手順を見てみましょう.

3.ノードを結合して鍵を取得する

鍵を削除する演算が実行されても、B−TREE属性の1つである「すべてのノードにt(最小回数)−1つ以上の鍵が必要」である.満たさなければならない.したがって、削除操作を実行するノードの鍵数がt−1である場合、ノードの鍵数をt個以上に増やす必要がある.
このとき,ノード鍵の数を増やす方法は2つある.
(1隣接する兄弟ノードから鍵を取得するか、(2)隣接する兄弟ノードとマージする.
この2つの方法のどちらを使用するかは、兄弟ノードの鍵の数に依存します.
(1)兄弟ノードの鍵の個数がt個より大きい場合,1個だけ取得しても鍵の個数はt−1個を満たすので,鍵の取得方法を選択する.
(2)ただし,兄弟ノードの鍵数がt−1個である場合,鍵を1個入力すると,前述した最小鍵数を満たすことができない.したがって、2つのノードを結合します.
マージ時には、取得した親ノードの1つの鍵がマージされ、マージされたターゲットノードの個数がt-1であるため、2つのノードをマージして親ノードの1つの鍵を取得しても、キーの個数は、マージの場合にノードが持つ最大鍵の個数を超えない.
(1)兄弟ノードから鍵をインポート
まず,隣接する兄弟ノードから鍵のコードを取得する.この場合、左側の兄弟ノードからインポートするか、右側の兄弟ノードからインポートすることができます.
兄弟ノードから鍵を取得する場合、兄弟ノードの鍵を直接取得するのではなく、兄弟ノードから取得する鍵と親ノードを2つのサブノードの基準とする鍵を変更し、親ノードから基準鍵を取得します.
下図のように.
このとき、親の身長を下げる理由は、兄弟の身長をそのまま持ってくると、身長を基準に子どもを並べ替えるB-TREEの性質に反するためだ.
次のプロセスでは、兄弟ノードから直接12が導入されると、14と17の間のサブノードは12を含み、これはB−TREEの性質に反する.

void move_key_right_to_left(node *left_child, node *right_child, int *parent_key) {
    left_child->key[MIN_DEGREE] = *parent_key; //부모의 키를 가져오고
    left_child->key_count += 1; //왼쪽 노드의 키의 개수 증가
    *parent_key = right_child->key[1]; //부모의 키를 오른쪽 형제노드에서 가져온 키로 바꿔주기
    right_child->key_count -= 1; //오른쪽 노드의 키의 개수를 감소
    left_child->linker[MIN_DEGREE + 1] = right_child->linker[1];//오른쪽노드에서 자식 가져오기
    
    //오른쪽 노드에서 가장 앞에 있던 키가 없어졌으므로 키와 자식 한칸씩 당겨주기
    for (int j = 1; j <= right_child->key_count; j++) {
        right_child->key[j] = right_child->key[j + 1];
    }
    //리프노드이면 자식이 없기 때문에 리프노드가 아닐 때만 자식을 옮겨준다.
    if (!left_child->is_leaf) {
        for (int j = 1; j <= (right_child->key_count) + 1; j++ ) {
            right_child->linker[j] = right_child->linker[j + 1];
        }
    }
}

void move_key_left_to_right(node *left_child, node *right_child, int *parent_key) {
    for (int j = right_child->key_count; j >= 1; j--) {
        right_child->key[j + 1] = right_child->key[j];
    }
    int left_sibling_key_count = left_child->key_count;
    if (!right_child->is_leaf){
        for (int j = (right_child->key_count) + 1; j >= 1; j--) {
            right_child->linker[j + 1] = right_child->linker[j];
        }
        right_child->linker[1] = left_child->linker[left_sibling_key_count + 1];
    }
    right_child->key_count += 1;
    right_child->key[1] = *parent_key;
    *parent_key = left_child->key[left_sibling_key_count];
    left_child->key_count -= 1;
}

(2)兄弟ノードのマージ
マージを行うと、親はマージする2つのサブノードを区切る基準となるキーを置いて、2つのノードをマージするようにマージします.
このとき親の身長を下げるのもB-TREEの性格に背かないためです.
下図のように.
このとき親の身長17を下げて合併しなければ順位も正しくなく、親の身長は2個、子供も2個となってB-TREEの性格に反する.

void merge_node(node *parent, node *left_child, node *right_child, int index) {
    //왼쪽 자식의 끝에 부모의 키를 내린다.
    left_child->key[left_child->key_count + 1] = parent->key[index];
    //부모의 키를 내렸으니 부모의 키와 자식을 한칸씩 당겨준다.
    for (int j = index; j < parent->key_count; j++) {
        parent->key[j] = parent->key[j + 1];
    }
    for (int j = index + 1; j <= parent->key_count; j++) {
        parent->linker[j] = parent->linker[j + 1];
    }
    parent->key_count -= 1;
    
    //오른쪽 자식의 키를 모두 왼쪽 자식으로 옮겨준다.
    for (int j = 1; j <= right_child->key_count; j++) {
        left_child->key[MIN_DEGREE + j] = right_child->key[j];
    }
    if (!left_child->is_leaf) {
        for (int j = 1; j <= (right_child->key_count) + 1; j++) {
            left_child->linker[MIN_DEGREE + j] = right_child->linker[j];
        }
    } 
    
    //왼쪽 자식의 키의 개수 증가시킨다. 이때 왼쪽자식의 키의 개수는 항상 2t - 1개이다.
    left_child->key_count += (right_child->key_count + 1);
    
    //오른쪽 자식은 더이상 사용하지 않기 때문에 메모리를 해제한다. 
    free(right_child);
}

4.削除

まず、削除演算の一般的な手順は次のとおりです.
削除する鍵が見つかった後、出会ったノードの鍵数がt-1個の場合、兄弟ノードから鍵を取得するか、結合鍵をt個以上にして降格させる.
キーをt個以上に設定しておくのは、削除や再アップロードの回数を最小限に抑えるためです.
例えば、削除鍵を含むノードの鍵数がt−1個であり、隣接する兄弟ノードの鍵数もt−1個である場合、削除のためにマージする必要がある.
ただし、親ノードの鍵数もt-1個であると、親ノードから鍵を取得できないため、親ノードの鍵数をt個以上に再調整する必要がある.
従って、下から出会ったノードの鍵数をt個以上に繰り上げて調整すれば、上記の例のように親ノードに戻ることを回避することができる.
削除演算は2つのケースで行われます.
(1)リーフノードから削除,(2)内部ノードから削除.
このとき,内部ノードとはリーフノード以外のすべてのノードを指す.
(1)リーフノードから削除
リーフノードから削除する場合は,鍵を削除するだけでよい.
上から降りて出会ったすべてのノードの鍵の個数をt個以上に調整したので,直接削除しても鍵の最小個数t−1個を満たす.
(2)内部ノードからの削除
内部ノードから削除する場合も、左、右のサブノードのキーがtより大きいか、tでないかの2つに分けられます.
     (2)-1左側または右側のサブノードのキーはtより大きい.
左サブキーの個数がtより大きい場合は、先頭キー(Inorder Predeccessor)が検索され、右サブキーの個数がtより大きい場合は、後ガイド(Inorder Successor)が検索され、削除されたキーに格納され、次に、見つかった先頭キー、後ガイドキーが削除演算される.
このとき、リーフノードには、プリアンブル、ポストガイドが存在する.
下図のように.
1.内部ノードでプリアンブルを検索して10を削除します.このとき,10のプリアンブルは18であり,リーフノード上に存在する.
2.次に10を18に変更し、リーフノード上の18を削除演算する.

このとき、前キーと後キーを検索するコードは以下のようになります.
プリアンブルキーを検索するには、削除するキーの左側のサブノードにドロップし、リーフノードに遭遇するまでそのノードの一番右側のサブノードにドロップします.リーフノードに到達すると、そのノード上の最大のキーがプリアンブルとなる.
後続のキーを探すときは、下がる方向が逆になるだけで、方法は同じです.

int PRED (node *pred_child) {
    if (pred_child->is_leaf) {
        return pred_child->key[pred_child->key_count];
    } else {
        return PRED(pred_child->linker[(pred_child->key_count) + 1]);
    }
}

int SUCC (node *succ_child) {
    if (succ_child->is_leaf) {
        return succ_child->key[1];
    } else {
        return SUCC(succ_child->linker[1]);
    }
}

     (2)-2隣接するサブノードの鍵はすべてt-1である.
この場合、隣接する2つのサブノードを結合し、内部ノードの鍵を削除できます.
下図のように.

次に、削除演算に使用するコードを示します.
上記の手順に従って、ルートノードの鍵がマージまたは削除プロセスによってすべて消えた場合は、ルートの更新に注意するだけでよい.

void b_tree_delete(node *sub_root, node **root, int k) {
    if ((*root)->key_count == 0) {
        if ((*root)->is_leaf) {
            printf("tree is empty\n");
            return;
        }
    }
    node_delete(sub_root, k);
    if ((*root)->key_count == 0) {
        if ((*root)->is_leaf) {
            printf("tree is empty\n");
            free(*root);
            b_tree_create(root);
            return;
        }
        else {
            node *old_root = *root;
            *root = (*root)->linker[1];
            free(old_root);
            return;
        }
    }
}

void node_delete(node *sub_root, int k) {
    if (sub_root->is_leaf){
        int original_key_count = sub_root->key_count;
        for (int i = 1; i <= sub_root->key_count; i ++) {
            if (sub_root->key[i] == k){
                for (int j = i; j < sub_root->key_count; j ++) {
                    sub_root->key[j] = sub_root->key[j + 1];
                }
                sub_root->key_count -= 1;
            }
        }
        if (original_key_count == sub_root->key_count) {
            printf("%d not in b-tree\n", k);
        }
        return;
    } 
    int i = 1;
    while(sub_root->key[i] <  k && i <= sub_root->key_count) {
        i += 1;
    }
    if (sub_root->key[i] == k && i <= sub_root->key_count) {
        node *left_child = sub_root->linker[i];
        node *right_child = sub_root->linker[i + 1];
        if (left_child->key_count >= MIN_DEGREE) { 
            int pred = PRED(left_child);
            sub_root->key[i] = pred;
            node_delete(left_child, pred);
            return;
        }
        else if (right_child->key_count >= MIN_DEGREE) { 
            int succ = SUCC(right_child);
            sub_root->key[i] = succ;
            node_delete(right_child, succ);
            return;
        } else {
            merge_node(sub_root, left_child, right_child, i);
            node_delete(left_child, k);
            return;
        }
        return;
    }
    if (i == sub_root->key_count + 1) { 
        node *left_child = sub_root->linker[i - 1];
        node *right_child = sub_root->linker[i];
        if (sub_root->linker[i]->key_count >= MIN_DEGREE) { 
            node_delete(sub_root->linker[i], k);
            return;
        }
        if (sub_root->linker[i - 1]->key_count >= MIN_DEGREE) { 
            move_key_left_to_right(left_child, right_child, &(sub_root->key[i - 1]));
            node_delete(right_child, k);
            return;
        }
        else { 
            merge_node(sub_root, left_child, right_child, i - 1);
            node_delete(left_child, k);
            return; 
        }
        return;
    }
    else {
        node *left_child = sub_root->linker[i];
        node *right_child = sub_root->linker[i + 1];
        if (sub_root->linker[i]->key_count >= MIN_DEGREE) { 
            node_delete(sub_root->linker[i], k);
            return;
        }
        if (sub_root->linker[i + 1]->key_count >= MIN_DEGREE) { 
            move_key_right_to_left(left_child, right_child, &(sub_root->key[i]));
            node_delete(left_child, k);
            return;
        }
        else {
            merge_node(sub_root, left_child, right_child, i);
            node_delete(sub_root->linker[i], k);
            return;
        }
        return;
    }
}

次に、実装されたツリーを出力するコードを示します.
DFSとして実装される.

void display(node *cur_node, int blanks) {
    int i;
    if (cur_node->key_count == 0) {
        printf("tree is empty\n");
        return;
    }
    if (cur_node->is_leaf) {
        for (i = 1; i <= cur_node->key_count; i++) {
            for (int j = 1; j <= blanks; j ++)
                printf("---!");
            printf("%d\n", cur_node->key[i]);
        }
        return;
    }
    for (i = 1; i <= cur_node->key_count; i++) {
        display(cur_node->linker[i], blanks + 1);
        for (int j = 1; j <= blanks; j ++)
            printf("---!");
        printf("%d\n", cur_node->key[i]);
    }
    display(cur_node->linker[i], blanks + 1);
    return;
}

今週のテーマはとても面白くて、時間がどのように過ぎたのか分かりません.
フィードバックを歓迎します.
-終了-