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; }
リンク
リンク
