二叉搜索树

查找问题是计算机中非常重要的基础问题

二分查找法

对于有序数组，才能使用二分查找法(排序作用)

public class BinarySearch {
    public static int binarySearch(Comparable[] arr, Comparable target) {

        if (arr == null || arr.length == 0) {
            return -1;
        }
        int n = arr.length;
        int l = 0, r = n - 1;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (arr[mid].compareTo(target) == 0) {
                return mid;
            } else if (arr[mid].compareTo(target) > 0) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }

        return -1;
    }
}

总结：

1. int mid = (low + high) / 2;如果low 和 high足够大时，low + high会越界。更好的写法为int mid = low + (high - low) / 2;
2. compareTo
   Returns:

a negative integer, zero, or a positive integer as this object is less than, equal to, or greater than the specified object.It is strongly recommended, but not strictly required that (x.compareTo(y)==0) == (x.equals(y)).

floor算法的实现

    public static int floor(Comparable[] arr, Comparable target) {
        if (arr == null || arr.length == 0) {
            return -1;
        }

        if (arr[0].compareTo(target) > 0) {
            return -1;
        }

        int n = arr.length;
        int l = 0, r = n - 1;
        int floor = 0;
        boolean found = false;
        while (l < r) {
            floor = l + (r - l) / 2;
            if (arr[floor].compareTo(target) == 0) {
                found = true;
                break;
            } else if (arr[floor].compareTo(target) > 0) {
                r = floor - 1;
            } else {
                l = floor + 1;
            }
        }
        if (found) {
            while (floor >= 1 && arr[floor - 1].compareTo(arr[floor]) == 0) {
                floor--;
            }
            return floor;
        } else {
            if (l == r) {
                if (arr[l].compareTo(target) < 0) {
                    return l;
                } else {
                    return (l - 1) >= 0 ? l - 1 : 0;
                }
            } else {
                return Math.min(l, r);
            }
        }
    }

总结：边界条件比较多，但是应该有更优的算法。算法复杂度应该为min(O(logn), O(m)),其中m为target元素重复的个数，即while循环中floor遍历的个数

二分搜索树

优势：为实现查找表这种数据结构，也即字典。

二分搜索树的优势

1. 不仅可以查找数据，还可以高效地插入，删除数据，动态维护数据
2. 可以方便地回答 很多 数据之间的关系问题

min max floor ceil rank select

特性:

1. 每个节点的键值大于左孩子
2. 每个节点的键值小于右孩子
3. 以左右孩子为根的子树仍为二分搜索树
4. 不一定是完全二叉树(用数组表示并不方便)

二叉搜索树的创建

package com.meituan.search;
class Node<K, V> {
    K key;
    V value;
    Node left;
    Node right;
    public Node(K key, V value) {
        this.key = key;
        this.value = value;
        this.left = this.right = null;
    }
}

public class BinarySearchTree {
    private Node root;
    int count;

    public BinarySearchTree() {
        this.root = null;
        this.count = 0;
    }

    public int size() {
        return count;
    }

    public boolean isEmpty() {
        return count == 0;
    }
}

插入新节点 insert

    public void insert(K key, V value) {
        root = insert(root, key, value);
    }

    private Node insert(Node node, K key, V value) {
        if (node == null) {
            count++;
            return new Node(key, value);
        }

        if (key == node.key) {
            node.value = value;
        } else if (key < node.key) {
            node.left = insert(node.left, key, value);
        } else {
            node.right = insert(node.right, key, value);
        }

        return node;
    }

总结：
私有方法返回一个node的原因是在退出递归时构建子树

查找元素

    /**
    * 返回值的方式
    * 1. 返回node，不好Node为内部类
    * 2. 返回Value
    */
    public V search(K key) {
        return search(root, key);
    }

    private V search(Node root, K key) {
        if (root == null) {
            return null;
        } 

        if (key == root.key) {
            return root.value;
        } else if (key < root.key) {
            return search(root.left, key)
        } else {
            return search(root.right, key);
        }
    }

遍历

前中后序遍历

1. 前序遍历

递归法

public void preOrderRec(Node root) {
    if (root == null) {
        return;
    }

    System.out.println(root.value);
    traverseRec(root.left);
    traverseRec(root.right);
}

迭代法
Stack可以解决，Queue无法解决

public void preOrder(Node root) {
    if (root == null) {
        return;
    }

    Stack<Node> stack = new Stack<>();
    stack.push(root);

    while (!stack.isEmpty()) {
        Node cur = stack.pop();
        System.out.println(cur.value);

        if (cur.right != null) {
            stack.push(cur.right);
        }

        if (cur.left != null) {
            stack.push(cur.left);
        }
    }
}

1. 中序遍历

递归法

public void preOrderRec(Node root) {
    if (root == null) {
        return;
    }

    traverseRec(root.left);
    System.out.println(root.value);
    traverseRec(root.right);
}

迭代法

public void inOrder(Node root) {
    if (root == null) {
        return;
    }

    Stack<Node> stack = new Stack<>();
    Node cur = root;
    while (true) {
        while (cur != null) {
            stack.push(cur);
            cur = cur.left;
        }

        if (stack.isEmpty()) {
            break;
        }

        cur = stack.pop();
        System.out.println(cur.value);
        cur = cur.right;
    }
}

1. 后序遍历

递归法

public void preOrderRec(Node root) {
    if (root == null) {
        return;
    }

    traverseRec(root.left);
    traverseRec(root.right);    
    System.out.println(root.value);
}

迭代法

public void inOrder(Node root) {
    if (root == null) {
        return;
    }

    Stack<Node> stack = new Stack<>();
    Stack<Node> out = new Stack<>();
    stack.push(root);

    while (!stack.isEmpty()) {
        Node cur = stack.pop();
        out.push(cur);

        if (cur.left != null) {
            stack.push(cur.left);
        }
        if (cur.right != null) {
            stack.push(cur.right);
        }
    }

    while (!out.isEmtpy()) {
        Node cur = out.pop();
        System.out.println(cur.value);
    }
}

广度优先遍历 （层序优先遍历）

public void levelOrder(Node root) {
    if (root == null) {
        return;
    }

    Queue<Node> queue = new LinkedList<>();
    queue.add(root);

    while (!queue.isEmpty()) {
        Node cur = queue.offer();
        System.out.println(cur.value);

        if (cur.left != null) {
            queue.add(cur.left);
        } 
        if (cur.right != null) {
            queue.add(cur.right);
        }
    }
}

删除节点

首先删除最小值和最大值

查找到最大值或最小值

K minimun() {
    if (count == 0) {
        return null;
    }

    return minimum(root).key;
}

K maximum() {
    if (count == 0) {
        return null;
    }
    return maximum(root);
}

private Node minimum(Node node) {
    if (node.left == null) {
        return node;
    }
    return minimun(node.left);
}

private Node maximum(Node node) {
    if (node.right == null) {
        return node;
    }
    return maximum(node.right);
}

删除最小值，找到最左子树，如果该子树还有右子树，将该右子树挂到被删除结点的位置上来

void removeMin() {
    if (root == null) {
        return;
    }

    root = removeMin(root);
}

private Node removeMin(Node node) {
    if (node.left == null) {
        count--;
        return node.right;
    }
    node.left = removeMin(node.left);
    return node;
}

删除最大值，找到最右子树，如果该子树还有左子树，将该左子树挂到被删除结点的位置上来

void removeMax() {
    if (root == null) {
        return;
    }
    root = removeMax(root);
}

private Node removeMax(Node node) {
    if (node.right == null) {
        count--;
        return node.left;
    }
    node.right = removeMax(node.right);
    return node;
}

删除任意结点

删除最大及最小值的算法，同样适用于只有左孩子或者右孩子的节点；难点在于，删除既有左孩子又有右孩子的节点

public Node deleteNode(Node node, K key) {
    if (node == null) {
        return;
    }
    if (key < node.key) {
        node.left = deleteNode(node.left, key);
        return node;
    } else if (key > node.key) {
        node.right = deleteNode(node.right, key);
        return node;
    } else {
        // node.key == key 
        if (node.left == null) {
            count--;
            return node.right;
        }
        if (node.right == null) {
            count--;
            return node.left;
        }

        Node successor = new Node(minimum(node.right).key, minimum(node.right).value);
        count++;
        successor.right = removeMin(node.right);
        successor.left = node.left;
        return successor;
    }
}

二分搜索树的局限性

二分搜索树可能退化成链表，改造方法是平衡二叉树，最著名的解决方法为红黑树

平衡二叉树和堆的结合：Treap