Here's an implementation of a binary search tree in Python:
python
class Node:
"""
Represents a node in a binary search tree.
"""
def __init__(self, value):
self.value = value
self.left = None
self.right = None
class BinarySearchTree:
"""
Represents a binary search tree.
"""
def __init__(self):
self.root = None
def insert(self, value):
"""
Inserts a new node with the given value into the binary search tree.
"""
new_node = Node(value)
if self.root is None:
self.root = new_node
else:
current_node = self.root
while True:
if value < current_node.value:
if current_node.left is None:
current_node.left = new_node
break
else:
current_node = current_node.left
else:
if current_node.right is None:
current_node.right = new_node
break
else:
current_node = current_node.right
def find(self, value):
"""
Finds the node with the given value in the binary search tree.
"""
current_node = self.root
while current_node is not None:
if value == current_node.value:
return current_node
elif value < current_node.value:
current_node = current_node.left
else:
current_node = current_node.right
return None
def delete(self, value):
"""
Deletes the node with the given value from the binary search tree.
"""
parent_node = None
current_node = self.root
while current_node is not None:
if value == current_node.value:
if current_node.left is None and current_node.right is None:
# Node has no children
if parent_node is None:
self.root = None
elif current_node == parent_node.left:
parent_node.left = None
else:
parent_node.right = None
elif current_node.left is None:
# Node has one right child
if parent_node is None:
self.root = current_node.right
elif current_node == parent_node.left:
parent_node.left = current_node.right
else:
parent_node.right = current_node.right
elif current_node.right is None:
# Node has one left child
if parent_node is None:
self.root = current_node.left
elif current_node == parent_node.left:
parent_node.left = current_node.left
else:
parent_node.right = current_node.left
else:
# Node has two children
successor_node = current_node.right
while successor_node.left is not None:
successor_node = successor_node.left
current_node.value = successor_node.value
current_node = successor_node
value = current_node.value
parent_node = current_node.parent
elif value < current_node.value:
parent_node = current_node
current_node = current_node.left
else:
parent_node = current_node
current_node = current_node.right
In this implementation, a Node class represents a node in the binary search tree, and a BinarySearchTree class represents the tree itself. The insert method is used to insert a new node into the tree, the find method is used to find a node with a specific value, and the delete method is used to delete a node with a specific value.
The insert method works by traversing the tree starting from the root node and comparing the value of the new node to the value of each node until a suitable position is found. If
No comments:
Post a Comment