Implementing a Binary search in python program with all the essential operations—insert, delete, and search—in Python can be done by defining a Node class and a BinarySearchTree class. Below is a full implementation:
Implementation of a Binary Search Tree (BST) in Python
class Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
class BinarySearchTree:
def __init__(self):
self.root = None
def insert(self, key):
if self.root is None:
self.root = Node(key)
else:
self._insert(self.root, key)
def _insert(self, root, key):
if key < root.key:
if root.left is None:
root.left = Node(key)
else:
self._insert(root.left, key)
else:
if root.right is None:
root.right = Node(key)
else:
self._insert(root.right, key)
def search(self, key):
return self._search(self.root, key)
def _search(self, root, key):
if root is None or root.key == key:
return root
if key < root.key:
return self._search(root.left, key)
return self._search(root.right, key)
def delete(self, key):
self.root = self._delete(self.root, key)
def _delete(self, root, key):
if root is None:
return root
if key < root.key:
root.left = self._delete(root.left, key)
elif key > root.key:
root.right = self._delete(root.right, key)
else:
# Node with only one child or no child
if root.left is None:
return root.right
elif root.right is None:
return root.left
# Node with two children: Get the inorder successor
temp = self._minValueNode(root.right)
root.key = temp.key
root.right = self._delete(root.right, temp.key)
return root
def _minValueNode(self, node):
current = node
while current.left is not None:
current = current.left
return current
def inorder(self):
self._inorder(self.root)
def _inorder(self, root):
if root:
self._inorder(root.left)
print(root.key, end=' ')
self._inorder(root.right)
# Example usage:
bst = BinarySearchTree()
bst.insert(50)
bst.insert(30)
bst.insert(20)
bst.insert(40)
bst.insert(70)
bst.insert(60)
bst.insert(80)
print("Inorder traversal of the BST:")
bst.inorder() # Output should be: 20 30 40 50 60 70 80
# Search for a node
node = bst.search(60)
if node:
print(f"nNode with key {node.key} found!")
else:
print("nNode not found!")
# Delete a node
bst.delete(20)
print("Inorder traversal after deleting 20:")
bst.inorder() # Output should be: 30 40 50 60 70 80
bst.delete(30)
print("nInorder traversal after deleting 30:")
bst.inorder() # Output should be: 40 50 60 70 80
bst.delete(50)
print("nInorder traversal after deleting 50:")
bst.inorder() # Output should be: 40 60 70 80
Explanation of the Code:
- Node Class:
- Each Node object represents a single node in the tree and contains the key (value), a pointer to the left child, and a pointer to the right child.
- BinarySearchTree Class:
- insert(key): Inserts a new node with the given key into the BST.
- _insert(root, key): A recursive helper function to find the correct location to insert the new node.
- search(key): Searches for a node with the given key in the BST.
- _search(root, key): A recursive helper function for searching.
- delete(key): Deletes a node with the given key from the BST.
- _delete(root, key): A recursive helper function for deletion.
- _minValueNode(node): Finds the node with the smallest key value, used in the deletion process when the node to be deleted has two children.
- inorder(): Performs an inorder traversal of the BST, printing the keys in sorted order.
- _inorder(root): A recursive helper function for inorder traversal.
Example Usage:
- The example creates a BST, inserts several nodes, performs searches, and demonstrates deletion while maintaining the BST properties.
Leave a Reply