c++ - コピーせずに二分探索木を削除する

Question

単純な二分探索木データ構造（自己平衡化ではない）をプログラミングする場合、2つの子を持つノードを削除するときにほとんどのリソースが提供するアドバイスは、左側の子の1つから削除されるノードにデータをコピーすることです。これは悪い習慣ですか？ある種のポインタ操作はより速い結果を提供しませんか？これを一般化できるBSTローテーションアルゴリズムはありますか？

Answer 1

はい、ノードをコピーする必要はありません。削除するノードの場所にノードを配置するために、ノードを「移動」（つまり、ポインタを変更）するだけです。バランスを維持しようとしない場合は、実際にはどのような種類の回転も行う必要はありません。左側のサブツリーの右端のノード（または右側のサブツリーの左端のノード）を選択するだけです。 -木）。それを現在の場所から削除し、削除する必要のあるノードの場所に挿入します（すべて厳密にポインターを操作することによって）。