[HL-7] Basic Data Structures and Algorithms

import java.util.ArrayList;
import java.util.List;

public class LinkedList<Item>
{
    private class Node
    {
        Item item;
        Node next;
    }

    private int N;
    private Node first;

    public LinkedList() {
        first = null;
        N = 0;
    }

    public void insertAtBeginning(Item item)
    {
        // save a link to the list
        Node oldfirst = first;
        // create a new node for the beginning
        first = new Node();
        // set the instance variables in the new node
        first.item = item;
        first.next = oldfirst;
        N++;
    }

    public void removeFromBeginning()
    {
        if (first == null) return;
        // remove the first node in a linked list
        first = first.next;
    }

    public void insertAtEnd(Item item)
    {
        // Time complexity: O(n)
        Node last = new Node();
        last.item = item;
        if (first == null) { first = last; return; }

        Node oldlast = first;
        while (oldlast.next != null)
            oldlast = oldlast.next;

        assert oldlast.next == null;
        oldlast.next = last;
    }

    public List<Item> array()
    {
        List<Item> items = new ArrayList<Item>();

        for (Node x = first; x != null; x = x.next)
            items.add(x.item);

        return items;
    }
}

public class BST<Key extends Comparable<Key>, Value>
{
    private Node root;

    private class Node
    {
        private Key key;
        private Value val;
        private Node left, right;
        private int N;

        public Node(Key key, Value val, int N)
        {
            this.key = key;
            this.val = val;
            this.N   = N;
        }
    }

    public int size()
    {
        return size(root);
    }

    private int size(Node x)
    {
        if (x == null) return 0;
        else           return x.N;
    }

    public Value search(Key key)
    {
        return search(root, key);
    }

    private Value search(Node x, Key key)
    {
        if (x == null) return null;
        int cmp = key.compareTo(x.key);
        if      (cmp < 0) return search(x.left, key);
        else if (cmp > 0) return search(x.right, key);
        else return x.val;
    }

    public void insert(Key key, Value val)
    {
        root = insert(root, key, val);
    }

    private Node insert(Node x, Key key, Value val)
    {
        if (x == null) return new Node(key, val, 1);
        int cmp = key.compareTo(x.key);
        if      (cmp < 0) x.left  = insert(x.left, key, val);
        else if (cmp > 0) x.right = insert(x.right, key, val);
        else x.val = val;
        x.N = size(x.left) + size(x.right) + 1;
        return x;
    }

    public Key min()
    {
        return min(root).key;
    }

    private Node min(Node x)
    {
        if (x.left == null) return x;
        return min(x.left);
    }

    public void deleteMin()
    {
        root = deleteMin(root);
    }

    private Node deleteMin(Node x)
    {
        if (x.left == null) return x.right;
        x.left = deleteMin(x.left);
        x.N = size(x.left) + size(x.right) + 1;
        return x;
    }

    // delete: replace x by its successor (smallest node in the right
    // subtree)
    public void delete(Key key)
    {
        root = delete(root, key);
    }

    private Node delete(Node x, Key key)
    {
        if (x == null) return null;
        int cmp = key.compareTo(x.key);
        if      (cmp < 0) x.left  = delete(x.left, key);
        else if (cmp > 0) x.right = delete(x.right, key);
        else
        {
            if (x.right == null) return x.left;
            if (x.left == null) return x.right;
            Node t = x;
            x = min(t.right);
            x.right = deleteMin(t.right);
            x.left = t.left;
        }
        x.N = size(x.left) + size(x.right) + 1;
        return x;
    }

    public static void main(String[] args)
    {
        BST<String, String> bst = new BST<String, String>();

        bst.insert("S","S");
        bst.insert("E","E");
        bst.insert("X","X");
        bst.insert("A","A");
        bst.insert("C","C");
        bst.insert("R","R");
        bst.insert("H","H");

        System.out.println(bst.search("H"));
        System.out.println(bst.size());
        bst.delete("H");
        System.out.println(bst.size());
        System.out.println(bst.search("H"));
    }
}

import java.util.Arrays;

public class BinarySearch
{
    public static int searchIterative(int key, int[] a)
    {
        int lo = 0;
        int hi = a.length - 1;
        while (lo <= hi)
        {
            int mid = lo + (hi - lo) / 2;
            if      (key < a[mid]) hi = mid - 1;
            else if (key > a[mid]) lo = mid + 1;
            else                   return mid;
        }
        return -1;
    }

    public static int searchRecursive(int key, int[] a)
    {
        return searchRecursiveHelper(key, 0, a.length-1, a);
    }

    private static int searchRecursiveHelper(int key, int lo, int hi, int[] a)
    {
        if (hi < lo) return -1;
        int mid = lo + (hi - lo) / 2;
        if      (key < a[mid]) return searchRecursiveHelper(key, lo, mid-1, a);
        else if (key > a[mid]) return searchRecursiveHelper(key, mid+1, hi, a);
        else                   return mid;
    }

    public static void main(String[] args)
    {
        int[] whitelist = new int[] {1,5,52,23,123,32,55,78,21,32};

        Arrays.sort(whitelist);

        System.out.println(searchIterative(1, whitelist));
        System.out.println(searchIterative(55, whitelist));
        System.out.println(searchIterative(32, whitelist));
        System.out.println(searchIterative(11, whitelist));

        System.out.println(searchRecursive(1, whitelist));
        System.out.println(searchRecursive(55, whitelist));
        System.out.println(searchRecursive(32, whitelist));        
        System.out.println(searchRecursive(11, whitelist));
    }
}