Binary Search Trees (BST)

Binary search trees (BST) are a fundamental data structure used in computer science and are a key component in many algorithms. BSTs are used in a variety of applications, from database systems to sorting algorithms. BSTs provide efficient ways of searching, inserting, and deleting elements. In this article, we will discuss the time and space complexities associated with BSTs, as well as provide examples of how to implement them in Python.

What is a Binary Search Tree?

A Binary Search Tree (BST) is a collection of nodes arranged in a hierarchical structure. Each node contains two fields: a key and a value. The key of a node is used to compare the relative order of two nodes. The key is also used to search, insert, and delete elements from the tree. Each node in the tree can have at most two children, referred to as the left and right child. The left child must have a key that is less than or equal to the parent node’s key. Similarly, the right child must have a key that is greater than or equal to the parent node’s key.

How does Binary Search Trees Work?

A binary search tree (BST) is a type of data structure that is used in computer science to store and organize data. It is a tree-like structure with nodes that contain a key, left and right pointers, and a data value.

To begin, each node in the tree is initialized as the root node. The root node will contain a key, left and right pointers, and a data value. The root node is the starting point to traverse the BST.

Next, the BST is traversed in a top-down fashion. To look up a node, the key of the root node is compared to the key being searched for. If the key being searched for is less than the root node’s key, the left pointer is followed. If the key being searched for is greater than the root node’s key, the right pointer is followed. This process is repeated until the key being searched for is found.

Once the desired node is located, the data stored in the node is retrieved and returned. If the node is not found, an error is returned.

The BST is an efficient data structure for searching and inserting data, as the time complexity for searching is O(log n). The time complexity for inserting a node is also O(log n). This is because the BST is self-balancing, meaning the height of the tree is kept to a minimum. This allows for faster searches and insertions of data.

Binary search trees are often used in applications where fast search and insertion operations are required, such as in databases, search engines, and sorting algorithms.

Time Complexity

The time complexity of BSTs is determined by the number of operations required to access, search, insert, and delete elements from the tree. To evaluate the time complexity, we must consider the average case and the worst case.

Access:

The time complexity of accessing a node in a BST is O(log n), where n is the number of nodes in the tree. This is because, in the worst case, the search must traverse the entire tree. However, since the tree is balanced, the search will typically take log(n) time.

Search:

The time complexity of searching a BST is also O(log n). This is because, in the worst case, the search must traverse the entire tree. However, since the tree is balanced, the search will typically take log(n) time.

Insertion:

The time complexity of inserting a node into a BST is O(log n). This is because, in the worst case, the insertion must traverse the entire tree. However, since the tree is balanced, the insertion will typically take log(n) time.

Deletion:

The time complexity of deleting a node from a BST is O(log n). This is because, in the worst case, the deletion must traverse the entire tree. However, since the tree is balanced, the deletion will typically take log(n) time.

Space Complexity:

The space complexity of a BST is determined by the amount of memory required to store the tree. The space complexity of a BST is O(n), where n is the number of nodes in the tree. This is because the tree must store the keys and values of each node.

Creating a Binary Search Tree in Python

Now that we have discussed the time and space complexities of BSTs, let’s take a look at how to implement one in Python.

We will start by creating a Node class that will be the building blocks of our BST. The Node class will contain two fields: a key and a value. It will also contain a reference to the left and right children of the node.

class Node:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.left = None
        self.right = None

Next, we will create a BinarySearchTree class that will contain the logic for inserting, searching, and deleting nodes from our BST. The BinarySearchTree class will contain a reference to the root node of the tree.

class BinarySearchTree:
    def __init__(self):
        self.root = None

Now we can implement the insert(), search(), and delete() methods.

The insert() method will take a key and a value and insert them into the BST. The method will start by creating a new Node object with the key and value. It will then traverse the BST to find the correct position for the new node.

def insert(self, key, value):
    # Create a new node
    new_node = Node(key, value)

    # Check if the tree is empty
    if self.root is None:
        self.root = new_node
        return

    # Traverse the tree to find the correct position
    current_node = self.root
    while current_node is not None:
        if key < current_node.key:
            # Go left
            if current_node.left is None:
                current_node.left = new_node
                return
            else:
                current_node = current_node.left
        else:
            # Go right
            if current_node.right is None:
                current_node.right = new_node
                return
            else:
                current_node = current_node.right

The search() method will take a key and search for it in the BST. It will start by checking if the tree is empty. If the tree is not empty, it will traverse the tree to find the node with the given key.

def search(self, key):
    # Check if the tree is empty
    if self.root is None:
        return None

    # Traverse the tree to find the node with the given key
    current_node = self.root
    while current_node is not None:
        if key == current_node.key:
            return current_node
        elif key < current_node.key:
            current_node = current_node.left
        else:
            current_node = current_node.right

    # Node with given key was not found
    return None

The delete() method will take a key and delete the node with the given key from the tree. It will start by searching for the node with the given key. If the node is found, the method will delete the node and update the pointers of the parent and child nodes accordingly.

def delete(self, key):
    # Search for the node with the given key
    node_to_delete = self.search(key)
    if node_to_delete is None:
        # Node with given key was not found
        return

    # Check if node to be deleted has no children
    if node_to_delete.left is None and node_to_delete.right is None:
        # Check if node to be deleted is root
        if node_to_delete == self.root:
            self.root = None
            return
        # Find parent node
        parent = self._find_parent(key)
        # Update parent node's pointer
        if parent.left == node_to_delete:
            parent.left = None
        else:
            parent.right = None
        return

    # Node to be deleted has one child
    if node_to_delete.left is None or node_to_delete.right is None:
        # Check if node to be deleted is root
        if node_to_delete == self.root:
            # Check if node to be deleted has a left child
            if node_to_delete.left is not None:
                self.root = node_to_delete.left
            # Node to be deleted has a right child
            else:
                self.root = node_to_delete.right
            return
        # Find parent node
        parent = self._find_parent(key)
        # Check if node to be deleted has a left child
        if node_to_delete.left is not None:
            # Update parent node's pointer
            if parent.left == node_to_delete:
                parent.left = node_to_delete.left
            else:
                parent.right = node_to_delete.left
            return
        # Node to be deleted has a right child
        else:
            # Update parent node's pointer
            if parent.left == node_to_delete:
                parent.left = node_to_delete.right
            else:
                parent.right = node_to_delete.right
            return

    # Node to be deleted has two children
    if node_to_delete.left is not None and node_to_delete.right is not None:
        # Find the in-order successor of the node to be deleted
        successor = self._find_successor(node_to_delete)
        # Copy the successor's key and value to the node to be deleted
        node_to_delete.key = successor.key
        node_to_delete.value = successor.value
        # Find the parent node of the successor
        parent = self._find_parent(successor.key)
        # Delete the successor
        if parent.left == successor:
            parent.left = None
        else:
            parent.right = None
        return

Conclusion

In this article, we discussed the time and space complexities associated with Binary Search Trees (BSTs) and how to implement them in Python. We discussed the time complexities of BSTs for accessing, searching, inserting, and deleting nodes. We also discussed the space complexity of BSTs. Finally, we provided code examples for creating a BST and implementing the insert(), search(), and delete() methods.

Exercises