← Back to Data Structures and Algorithms in Python
1. Introduction
A Binary Search Tree (BST) is a specialized version of a binary tree where for each node, all elements in the left subtree are less than the node, and all elements in the right subtree are greater than the node. It provides the advantage of faster search, insert, and delete operations compared to linear data structures like arrays and linked lists.
2. Implementation Steps
1. Define a Node class that will contain data, a left child, and a right child.
2. Implement the BinarySearchTree class which initializes the root node.
3. Provide methods to insert, search, delete, and display the tree using inorder traversal.
3. Implementation in Python
class Node:
def __init__(self, data):
self.data = data # Holds the data for the node
self.left = None # Pointer to the left child node
self.right = None # Pointer to the right child node
class BinarySearchTree:
def __init__(self):
self.root = None # Initialize the root of the tree as None
def insert(self, data):
# Insert data into the tree
if self.root is None:
self.root = Node(data)
else:
self._insert_recursive(self.root, data)
def _insert_recursive(self, node, data):
# A private helper function to insert data recursively
if data < node.data:
if node.left is None:
node.left = Node(data)
else:
self._insert_recursive(node.left, data)
elif data > node.data:
if node.right is None:
node.right = Node(data)
else:
self._insert_recursive(node.right, data)
def search(self, data):
# Search for data in the tree
return self._search_recursive(self.root, data)
def _search_recursive(self, node, data):
# A private helper function to search for data recursively
if node is None:
return False
if node.data == data:
return True
if data < node.data:
return self._search_recursive(node.left, data)
return self._search_recursive(node.right, data)
def inorder(self):
# Display tree using inorder traversal
return self._inorder_recursive(self.root)
def _inorder_recursive(self, node):
# A private helper function for inorder traversal
result = []
if node:
result += self._inorder_recursive(node.left)
result.append(node.data)
result += self._inorder_recursive(node.right)
return result
# Test the BinarySearchTree class
bst = BinarySearchTree()
bst.insert(50)
bst.insert(30)
bst.insert(70)
bst.insert(20)
bst.insert(40)
print("Inorder traversal:", bst.inorder())
print("Search for 40:", bst.search(40))
print("Search for 80:", bst.search(80))
Output:
Inorder traversal: [20, 30, 40, 50, 70] Search for 40: True Search for 80: False
Explanation:
1. The Node class is designed to hold its data, a left child, and a right child.
2. The BinarySearchTree class starts with a root which is the initial node of the tree.
3. The insert method adds data to the tree. If the tree is empty, the root node is established. If not, a recursive helper function (_insert_recursive) finds the correct position for the new node.
4. The search method checks whether a specific data value exists in the tree. It uses a recursive function (_search_recursive) to complete the search.
5. The inorder method showcases the tree using the inorder traversal technique. This outputs a sorted sequence for binary search trees.
6. In the testing segment, we initiate a binary search tree, inject several values, and then conduct search and display functions.
Related Data Structures in Python
- Stack Implementation in Python
- Queue Implementation in Python
- Deque Implementation in Python
- Singly Linked List Implementation in Python
- Doubly Linked List Implementation in Python
- Circular Linked List Implementation in Python
- PriorityQueue Implementation in Python
- Circular Queue Implementation in Python
- Binary Search Tree Implementation in Python
- Stack Implementation Using Linked List in Python
- Stack Implementation Using Doubly Linked List in Python
Comments
Post a Comment