nodes - ノード削除の前または後に AVL ツリーのバランスをとりますか?

Question

この演習では、受講者に AVL ツリーからノードを削除するよう求めます。この場合、最も深い深さと最も浅い深さの差が 1 より大きいため、ある程度のバランス調整が必要です。それとも関係ありませんか？

問題の AVL ツリーの画像

Answer 1

基本的に、BST から削除する場合と同じように削除します。次に、深さ係数 (ツリーの各パスの長さ) を計算し、バランスが取れていないパスに応じて通常の挿入で行うように回転を行います。したがって、質問に答えるには、削除後にローテーションを行います。