【数据结构】Java中Map和Set详解（含二叉搜索树和哈希表）

public class BinarySearchTree {
    public static class Node {
        int key;
        Node left;
        Node right;
        public Node(int key) {
            this.key = key;
        }
    }
    private Node root = null;
    /**
     * 在搜索树中查找 key，如果找到，返回 key 所在的结点，否则返回 null
     * @param key
     * @return
     */
    public Node search(int key) {
        Node cur = root;
        while (cur != null) {
            if (key == cur.key) {
                return cur;
            } else if (key < cur.key) {
                cur = cur.left;
            } else {
                cur = cur.right;
            }
        }
        return null;
    }
    /**
     * 插入
     * @param key
     * @return true 表示插入成功, false 表示插入失败
     */
    public boolean insert(int key) {
        if (root == null) {
            root = new Node(key);
            return true;
        }
        Node cur = root;
        Node parent = null;
        while (cur != null) {
            if (key == cur.key) {
                return false;
            } else if (key < cur.key) {
                parent = cur;
                cur = cur.left;
            } else {
                parent = cur;
                cur = cur.right;
            }
        }
        Node node = new Node(key);
        if (key < parent.key) {
            parent.left = node;
        } else {
            parent.right = node;
        }
        return true;
    }
    /**
     * 删除成功返回 true，失败返回 false
     * @param key
     * @return
     */
    public boolean remove(int key) {
        return delete(root,key);
    }
    private boolean delete(Node root,int key){
        /*
根据cur的孩子是否存在分四种情况
1. cur左右孩子均不存在
2. cur只有左孩子
3. cur只有右孩子
4. cur左右孩子均存在
看起来有四种情况，实际情况1可以与情况2或者3进行合并，只需要处理是那种情况即可
除了情况4之外，其他情况可以直接删除
情况4不能直接删除，需要在其子树中找一个替代节点进行删除
*/
        Node cur = root;
        Node parent = null;
        while (cur != null) {
            if (key == cur.key) {
                break;
            } else if (key < cur.key) {
                parent = cur;
                cur = cur.left;
            } else {
                parent = cur;
                cur = cur.right;
            }
        }
// 该元素不在二叉搜索树中
        if(null == cur){
            return false;
        }
//由于二叉查找树的性质，如果将当前节点替换为左子树中最大的或者右子树中最小的一定不会破坏二叉查找树的结构。
        if((cur.left!=null&&cur.right==null)||(cur.left==null&&cur.right==null)){
            cur=cur.left;
        }else if(cur.left==null&&cur.right!=null){
            cur=cur.right;
        }else{
            int val=SearchleftMax(cur.left);
            cur.key=val;
            delete(cur.left,val);
        }
        return true;
    }

    private int SearchleftMax(Node left) {
        if(left==null){
            return 0;
        }
        if(left.right==null){
            return left.key;
        }
        return SearchleftMax(left.right);
    }

}