deleteメソッドの実装

AVL ツリーからの要素の削除は、ツリーの再バランスが必要になる場合があることを除けば、BST からの削除と同じです。 「BST からの要素の削除」セクションで説明したように、バイナリ ツリーから要素を削除するには、アルゴリズムは最初にその要素を含むノードを見つけます。 current はバイナリ ツリー内の要素を含むノードを指し、parent は current ノードの親を指します。 現在の ノードは、親 ノードの左の子または右の子である可能性があります。
要素を削除するときは 2 つのケースが発生します。

ケース 1: 以下の図 (a) に示すように、現在の ノードには左の子がありません。 現在の ノードを削除するには、下の図 (b) に示すように、親 ノードを 現在の ノードの右側の子に接続するだけです。 親ノードからルートまでのパスに沿ったノードの高さが減少している可能性があります。ツリーのバランスを確保するには、

を呼び出します。

balancePath(parent.element);

ケース 2: 現在の ノードには左の子があります。 rightMost は current ノードの左側のサブツリーで最大の要素を含むノードを指し、parentOfRightMost は rightMost の親ノードを指します。 ノード (以下の図 (a) に示す)。 rightMost ノードは右の子を持つことはできませんが、左の子を持つことはできます。 current ノードの要素値を rightMost ノードの要素値に置き換え、parentOfRightMost ノードを rightMost の左の子に接続します。 > ノードを削除し、下の図 (b) に示すように rightMost ノードを削除します。

parentOfRightMost からルートまでのパスに沿ったノードの高さが減少している可能性があります。ツリーのバランスを確保するには、

を呼び出します。

balancePath(右端の親);

以上がdeleteメソッドの実装の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。