BSTからノードを削除するには、いくつかのケースが考えられます。以下では、それぞれのケースについて説明し、コード例を示します。
-
削除対象のノードが葉ノードの場合:
- 削除対象のノードを単純に削除します。
-
削除対象のノードが子を1つだけ持つ場合:
- 削除対象のノードの親ノードと、削除対象のノードの子ノードをつなぎ直します。
-
削除対象のノードが子を2つ持つ場合:
- 削除対象のノードの右部分木の最小ノードを見つけます(または左部分木の最大ノードを見つけます)。
- 最小ノード(または最大ノード)の値を削除対象のノードにコピーし、最小ノード(または最大ノード)を削除します。
これらのケースに基づいて、効果的な削除操作の実装方法をコード例とともに紹介します。以下は、PythonでのBST削除操作の例です。
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
class BST:
def __init__(self):
self.root = None
def delete_node(self, value):
self.root = self._delete_node(self.root, value)
def _delete_node(self, root, value):
if root is None:
return root
if value < root.value:
root.left = self._delete_node(root.left, value)
elif value > root.value:
root.right = self._delete_node(root.right, value)
else:
if root.left is None:
return root.right
elif root.right is None:
return root.left
else:
min_value = self._find_min_value(root.right)
root.value = min_value
root.right = self._delete_node(root.right, min_value)
return root
def _find_min_value(self, root):
while root.left is not None:
root = root.left
return root.value
# BSTの削除操作の使用例
bst = BST()
bst.root = Node(10)
bst.root.left = Node(5)
bst.root.right = Node(15)
bst.root.left.left = Node(3)
bst.root.left.right = Node(7)
bst.root.right.left = Node(12)
bst.root.right.right = Node(17)
bst.delete_node(5)
このように、BSTの削除操作は削除対象のノードのケースに応じて異なるアプローチが必要です。適切な場合分けと適切なコード例を使用することで、効果的な削除操作を実装できます。