【数据结构】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);
    }
 
}

 性能分析：       

1. Set是继承自Collection的一个接口类
2. Set中只存储了key，并且要求key一定要唯一
3. TreeSet的底层是使用Map来实现的，其使用key与Object的一个默认对象作为键值对插入到Map中的
4. Set最大的功能就是对集合中的元素进行去重
5. 实现Set接口的常用类有TreeSet和HashSet，还有一个LinkedHashSet，LinkedHashSet是在HashSet的基础上维护了一个双向链表来记录元素的插入次序。
6. Set中的Key不能修改，如果要修改，先将原来的删除掉，然后再重新插入
7. TreeSet中不能插入null的key，HashSet可以。