バイナリツリー内のノードを削除する時間はどれくらいですか

Question

バイナリツリー内のノードを削除するには、ノードを検索する必要があります。これは最小O（log N）と最大O（N）で可能です。ノードによっては、ポインタを再配置する必要があります。どのようにしてその時間複雑さを計算しますか？

Answer 1

ほとんどの複雑さは、ノードを検索しています。親ノードが保持されている限り、それが見つかると、ノードを削除するための割り当てはほんの数です。だからそれは一定の順序です。

Answer 2

どのように削除を行っているかによって異なります。最も一般的な方法は、ノードの後継ノードを見つけ、そのノードをその後継ノードに置き換えることです。これはO（h）で行うことができます。ここで、hはツリーの高さです。最悪の場合、これはO（n）ですが、バランスの取れた木では最悪の場合O（lg n）です。

Answer 3

ここで、「最悪の検索時間は最大O（N）」になっていますか？それはBSTでは決して起こらないはずです。最悪の場合、検索と削除には最大O（h）でなければなりません。ここで、「h」はツリーの高さです。このhelpful articleを参照してください。

Answer 4

はい最良ケースの複雑さO（LOGN）（ときに完全にバランス）と
最悪の場合の複雑性は、（N）
1 Oである2 - - 3 - BST欠失を有する4

しかし主な問題（ Hibbard Deletion）は、対称ではないということです。多くの挿入および削除後に、BSTはバランスが取れなくなります。研究者は、樹木のランダムな挿入と削除の高さが十分に長いと、sqrt（n）となることを証明した。今度はすべての操作（検索、挿入、削除）はO（logn）と比べて良くない時間であるsqrt（n）となります。

これは、BSTの効率的な対称的な削除の問題を非常に長く（約50年）公開しています。保証されたバランスの取れた木のために、我々はRedBlackツリー等を使用しなければなりません。