0

Avlツリーで、2つの子を持つノードを削除すると、そのノードを後続（右側のサブツリーの最小値）または先行（左側のサブツリーの最大値）のいずれかに置き換えることができることを知っています。

私の質問は次のとおりです。標準では、どのサブツリーにノードとスワップしますか？後継者または前任者？

ありがとう！:)

4

1 に答える 1

2

後で必要なすべてのリバランスを行う限り、どちらかを使用できます。アルゴリズムはどちらの方法でも機能します。

本当に賢くなりたい場合は、後でリバランスが最も少なくて済むものに基づいて、どちらかを選択できます。ただし、常に次に大きいキーまたは次に小さいキーを選択するよりも、かなり複雑になります。

于 2012-10-02T22:13:44.710 に答える