-
削除する要素の探索: 削除する要素をBST内で探索します。BSTの根ノードから始め、削除する要素が現在のノードの値と一致するか比較します。一致した場合、そのノードを削除します。一致しない場合は、探索を続けるために次のステップに進みます。
-
子ノードの有無による場合分け: a. 子ノードを持たない場合: 削除するノードが子ノードを持たない場合、そのノードを単純に削除します。親ノードとのリンクを切断し、メモリから解放します。
b. 左の子ノードまたは右の子ノードを持つ場合: 削除するノードが左の子ノードまたは右の子ノードを持つ場合、その子ノードを削除するノードの位置に置き換えます。これにより、BSTの整合性が保たれます。
-
子ノードが2つある場合: 削除するノードが2つの子ノードを持つ場合、以下の手順を実行します。 a. 削除するノードの右の部分木で最小の値を持つノードを探します。 b. そのノードの値を削除するノードにコピーします。 c. 最小値を持つノードを再帰的に削除します。
以上の手順に従って、要素をBSTから削除することができます。以下に、PythonでのBSTの要素削除の例を示します。
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def deleteNode(root, key):
if root is None:
return root
if key < root.val:
root.left = deleteNode(root.left, key)
elif key > root.val:
root.right = deleteNode(root.right, key)
else:
if root.left is None:
return root.right
elif root.right is None:
return root.left
else:
min_val = findMin(root.right)
root.val = min_val.val
root.right = deleteNode(root.right, min_val.val)
return root
def findMin(node):
current = node
while current.left is not None:
current = current.left
return current
# 例として、BSTから要素5を削除する場合
# BSTを構築
root = TreeNode(5)
root.left = TreeNode(3)
root.right = TreeNode(7)
root.left.left = TreeNode(2)
root.left.right = TreeNode(4)
root.right.left = TreeNode(6)
root.right.right = TreeNode(8)
# 要素5を削除
deleteNode(root, 5)このように、BSTから要素を削除する方法と、それに対するコード例を紹介しました。これを参考にして、自身でBSTから要素を削除する処理を実装してみてください。