A binary search tree (BST) is a data structure that allows for fast insertion, deletion, and search operations. It is called a “binary” tree because each node has at most two children. The left child of a node is always less than the node’s value, and the right child is always greater.
One advantage of a BST is that it can be easily implemented in Python using just a few basic data structures. In this article, we will go over how to write a BST in Python and provide some examples of how it can be used.
To start, let’s define the structure of a BST node. Each node will have a value and pointers to its left and right children:
class BSTNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = NoneNext, we will define the BST itself. We will keep track of the root node and will define methods for inserting, deleting, and searching for values in the tree:
class BST:
def __init__(self):
self.root = None
def insert(self, value):
# code for inserting a value into the tree goes here
def delete(self, value):
# code for deleting a value from the tree goes here
def search(self, value):
# code for searching for a value in the tree goes here
Now, let’s go over how to implement the insert, delete, and search methods.
Inserting a Value
To insert a value into a BST, we first need to check if the tree is empty. If it is, we can simply set the root node to a new BSTNode with the value we want to insert. If the tree is not empty, we need to find the correct place to insert the new node.
To do this, we will start at the root node and compare the value we want to insert to the value of the current node. If the value is less than the current node’s value, we will move to the left child. If the value is greater, we will move to the right child. We continue this process until we reach a leaf node (a node with no children). At this point, we can insert the new node as the left or right child of the leaf node, depending on whether the value is less than or greater than the leaf node’s value.
Here is the code for the insert method:
def insert(self, value):
new_node = BSTNode(value)
if self.root is None:
self.root = new_node
return
current_node = self.root
while True:
if value < current_node.value:
if current_node.left is None:
current_node.left = new_node
return
current_node = current_node.left
else:
if current_node.right is None:
current_node.right = new_node
return
current_node = current_node.right
Deleting a Value
Deleting a value from a BST is a bit more complicated than inserting a value. There are three cases we need to consider:
- The node we want to delete is a leaf node (has no children). In this case, we can simply remove the node from the tree.
- The node we want to delete has one child. In this case, we can simply replace the node with its child. 3. The node we want to delete has two children. In this case, we need to find the smallest value in the right subtree of the node and use that value to replace the node. Then, we can delete the smallest value from the right subtree.
- Here is the code for the delete method:
def delete(self, value):
if self.root is None:
return
current_node = self.root
parent = None
while current_node is not None and current_node.value != value:
parent = current_node
if value < current_node.value:
current_node = current_node.left
else:
current_node = current_node.right
if current_node is None:
return
# Case 1: Leaf node
if current_node.left is None and current_node.right is None:
if parent is None:
self.root = None
elif parent.left == current_node:
parent.left = None
else:
parent.right = None
# Case 2: Node with one child
elif current_node.left is None:
if parent is None:
self.root = current_node.right
elif parent.left == current_node:
parent.left = current_node.right
else:
parent.right = current_node.right
elif current_node.right is None:
if parent is None:
self.root = current_node.left
elif parent.left == current_node:
parent.left = current_node.left
else:
parent.right = current_node.left
# Case 3: Node with two children
else:
successor = current_node.right
while successor.left is not None:
successor = successor.left
current_node.value = successor.value
self.delete(successor.value)
Searching for a Value
To search for a value in a BST, we simply need to start at the root node and compare the value we are searching for to the value of the current node. If the value is less than the current node’s value, we move to the left child. If the value is greater, we move to the right child. We continue this process until we either find the value or reach a leaf node without finding the value.
Here is the code for the search method:
def search(self, value):
current_node = self.root
while current_node is not None and current_node.value != value:
if value < current_node.value:
current_node = current_node.left
else:
current_node = current_node.right
return current_node is not None
Example
Here is an example of how to use our BST class to create a tree and perform some basic operations:
# Create a new BST
tree = BST()
# Insert some values into the tree
tree.insert(5)
tree.insert(3)
tree.insert(8)
tree.insert(1)
tree.insert(4)
tree.insert(7)
tree.insert(10)
# Search for a value in the tree
print(tree.search(4)) # True
print(tree.search(6)) # False
# Delete a value from the tree
tree.delete(8)
print(tree.search(8)) # False
Conclusion
In this article, we went over how to write a binary search tree in Python. We defined the BSTNode class to represent a single node in the tree and the BST class to represent the tree itself. We also implemented methods for inserting, deleting, and searching for values in the tree. With these basic building blocks, you can use a BST to efficiently store and manipulate data in your Python programs.
