The implementation of a Binary Search Tree (BST) involves creating a tree structure with nodes, where each node contains a key, and the left and right subtrees follow specific ordering rules. Here’s a breakdown of how to implement a Binary Search Tree:
1. Node Structure
Each node in the binary search tree contains:
- Key: The value of the node.
- Left child: A reference to the left child node.
- Right child: A reference to the right child node.
class Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
2. Binary Search Tree Class
The Binary Search Tree class typically contains methods for inserting, searching, deleting nodes, and traversing the tree.
class BST:
def __init__(self):
self.root = None
3. Insert Method
The insert method adds a new key to the BST, ensuring that all nodes to the left of a node have smaller values, and nodes to the right have larger values.
def insert(self, root, key):
if root is None:
return Node(key)
if key < root.key:
root.left = self.insert(root.left, key)
else:
root.right = self.insert(root.right, key)
return root
def insert_root(self, key):
self.root = self.insert(self.root, key)
4. Search Method
The search method checks whether a value exists in the BST. It compares the target value with the current node and traverses left or right accordingly.
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)
5. Delete Method
To delete a node, the BST must consider three cases:
- The node is a leaf (no children).
- The node has one child.
- The node has two children (in which case, we usually replace it with the in-order successor or predecessor).
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 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
root.key = self.min_value(root.right)
root.right = self.delete(root.right, root.key)
return root
def min_value(self, node):
current = node
while current.left:
current = current.left
return current.key
6. Traversal Methods
Traversal methods allow you to visit all nodes in the tree, either in:
- In-order: Visit left, root, right (results in sorted order for BST).
- Pre-order: Visit root, left, right.
- Post-order: Visit left, right, root.
def inorder(self, root):
if root:
self.inorder(root.left)
print(root.key, end=" ")
self.inorder(root.right)
def preorder(self, root):
if root:
print(root.key, end=" ")
self.preorder(root.left)
self.preorder(root.right)
def postorder(self, root):
if root:
self.postorder(root.left)
self.postorder(root.right)
print(root.key, end=" ")
Example of Using the BST
bst = BST()
bst.insert_root(50)
bst.insert_root(30)
bst.insert_root(70)
bst.insert_root(20)
bst.insert_root(40)
bst.insert_root(60)
bst.insert_root(80)
# Traversals
print("In-order Traversal: ")
bst.inorder(bst.root)
print("\nPre-order Traversal: ")
bst.preorder(bst.root)
# Searching for a key
found_node = bst.search(bst.root, 60)
if found_node:
print(f"\nNode with key {found_node.key} found.")
else:
print("\nNode not found.")
# Deleting a node
bst.root = bst.delete(bst.root, 20)
print("\nIn-order Traversal after deletion: ")
bst.inorder(bst.root)
Summary of Methods
- Insert: Adds a new node while maintaining the BST property.
- Search: Searches for a node with a specific key.
- Delete: Removes a node, handling various cases (no children, one child, two children).
- Traversal: Provides ways to visit the nodes in a specific order (in-order, pre-order, post-order).
This is a basic structure for implementing a Binary Search Tree. More advanced techniques can be added, like balancing the tree (e.g., AVL tree, Red-Black tree), or methods for finding the height, depth, or balance of the tree.