-
二分探索木(BST)の削除操作の基本的なアイデア:
- 削除したいノードが葉ノードである場合、そのノードを単に削除します。
- 削除したいノードが子ノードを1つだけ持つ場合、そのノードを削除し、子ノードを上位のノードに接続します。
- 削除したいノードが子ノードを2つ持つ場合、以下のいくつかの方法があります。ここでは一つの方法を紹介します。
-
削除操作の具体的な手順:
- 削除したいノードを見つけます。
- 削除したいノードの右部分木の最小ノードまたは左部分木の最大ノードを見つけます(このノードは、削除したいノードの直後または直前の値を持ちます)。
- 見つけたノードを削除したいノードと入れ替えます。
- 入れ替えたノードを削除します(このノードは、削除したいノードの位置に移動します)。
-
コード例: 以下に、Pythonでの二分探索木の削除操作のコード例を示します。
class Node: def __init__(self, value): self.value = value self.left = None self.right = None def delete_node(root, key): if root is None: return root if key < root.value: root.left = delete_node(root.left, key) elif key > root.value: root.right = delete_node(root.right, key) else: if root.left is None: temp = root.right root = None return temp elif root.right is None: temp = root.left root = None return temp temp = get_min_value_node(root.right) root.value = temp.value root.right = delete_node(root.right, temp.value) return root def get_min_value_node(node): current = node while current.left is not None: current = current.left return current
これらの手順とコード例を使用すると、bstの削除操作を正確に実行することができます。この情報を使って、ブログ投稿を作成してください。