数据结构——二叉搜索树、Map和Set

对于不同的数据结构，他们的使用场景是不一样的，map和set这两种数据结构主要用在搜索相关的场景中。学习这些之前我们先来了解一下二叉搜索树，

一、搜索树

1.1概念

1.2 搜索树操作

1.2.1树的查找操作

代码如下：

 public TreeNode search(int val) {
        TreeNode cur = root;
        while (cur != null) {
            if (cur.val < val) {
                cur = cur.right;
            } else if (cur.val > val) {
                cur = cur.left;
            } else {
                return cur;
            }
        }
        return null;
    }

1.2.2树的插入操作

与树的查找操作一样，也需要与树的节点进行大小比较，cur的移动方法与查找相同，当我们还需要定义一个parent记录cur的父亲节点，当cur为空时，要插入的值就可以通过与parent节点的值比较大小来确定插入到parent的左节点还是右节点。

public void insert(int val) {
        if (root == null) {
            root = new TreeNode(val);
            return;
        }
        TreeNode cur = root;
        //记录cur的父亲节点
        TreeNode parent = null;
        while (cur != null) {
            parent=cur;
            if (val > cur.val) {
                cur = cur.right;
            } else if(val<cur.val){
                cur = cur.left;
            }else{
                //二叉搜索树不能有两个一样的值
                return;
            }
        }
        if(val>parent.val){
            parent.right=new TreeNode(val);
        }else{
            parent.left=new TreeNode(val);
        }
    }

1.2.3树的删除操作

实际上，在情况一和情况三中还分别有三种小情况：

代码如下：

private void removeNode(TreeNode parent, TreeNode cur) {
        //情况1：cur的左边为空
        if(cur.left==null){
            if(cur==root){
                //cur是根结点
                root=cur.right;
            }else if(parent.right==cur){
                //parent的右节点是cur
                parent.right=cur.right;
            }else if(parent.left==cur){
                //parent的左节点是cur
                parent.left=cur.right;
            }
        }else if(cur.right==null){//情况2：cur的右边为空
            if(cur==root){
                //cur是根结点
                root=cur.left;
            }else if(parent.right==cur){
                //parent的右节点是cur
                parent.right=cur.left;
            }else{
                //parent的左节点是cur
                parent.left=cur.left;
            }
        }else{//情况3：cur的左右都不为空
            TreeNode rightMin = cur.right;
            TreeNode parent2=cur;//记录rightMin的父亲节点
            while(rightMin.left!=null){
                parent2=rightMin;
                rightMin=rightMin.left;
            }
            //找到右树最小值,将cur.val覆盖,相当于删除了这个节点
            cur.val=rightMin.val;

            //删除rightMin节点，与情况一方法相同
             if(parent2.left==rightMin) {
                 parent2.left = rightMin.right;
             }else{
                 parent2.right=rightMin.right;
             }
        }
    }

1.2.4复杂度分析

！！！Map.Entry<k,v>中没有设置key的方法。 

3.1Map的常用方法

四、Set的使用

4.1Set的常用方法

！！！Map不能使用迭代器，只有Set才可以，原因是Map没有实现Iterable接口，但是我们可以使用entrySet方法将Map的键值对放入Set中，在通过Set使用迭代器间接遍历Map。

 public static void main(String[] args) {
       TreeSet<String> treeSet = new TreeSet<>();
        treeSet.add("abcd");
        treeSet.add("hello");
        treeSet.add("def");

        //判断元素是否存在于集合中，存在返回true
        System.out.println(treeSet.contains("hello"));

        //迭代器遍历
        Iterator<String> it = treeSet.iterator();
        while(it.hasNext()){
            System.out.println(it.next()+" ");
        }

    }

5.2冲突-避免-负载因子调节  

由于填入表中的元素个数是无法改变的，因此我们只能通过增加散列表的长度来降低负载因子。 

5.3冲突-解决-开散列/哈希桶 

5.4HashMap代码实现 

class HashBuck {
    //桶中的节点
    static class Node {
        public int key;
        public int val;
        public Node next;

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

    //负载因子大小
    public static final double DEFAULT_LOADFACTER = 0.75f;

    //数组
    public Node[] array = new Node[10];
    public int usedSize;

    //存放值
    public void push(int key,int val){
        int index = key % 10;//随便举例的一个哈希函数

        //首先要遍历对应链表，看是否已经存在key
        Node cur = array[index];
        while(cur!=null){
            if(cur.key==key){
                cur.val=val;
            }
            cur=cur.next;
        }

        //说明没有key节点
        Node node = new Node(key,val);
        node.next=array[index];
        array[index]=node;
        usedSize++;

        //计算负载因子大小
        if(doloadFactor()>=DEFAULT_LOADFACTER){
            //扩容
            reSize();
        }
    }

    private void reSize() {
        //注意不能直接拷贝到新数组，因为扩容后哈希函数已经发生了改变
        //需要重新遍历桶中的所有节点，重新把这些节点放到合适的桶中
        Node[] newArray = new Node[array.length*2];
        for (int i = 0; i < array.length; i++) {
            Node cur=array[i];

            while(cur!=null){
                int newIndex= cur.key% newArray.length;
                Node curN=cur.next;
                cur.next=newArray[newIndex];
                newArray[newIndex]=cur;
                cur=curN;
            }
        }
        //将array指向newArray即可
        array=newArray;
    }

    private double doloadFactor() {
        return usedSize*1.0/array.length;
    }


    public int getVal(int key){
        int index = key % 10;
        Node cur = array[index];
        while(cur!=null){
            if(cur.key==key){
               return cur.val;
            }
            cur=cur.next;
        }
        //没找到
        return -1;
    }

}

在对散列表进行reSize过程中，可能会遇到下面的问题：

5.5性能分析

5.6哈希表和Java类集的关系