datastructures8BinarySearchTree

1package pkg3datastructures;2 3/*4 * datastructures8BinarySearchTree.java5 * ---------------------6 * A BST: left < node < right. Supports insert, search, delete, and in-order7 * traversal (which yields sorted output).8 *9 * COMPLEXITY: O(h) per op where h is height; O(log n) if balanced, O(n) if skewed.10 * WHEN TO USE: ordered data with fast search/insert/delete; range queries.11 */12import java.util.*;13 14public class datastructures8BinarySearchTree {15 16    static class Node {17        int val; Node left, right;18        Node(int val) { this.val = val; }19    }20 21    private Node root;22 23    void insert(int v) { root = insert(root, v); }24    private Node insert(Node n, int v) {25        if (n == null) return new Node(v);26        if (v < n.val) n.left = insert(n.left, v);27        else if (v > n.val) n.right = insert(n.right, v);   // ignore duplicates28        return n;29    }30 31    boolean contains(int v) {32        Node n = root;33        while (n != null) {34            if (v == n.val) return true;35            n = v < n.val ? n.left : n.right;36        }37        return false;38    }39 40    void delete(int v) { root = delete(root, v); }41    private Node delete(Node n, int v) {42        if (n == null) return null;43        if (v < n.val) n.left = delete(n.left, v);44        else if (v > n.val) n.right = delete(n.right, v);45        else {46            // Found: handle 0, 1, or 2 children47            if (n.left == null) return n.right;48            if (n.right == null) return n.left;49            Node successor = min(n.right);     // in-order successor50            n.val = successor.val;51            n.right = delete(n.right, successor.val);52        }53        return n;54    }55 56    private Node min(Node n) { while (n.left != null) n = n.left; return n; }57 58    void inorder(Node n, List<Integer> out) { if (n == null) return; inorder(n.left, out); out.add(n.val); inorder(n.right, out); }59    List<Integer> sorted() { List<Integer> out = new ArrayList<>(); inorder(root, out); return out; }60 61    public static void main(String[] args) {62        datastructures8BinarySearchTree bst = new datastructures8BinarySearchTree();63        for (int x : new int[]{50, 30, 70, 20, 40, 60, 80}) bst.insert(x);64        System.out.println("in-order (sorted): " + bst.sorted());65        System.out.println("contains 60: " + bst.contains(60) + " | contains 99: " + bst.contains(99));66 67        bst.delete(20);                 // leaf68        bst.delete(30);                 // one child69        bst.delete(50);                 // two children (root)70        System.out.println("after deletes: " + bst.sorted());71    }72}