Binary search tree

A Binary Search Tree (BST) is a tree data structure that keeps its elements in sorted order to allow efficient searching, insertion, and deletion operations. Each node contains a value and references to left and right children. For a node, all elements in the left subtree have values less than the node’s value, and all elements in the right subtree have values greater than or equal to the node’s value.

Key Characteristics of a Binary Search Tree

• Nodes: Each node has a value and two children pointers.
• Ordering Property: Left child values are less than the parent node’s value, and right child values are greater or equal.
• Dynamic Structure: The BST adapts its size as elements are added or removed.

Why Use a BST?

BSTs are used for scenarios that require dynamic and efficient data handling, including:

• Efficient Searching: Average-case time complexity for search is O(log n).
• Efficient Insertion: New elements can be inserted in O(log n) on average.
• Efficient Deletion: Elements can be deleted in O(log n) on average.
• Sorted Traversal: In-order traversal provides sorted data in O(n).

Implementing a BST in Java

A BST in Java can be implemented using classes to represent nodes and the BST itself.

Node Class

The node class represents a single node in the tree with value and pointers to left and right children.

class Node {
    int value;
    Node left, right;

    public Node(int item) {
        value = item;
        left = right = null;
    }
}

BST Class

The BST class encapsulates the operations that can be performed on the tree.

class BST {
    private Node root;

    public BST() {
        root = null;
    }

    public void insert(int value) {
        root = insertRec(root, value);
    }

    private Node insertRec(Node root, int value) {
        if (root == null) {
            root = new Node(value);
            return root;
        }
        if (value < root.value)
            root.left = insertRec(root.left, value);
        else if (value > root.value)
            root.right = insertRec(root.right, value);

        return root;
    }

    public boolean search(int value) {
        return searchRec(root, value);
    }

    private boolean searchRec(Node root, int value) {
        if (root == null) return false;
        if (root.value == value) return true;
        return value < root.value ? searchRec(root.left, value) : searchRec(root.right, value);
    }

    public void delete(int value) {
        root = deleteRec(root, value);
    }

    private Node deleteRec(Node root, int value) {
        if (root == null) return root;

        if (value < root.value)
            root.left = deleteRec(root.left, value);
        else if (value > root.value)
            root.right = deleteRec(root.right, value);
        else {
            if (root.left == null)
                return root.right;
            else if (root.right == null)
                return root.left;

            root.value = minValue(root.right);
            root.right = deleteRec(root.right, root.value);
        }

        return root;
    }

    private int minValue(Node root) {
        int minv = root.value;
        while (root.left != null) {
            minv = root.left.value;
            root = root.left;
        }
        return minv;
    }

    public void inorder() {
        inorderRec(root);
    }

    private void inorderRec(Node root) {
        if (root != null) {
            inorderRec(root.left);
            System.out.print(root.value + " ");
            inorderRec(root.right);
        }
    }
}

Advanced BST Concepts

Self-Balancing BSTs

Self-balancing BSTs like AVL trees and Red-Black trees automatically maintain the balance factor to ensure O(log n) complexity for all operations:

• AVL Tree: Balances based on the height of subtrees using rotations.
• Red-Black Tree: Balances using a color system and rotations.

Threaded BSTs

Threaded BSTs replace null pointers with links to the in-order successor to make in-order traversal faster.

Augmented BSTs

Augmented BSTs store additional information at each node for advanced queries like finding the kth smallest element.

Performance Analysis

The performance of BSTs is influenced by the tree’s balance:

• Balanced BST: Operations are O(log n).
• Unbalanced BST: Operations degrade to O(n) in the worst case.

Limitations of BSTs

• Degeneracy: An unbalanced BST can degrade to a linked list.
• Complex Rotations: Self-balancing trees have overhead due to rotations.
• Memory Overhead: Each node contains additional pointers.