Post 2: Trees and Binary Search Trees

Introduction

In computer science, a tree is a widely-used data structure that represents a hierarchical structure with a set of connected nodes. It consists of a collection of nodes, where each node has a value and a list of references to its child nodes. Trees offer efficient storage and retrieval of data and are applicable in various domains such as file systems, databases, and network routing.

A binary search tree (BST) is a type of tree data structure that has a special property: for any node in the tree, the value of every node in its left subtree is less than its own value, and the value of every node in its right subtree is greater than its own value. This property enables fast searching, inserting, and deleting of elements within the tree.

Properties of Binary Search Trees

• Every node in a BST has a key value, and no two nodes have the same key value.
• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• Both the left and right subtrees must also be binary search trees.

Searching in Binary Search Trees

A key benefit of binary search trees is their efficient searching capability. The searching process is accomplished by comparing the target value with the key value of each node.

Here is the algorithm for searching in a binary search tree:

def search(root, target):
    # Base case: node is empty or target found
    if root is None or root.value == target:
        return root
  
    # If target is greater than root's value, search in the right subtree
    if root.value < target:
        return search(root.right, target)
    
    # If target is smaller than root's value, search in the left subtree
    return search(root.left, target)

Insertion into Binary Search Trees

Inserting elements into a binary search tree involves finding the correct position to place the new node while maintaining the binary search tree property.

Here is the algorithm for inserting into a binary search tree:

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

def insert(root, value):
    # Base case: tree is empty, create a new root node
    if root is None:
        return Node(value)
  
    # Recursively find the correct position to insert the new node
    if value < root.value:
        root.left = insert(root.left, value)
    else:
        root.right = insert(root.right, value)
  
    return root

Deletion from Binary Search Trees

Deleting a node from a binary search tree requires finding the node to be deleted and considering various cases based on the number of child nodes the node has.

Here is the algorithm for deleting a node from a binary search tree:

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

def find_min_value_node(node):
    current = node
    while current.left:
        current = current.left
    return current

def delete_node(root, value):
    # Base case: tree is empty
    if root is None:
        return root
  
    # Recursively find the node to be deleted
    if value < root.value:
        root.left = delete_node(root.left, value)
    elif value > root.value:
        root.right = delete_node(root.right, value)
  
    # Node to be deleted found
    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
        # Find the minimum value in the right subtree to replace the deleted node
        temp = find_min_value_node(root.right)
        # Copy the minimum value to the node
        root.value = temp.value
        # Delete the duplicate node in the right subtree
        root.right = delete_node(root.right, temp.value)
  
    return root

Example:

Consider the following binary search tree:

        6
      /   \
     3     9
    / \     \
   2   4     11
        \
         5

• Searching for the value 5:

search(root, 5) -> Found

• Inserting the value 7 into the tree:

insert(root, 7) -> Tree after insertion:

        6
      /   \
     3     9
    / \     \
   2   4     11
        \     
         5   
          \
           7

• Deleting the value 6 from the tree:

delete_node(root, 6) -> Tree after deletion:

        7
      /   \
     3     9
    / \     \
   2   4     11
        \     
         5

Binary search trees provide efficient search, insert, and delete operations with an average time complexity of O(log n), where n is the number of elements in the tree. However, in some cases, when the tree is skewed, the worst-case time complexity can be O(n), making balancing techniques essential in certain scenarios.