A Binary Search Tree (BST) is a data structure that is used for efficient searching, insertion, and deletion of elements. It is a binary tree where each node has at most two children: a left child and a right child.
The key property of a BST comprises of:
- Every Node has a key
- Keys in the left sub-tree of the root are smaller than the key in the root
- Keys in the right sub-tree of the root are larger than the key in the root
- Left and Right Sub-trees are also Binary Search Trees
All the binary search trees are binary trees but not all binary trees are binary search trees
Search operation in Binary Search Tree
In a Binary Search Tree (BST), the search operation allows you to find a specific element (key) efficiently. Here's how the search operation works in a BST:
- The search begins at the root node of the BST.
- At each step of the search, the key being searched for is compared with the key of the current node.
- Based on the comparison, the search algorithm decides whether to continue searching in the left subtree, the right subtree or if the current node is the desired node.
- The search operation typically uses recursion to traverse the tree until it finds the desired key or reaches a leaf node (a node with no children).
- If the current node's key matches the desired key, the search operation terminates, and the node containing the key is returned. If the desired key is not found, the search operation returns false or None, indicating that the key is not present in the tree.
Now, let's illustrate the search operation with an example:
Consider the following BST:
5
/ \
3 7
/ \ / \
2 4 6 8
Suppose we want to search for the key 6 in this BST.
- We start at the root node with the value 5.
- Since 6 is greater than 5, we move to the right subtree.
- Now, we are at the node with value 7. Since 6 is less than 7, we move to the left subtree of 7.
- Now, we are at the node with value 6. Since 6 matches the desired key, we terminate the search and return True, indicating that 6 is present in the BST.
Implementation of a Binary Search Tree
Node
class Node:
"""
Represents a node in a binary tree.
Attributes:
_val: The value stored in the node.
_left: Reference to the left child node.
_right: Reference to the right child node.
"""
__slots__ = '_val', '_left', '_right'
def __init__(self, val, left=None, right=None):
"""
Initializes a node with the given value and optional left and right children.
Args:
val: The value to be stored in the node.
left: Reference to the left child node (default is None).
right: Reference to the right child node (default is None).
"""
self._val = val
self._left = left
self._right = right
BinarySearchTree
from collections import deque
class BinarySearchTree:
"""
Represents a Binary Search Tree (BST) data structure.
"""
def __init__(self):
"""
Initializes an empty Binary Search Tree.
"""
self._root = None
self._size = 0
def insert(self, e):
"""
Inserts a new element 'e' into the Binary Search Tree.
Args:
e: The element to be inserted.
"""
# Start from the root node
cur = self._root
# Traverse the tree to find the appropriate position to insert the new node
while cur:
if e < cur._val:
cur = cur._left
elif e > cur._val:
cur = cur._right
# Create a new node with the value 'e'
node = Node(e)
# If the tree is not empty, insert the new node at the appropriate position
if self._root:
if e < cur._val:
cur._left = node
else:
cur._right = node
else:
# If the tree is empty, set the new node as the root
self._root = node
def recursive_insert(self, node, e):
"""
Recursively inserts a new element 'e' into the Binary Search Tree.
Args:
node: The current node being considered.
e: The element to be inserted.
Returns:
The updated node.
"""
if node is None:
# Create a new node with the value 'e'
new_node = Node(e)
return new_node
if e < node._val:
node._left = self.recursive_insert(node._left, e)
elif e > node._val:
node._right = self.recursive_insert(node._right, e)
return node
def search(self, k):
"""
Searches for a key 'k' in the Binary Search Tree.
Args:
k: The key to search for.
Returns:
True if the key is found, False otherwise.
"""
node = self._root
while node:
if k < node._val:
node = node._left
elif k > node._val:
node = node._right
else:
return True
return False
def level_order(self):
"""
Performs level order traversal on the Binary Search Tree and prints the node values.
"""
q = deque()
t = self._root
print(t._val, end='--')
q.append(t)
while q:
t = q.popleft()
if t._left:
print(t._left._val, end='--')
q.append(t._left)
if t._right:
print(t._right._val, end='--')
q.append(t._right)
def in_order(self, node):
"""
Performs in-order traversal starting from the given node and prints the node values.
Args:
node: The starting node for the traversal.
"""
if node:
self.in_order(node._left)
print(node._val, end='--')
self.in_order(node._right)
def pre_order(self, node):
"""
Performs pre-order traversal starting from the given node and prints the node values.
Args:
node: The starting node for the traversal.
"""
if node:
print(node._val, end='--')
self.pre_order(node._left)
self.pre_order(node._right)
def post_order(self, node):
"""
Performs post-order traversal starting from the given node and prints the node values.
Args:
node: The starting node for the traversal.
"""
if node:
self.post_order(node._left)
self.post_order(node._right)
print(node._val, end='--')
bst = BinarySearchTree()
bst._root = bst.recursive_insert(None, 35)
bst.recursive_insert(bst._root, 15)
bst.recursive_insert(bst._root, 45)
bst.recursive_insert(bst._root, 20)
bst.recursive_insert(bst._root, 25)
bst.recursive_insert(bst._root, 55)
bst.in_order(bst._root)
print()
print(bst.search(15))
Application of Binary Search Trees
Binary Search Trees are commonly used in various applications where efficient searching and sorting are required, such as databases, compilers, and symbol tables in programming languages.
They are fundamental data structures in computer science and are extensively studied due to their simplicity and usefulness in algorithm design and analysis.