アルゴリズム入門講座: 2分探索木の削除のやり方をc++で学ぶ

ALDS1_8_Cを参考にして2分探索木の削除方法を学んでいきます。
問題文の2分探索木の削除に関するアルゴリズムを抜粋します。

2分探索木から与えられたキーkを持つ節点zを削除するdelete kは、
以下の3つの場合を検討したアルゴリズムに従い、
2分探索木条件を保ちつつ親子のリンク(ポインタ)を更新します。

1.zが子を持たない場合、zの親pの子（つまりz）を削除する。
2.zが1つの子を持つ場合、zの親の子をzの子に変更、
zの子の親をzの親に変更し、zを木から削除する
3.zが子を2つ持つ場合、zの次節点yのキーをzのキーへコピーし、yを削除する。
yの削除では1.または2.を適用する。
ここで、zの次節点とは、中間順巡回でzの次に得られる節点である。

問題では削除する節点としてzを引数として受け取ります。
削除する節点の候補をyとして
削除するyの子をxとして
図で各々のケースを確認してみます。

子を持たないケース(case1)

1をkeyにもつノードを削除したいとします。
ノード1は子を持たないので、繋ぎ直しをする必要がありません。
よって、そのまま消すことができます。

       0
  1(z = y)

子を1つ持つケース(case2)

12をキーにもつノードを削除したいとします。 12は左の子を持っています。

            30
  12(z = y)               88
1(x)

12をキーにもつノードを削除したいとします。 12は右の子を持っています。

            30
  12(z = y)               88
        15(x)

子を2つ持つケース(case3)

0をキーにもつノードを削除したいとします。
0は下図のような子を持っています。

       0(z)
  1      4
2 3   5(y) 8        
           7(x)

削除する節点yを決める

case1,2の場合はyをzそのものにします。

case3の場合は、中間順巡回でzの次に訪問される節点にします。

削除する節点yの1つの子xを決める

case1の場合は右の子(NIL)
case2の場合はNILでない子
case3の場合はzの次節点の右の子(次節点は最小値なのでに左の子は存在しない)になります。

削除する節点yの親子のポインタを繋ぎ変えてyを削除する

xの親がyの親になるようにポインタを繋ぎ変えます。

yの親の子がxになるようにポインタを繋ぎ変える

yが根のケースなのか、(yの親の)左の子なのか右の子なのかを調べて
ポインタを繋ぎ変えます。

最後に、case3限定でzのキーにyのキーを設定します。

プログラムの部品

続いて、部品となるプログラムをみていきます。
まずは、次節点を返すgetSuccessor関数です。

Node* getTreeSuccessor(Node *x){
    // xに右の子が存在する場合右部分木でキーが最も小さい節点xの次節店にあんる
    if(x->right != NIL)return getMinimumTree(x->right);
    // 右の子が存在しない場合
    Node *y = x->parent;
    while(y != NIL && x == y->right){
        x = y;
        y = y->parent;
    }
    return y;
}

右の子が存在しない場合、親をたどっていき、
最初に左の子になっている節点の親が次節点になります。
節点に次節点が存在しない場合(木の中でxが最大のキーを持つ場合)はNILを返します。

2分探索木の節点xを根とする場合の最小のキーを持つ節点を返す
getMinimumTree関数です

Node* getMinimumTree(Node *x){
    while(x->left != NIL) x = x->left;
    return x;
}

では、ALDS1_8_Cの問題に合わせたプログラムです。
削除するdeleteTree関数では、上記の手順で書いています。

#include <stdio.h>
#include <iostream>
#include <cstdlib>
using namespace std;

struct Node {
    int key;
    Node *left,*right,*parent;
};

Node *gRoot,*NIL;

Node* getMinimumTree(Node *x){
    while(x->left != NIL) x = x->left;
    return x;
}

Node* getTreeSuccessor(Node *x){
    if(x->right != NIL)return getMinimumTree(x->right);
    Node *y = x->parent;
    while(y != NIL && x == y->right){
        x = y;
        y = y->parent;
    }
    return y;
}

void deleteTree(Node *z){
    Node *y;    // 削除対象Node
    Node *x;    // yの子
    
    // 子がない場合はまたは一つしか子がない場合は対象の節点をそのまま消す
    if(z->left == NIL || z->right == NIL){
        y = z;
    }
    else{
        y = getTreeSuccessor(z);
    }
    
    // yの子xを求める
    if(y->left != NIL){
        x = y->left;
    }
    else{
        x = y->right;
    }
    
    if(x != NIL){
        x->parent = y->parent;
    }
    
    if(y->parent == NIL){
        gRoot = x;
    }else{
        if(y == y->parent->left){
            y->parent->left = x;
        }else{
            y->parent->right = x;
        }
    }
    
    if(y != z){
        z->key = y->key;
    }
    free(y);
}

Node *find(Node* u,int value){
    while(u != NIL && value != u->key){
        if(value < u->key) u = u->left;
        else u = u->right;
    }
    return u;
}

void insert(int value){
    Node *y = NIL;
    // 親
    Node *x = gRoot;
    // 自身
    Node *z;
    z = (Node*)malloc(sizeof(Node));
    z->key = value;
    z->left = NIL;
    z->right = NIL;
    
    // rootから自身を挿入する場所を探す
    while(x != NIL){
        // rootから検索
        y = x;
        if(z->key < x->key){
            x = x->left;
        }else{
            x = x->right;
        }
    }
    
    z->parent = y;
    // 親に子を持たせる
    if(y == NIL){
        gRoot = z;
    }else{
        if(z->key < y->key){
            y->left = z;
        }else{
            y->right = z;
        }
    }
}
// 先行順巡回
void preOrder(Node *u){
    if(u == NIL)return;
    printf(" %d",u->key);
    preOrder(u->left);
    preOrder(u->right);
}

// 中間順巡回
void inOrder(Node *u){
    if(u == NIL)return;
    inOrder(u->left);
    printf(" %d",u->key);
    inOrder(u->right);
}

int main(){
    int n,x;
    string com;
    
    cin >> n;
    for(int i = 0;i < n;++i){
        cin >> com;
        if(com[0] == 'f'){
            cin >> x;
            Node *t = find(gRoot,x);
            if(t != NIL) cout << "yes\n";
            else cout << "no\n";
        }
        if(com == "insert"){
            cin >> x;
            insert(x);
        }
        else if(com == "print"){
            inOrder(gRoot);
            cout << "\n";
            preOrder(gRoot);
            cout << "\n";
        }
        else if(com == "delete"){
            cin >> x;
            deleteTree(find(gRoot,x));
        }
    }
    return 0;
}

参考ソース https://book.mynavi.jp/ec/products/detail/id=35408

アルゴリズム入門講座

2018年2月10日土曜日

2分探索木の削除のやり方をc++で学ぶ