binary-search-tree - バイナリ サブツリーでの削除

Question

この場合、D の左と右の子を持つノードを削除しようとしています。

                 D
                /  \ 
               A    F 
                \
                 B

したがって、 D を削除しようとすると、 B に置き換える必要があります。これは、 B が左側のサブツリーで次に大きな要素であるためです。B に置き換える代わりに F に置き換えることはできますか?

Answer 1

できますが、最適ではありません。挿入と削除がO（log n）の周りにとどまるように、ツリーを常に可能な限りバランスの取れたものにする必要があります。

Answer 2

まず第一に、二分木だけがソートされていません。あなたのツリーは二分探索木だと思います。ツリーをyesよりもソートしたままにするだけの場合は、この特定の例でFに置き換えることができます。ツリーがより複雑な場合、追加のアクションなしでこれを行うことはできません。たとえば、Fの子が存在する場合はそれを使用して何かを行う必要があり、追加の不要な処理が必要になります。