2分木のノード削除

個人開発したアプリの宣伝
目的地が設定できる手帳のような使い心地のTODOアプリを公開しています。
Todo with Location

Todo with Location

  • Yoshiko Ichikawa
  • Productivity
  • Free

binary treeのノード削除

削除対象のノードの子が左右両方にある場合、削除後、親要素にどちらの要素をぶら下げれば良いか?

     10
   5     15
 2   6      17
1 3     

というツリーがあった場合、ノード5を削除した場合、どういうツリーになるか?という話し。

答え:子左要素の最大値をもってくる

上記の例でいうと5の左子ノード2の最大値ノード3を移動する。

つまりこういう状態になる。

     10
   3     15
 2   6      17
1      

ノード削除のサンプルコード

int delete_tree(int val){
    tree_node *node, *parent_node;
    tree_node *left_biggest;
    int direction = 0;
    node = tree_root;
    parent_node = NULL;
    
    while(node!=NULL && node->value!=val){
        if( node->value > val ){
            parent_node = node;
            node = node->left;
            direction = -1;
        }else{
            parent_node = node;
            node = node->right;
            direction = 1;          
        }
    }
    if( node == NULL ){
        return 0;
    }
    if( node->left == NULL || node->right == NULL ){
        if( node->left == NULL ){
            //親から見て削除nodeは左にある
            if( direction == -1 ){
                parent_node->left = node->right;
            }
             if( direction == 1 ){
                parent_node->right = node->right;
            }
            if( direction == 0 ){
               tree_root = node->right;
            }
        }
        else{
            if( direction == -1 ){
                parent_node->left = node->left;
            } 
            if( direction == 1 ){
                parent_node->right = node->left;
            }
            if( direction == 0 ){
               tree_root = node->left;
            }
        }
        free(node);
    }else{
        //削除対象に左右両方に子孫がある場合はleft側の最大値を持つ要素と入れ替える
        left_biggest = node->left;
        parent_node = node;
        direction = -1;
        while( left_biggest->right != NULL ){
            parent_node = left_biggest;
            left_biggest = left_biggest->right;
            direction = 1;
        }
        
        node->value = left_biggest->value;
        //削除対象の左子ノードが最大値
        if( direction == -1 ){
            parent_node->left = left_biggest->left;
        }
        //最大値の孫以降の要素がある
        else{
            parent_node->right = left_biggest->right;
        }
        //入れ替えた子孫要素の削除
        free( left_biggest );
    }
    return 1;
}