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

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

バランスパス(親要素);

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

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