アルゴリズムレビュー：バイナリ探索木の削除

2つのセクションでは、学びました。そして、BST内の要素を削除するにはどうすればよいのでしょうか？これは、このセクションの例を通して学びます！

以下も例を通して説明します。

トピック分析

一般的に、ノードの削除は2つのステップで行うことができます：

• まず、削除するノードを見つけます；
• 見つけたら削除してください。

説明: アルゴリズムの所要時間はO(h)で、hは木の高さです。

例

root = [5,3,6,2,4,null,7]
key = 3
 5
 / \
 3 6
 / \ \
2 4 7
削除するノードの値が3だとすると，まずノード3を見つけて削除する．
正解は[5,4,6,2,null,null,7], 下記をご覧いただきたい 
 5
 / \
 4 6
 / \
2 7
もうひとつの正解は[5,2,6,null,4,null,7]。
 5
 / \
 2 6
 \ \
 4 7

両セクションを最初に学習することを強くお勧めします！

最良の学習成果を得るために

改訂と統合

まず、2進探索木の性質を復習します：

• 左のサブツリーが空でない場合、左のサブツリーのすべての値がルート・ノードの値より小さい。
• 右のサブツリーが空でなければ、右のサブツリーのすべての値がルート・ノードの値より大きい。
• その左と右のサブツリーもそれぞれバイナリ探索木です。

典型的なBSTは以下の写真：

図解分析

コンセプトの明確化と分析BSTのノードを削除するには、まずノードを見つける必要があります。そして、見つかった後、3つのシナリオが発生します。

1.削除されるノードの左サブツリーが空である場合、削除されるノードの右サブツリー自身を置き換えます。

2.削除されるノードの右サブツリーが空である場合、削除されるノードの左サブツリー自身を置き換えます。

3.削除するノードの左右のサブツリーが空でない場合。現在のノードより小さい最大のノードを見つけ、それ自身を置き換える必要があります。

または現在のノードより大きい最小のノードと入れ替わります。

それを分析した後、コードがそれをどのように実装しているかを一緒に見てみましょう。

GO言語の例

ここでは、後継ノードを介して自分自身を置き換えるスキームを示します：

func deleteNode(root *TreeNode, key int) *TreeNode {
 if root == nil {
 return nil
 }
 if key < root.Val {
 root.Left = deleteNode( root.Left, key )
 return root
 }
 if key > root.Val {
 root.Right = deleteNode( root.Right, key )
 return root
 }
 //これはターゲットが見つかったことを意味する
 if root.Right == nil {
 //右のサブツリーは空である
 return root.Left
 }
 if root.Left == nil {
 //左のサブツリーは空である
 return root.Right
 }
 minNode := root.Right
 for minNode.Left != nil {
 //後継者を探す
 minNode = minNode.Left
 }
 root.Val = minNode.Val
 root.Right = deleteMinNode( root.Right )
 return root
}
func deleteMinNode( root *TreeNode ) *TreeNode {
 if root.Left == nil {
 pRight := root.Right
 root.Right = nil
 return pRight
 }
 root.Left = deleteMinNode( root.Left )
 return root
}

実施結果：

私が書いたすべての解答と各問題の完全な図解をeBookにまとめました。