Binary Search Tree

I. Concept and Introduction

A Binary Search Tree (BST), also known as a binary search tree, binary search tree, ordered binary tree, or sorted binary tree, satisfies the following conditions:

• If its left subtree is not empty, all node values in the left subtree are less than its root node value.
• If its right subtree is not empty, all node values in the right subtree are greater than its root node value.

Both its left and right subtrees are also binary search trees.

As shown in the figure below:

II. Applicability

A Binary Search Tree offers efficient operations for insertion, deletion, and querying.

The average time complexity is O(log n), with the worst-case scenario being O(n). Unlike heaps, a Binary Search Tree is not necessarily a complete binary tree and is not easily represented in an array format at its base level. Therefore, a linked list is used to implement the Binary Search Tree.

First, the array-based binary search method is introduced as a reference for the concept, followed by an introduction to the search method used in Binary Search Trees.

III. Illustration of Binary Search Process

The concept of binary search was proposed in 1946. Searching is a fundamental and crucial problem in computing, particularly for ordered sequences where binary search can be applied. To search for an element, we first compare the value V in the middle of the array with the data we are looking for, considering three scenarios:

• 1. If it equals the data we are searching for, it is directly found.
• 2. If it is less than V, continue the search in the group less than V.
• 3. If it is greater than V, continue the search in the group greater than V.

IV. Java Example Code

Source Code Download: Download

src/tutorialpro/binary/BinarySearch.java File Code:

package tutorialpro.binarySearch;

/**
 * Binary Search Algorithm
 */
public class BinarySearch {
    // Binary search in an ordered array arr for target
    // If target is found, return its index
    // If target is not found, return -1
    public static int find(Comparable[] arr, Comparable target) {

        // Search for target in arr[l...r]
        int l = 0, r = arr.length-1;
        while( l <= r ){

            // int mid = (l + r)/2;
            // To prevent integer overflow in extreme cases, use the following logic to calculate mid
            int mid = l + (r-l)/2;

            if( arr[mid].compareTo(target) == 0 )
                return mid;

            if( arr[mid].compareTo(target) > 0 )
                r = mid - 1;
            else
                l = mid + 1;
        }

        return -1;
    }
}