一、二叉搜索树
1、概述
二叉搜索树上的每一个结点其左子树的值小于根结点的值并且右子树的值大于根结点的值，对二叉搜索树进行中序遍历就能得到一个有序序列，所以二叉搜索树又称二叉排序树。
如下就是一棵二叉搜索树：
2、模拟实现搜索二叉树
二叉搜索树的结点由左子树右子树和数据域组成。
static class TreeNode { public int val; public TreeNode left; public TreeNode right; public TreeNode(int val) { this.val = val; } }
a、向搜索二叉树中插入数据
首先将待插入的数据包装为一个结点，如果搜索二叉树为空，这个二叉树的根结点就是待插入的结点，若二叉树不为空，就对二叉树进行遍历，并且需要定义一个结点表示遍历结点的父结点，要不然最后进行插入的时候找不到父结点。如果二叉树结点的值小于待插入的数据那么就继续遍历其右子树，如果二叉树结点的值大于待插入的数据那么就继续遍历其左子树，否则就表示二叉树中有待插入数据的结点，遍历结束后，如果带插入的值小于父结点的值，就插入为父结点的左子树结点否则插入为父结点的右子树结点。
public void insert(int val){ TreeNode node = new TreeNode(val); if(root == null){ root = node; return; } TreeNode cur = root; TreeNode parent = cur; while(cur != null){ if(cur.val == val){ return; }else if(cur.val < val){ parent = cur; cur = cur.right; }else{ parent = cur; cur = cur.left; } } if(val < parent.val){ parent.left = node; }else{ parent.right = node; } }
b、查找二叉搜索树的指定值的结点
若二叉树不为空，就遍历二叉树，如果找到结点值等于指定值，则返回该结点，若遍历的结点值小于指定值就遍历左子树否则遍历右子树。若遍历结束还未找到那么二叉树中就没有指定的结点。
public TreeNode find(int val) { if(root==null){ return null; } TreeNode cur = root; while(cur != null){ if(cur.val == val){ return cur; }else if(cur.val > val){ cur = cur.left; }else{ cur = cur.right; } } return null; }
c、删除二叉树的指定值的结点
首先在二叉树中查找是否存在待删除的结点cur并记录其父结点parent，若存在则存在以下几种情况：
- 若cur.left = null，如果cur = root,则root = cur.right，如果parent.left = cur,则parent.left = cur.right,如果parent.right = cur,则parent.left = cur.right.
- 若cur.right = null，如果cur = root,则root = cur.left，如果parent.left = cur,则parent.left = cur.left,如果parent.right = cur,则parent.left = cur.left.
- 若cur.left != null && cur.left ！=null，就需要找到cur的左子树的最大值结点node或右子树的最小值结点node，让cur的结点值等于node的结点值，然后再利用前两种情况删除node结点。
public boolean delete(int val){ //先找到指定的结点 if(root==null){ return false; } TreeNode cur = root; TreeNode parent = cur; while(cur != null){ if(cur.val == val){ break; }else if(cur.val > val){ parent = cur; cur = cur.left; }else{ parent = cur; cur = cur.right; } } //未找到指定结点 if(cur == null){ return false; } if(cur.left == null){ if(cur == root){ root = root.right; }else if(parent.left == cur){ parent.left = cur.right; }else{ parent.right = cur.right; } }else if(cur.right == null){ if(cur == root){ root = cur.left; }else if(parent.left == cur){ parent.left = cur.left; }else{ parent.right = cur.left; } }else{ TreeNode target = cur.left; while(target.right != null){ parent = target; target = target.right; } cur.val = target.val; if(parent.right == target){ parent.right = target.left; } if(parent.left == target){ parent.left = target.left; } } return true; }
3、对二叉搜索树进行性能分析
二叉搜索树主要用于查找，若二叉搜索树每个结点的查找概率相等，那么：
- 最优情况下，二叉搜索树变为完全二叉树，平均比较次数为log2 n；
- 最坏情况下，二叉搜索树变为单枝树，平均比较次数为n/2;
二、Map的使用
1、Map简介
Map是一个接口，但并没有继承Collection类，存放的是Key-Value键值对。Key都有与之对应的Value，Map中Key是惟一的，但Value并不唯一。
Map.Entey<K,V>是Map用于来存放键值对映射关系的内部类。该类主要提供有getKey()、getValue()、setValue()方法，并没有setKey的方法。
2、Map常用方法
说明：
Map只是一个接口并不能实例化对象，但可以利用TreeMap或HashMap来实例化对象。
在插入数据时，Key不能为空，但Value可以为空。
Map中所有的Key可以全部存储到Set中来进行访问，因为Key没有重复。
Map中所有的Value也可以分离，存储到Collection的某一个子集中。
Map中的Key无法修改，但是可以删除Key然后再重新插入Key。
TreeMap和HashMap的区别：
三、Set的使用
1、Set简介
Set也是一种数据集合，用于存放不重复的数据Key，Set是继承Collection类的接口，利用HashSet和TreeSet可以实例化对象。
2、Set常用方法
说明：
- Set是一个接口类。
- Set类似于数学中的集合，存放的是不重复的元素，利用Set这一特点可以对集合中的元素进行去重。
- Set中的元素也是不能直接修改的，需要先删除然后将重新修改好的元素再进行插入。
- LinkedHashSet是在HashSet的基础上维护了一个双向链表来记录元素的插入次序。
- TreeSet中不能插入空值，但是HashSet可以插入空值。
TreeSet和HashSet的区别：
四、哈希表
1、概念
哈希表也称为散列表，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
常见的散列函数：Hash(key) = key % p, p 通常取小于等于地址空间的最大质数。
2、冲突
a、冲突的概念
在利用散列函数计算哈希地址时通常可能会出现多个关键码计算出相同的哈希地址，这就是发生了冲突。
b、冲突的解决方案
负载因子：散列表中的元素数 / 散列表的长度。
冲突与散列因子也有如下关系：
如果负载因子较小，发生冲突的概率也会降低。
（闭散列）开放地址法
当发生冲突时，如果散列表还没有被填满就可以将元素放到空的位置，那么放到那个空位置？又有如下的解决方案：
线性探测法：当关键码计算出哈希地址时，如果此时哈希地址对应的位置已经有元素时，就移向下一个位置，如果下一个位置还有元素就继续向后移，直至发现空位置为止，就将该元素填入到空位置。
缺点：发生冲突的位置发生聚集。
二次探测法：空位置的寻找函数：Hash(key) = (d + i^2)%m（i=1,2,3,……）,d为初始计算的哈希地址，m为散列表的长度。初次时i=1，若计算出的Hash地址不为空时，就让i=2继续计算Hash地址直至找到空位置。
（开散列）链地址法
利用哈希函数计算出哈希地址之后，每个位置利用链表来存放哈希地址相同的元素。
利用链地址法模拟实现：
结点：由Key域、Value域和next域组成。
static class Node{ int val; int key; Node next; public Node(int key,int val){ this.key = key; this.val = val; } }
存放元素：首先利用key计算出哈希地址，若哈希地址的位置链表为空，就将新插入的结点设置为首元结点，否则就遍历链表若有相同的key值则就将Value值进行更新，接着利用尾插法插入元素，然后哈希表的有效长度加1，还要计算此时的负载因子，如果负载因子大于0.75，说明冲突太高了就需要扩容，扩容是遍历哈希表中的所有元素，重新计算哈希地址，再利用尾插法插入元素。
代码实现：
public void put(int key,int value){ //计算哈希地址 int index = key % array.length; Node cur = array[index]; //遍历链表 //链表为空 if(cur == null){ array[index] = new Node(key,value); }else{ Node preNode = null; while(cur != null){ preNode = cur; //相同关键码更新Value值 if(cur.key == key){ cur.val = value; return; } cur = cur.next; } //尾插法插入元素 preNode.next = new Node(key,value); } this.usedSize++; //计算负载因子 double load = 1.0 * usedSize / array.length; if(load >= 0.75){ //扩容 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 index = cur.key % newArray.length; Node nextNode = cur.next; Node node = newArray[index]; if(node == null){ newArray[index] = cur; }else{ Node pre = null; while(node != null){ pre = node; node = node.next; } pre.next = node; cur = nextNode; } } } array = newArray; }
获取key值对应的Value值：计算出哈希地址，对哈希地址所对应的哈希链表进行遍历，找到相同的key值，就返回Value值。
public int getValue(int key){ int index = key % array.length; Node cur = array[index]; while (cur != null){ if(cur.key == key){ return cur.val; } cur = cur.next; } return -1; }
注意：以上只是模拟实现，哈希地址的计算存在不足，一般向HashMap中加入元素时，该元素类需要重写HashCode()方法，利用该方法可以计算出哈希地址。
五、面试题
1、问答题
a、如果new HashMap(19),bucket数组多大？
答：32，bucket数组为>=19并且是最接近19的一个2次幂。
b、HashMap在什么时候会开辟bucket数组占用内存？
答：第一次加入元素时，会开辟大小为16的数组。
c、HashMap会在什么时候扩容？
答：负载因子大于负载因子，并且是进行2倍扩容。
d、如果两个关键码的哈希地址相同，会发生什么？如何获取值对象？
答：两个关键码的哈希地址相同会发生冲突，获取值对象时：遍历哈希哈希地址所对用的链表，然后利用equals()方法比较是否有与其关键码相同的元素，若有则可以找到，否则找不到。
e、在HashMap扩容时需要注意什么问题？
答：需要对原有的哈希表的元素进行遍历，并且重新计算出哈希地址，将元素插入到哈希地址所对应的链表中。
2、在线OJ题
a、只出现一次的数字
解题思路：定义一个set对象，遍历数组，如果set包含该元素就删除，否则就加入，二次再遍历数组，如果set包含遍历的元素，就直接返回该元素。
public int singleNumber(int[] nums) { Set<Integer> set = new HashSet<>(); for(int i = 0;i < nums.length;i++){ if(set.contains(nums[i])){ set.remove(nums[i]); }else{ set.add(nums[i]); } } for(int i = 0;i < nums.length;i++){ if(set.contains(nums[i])){ return nums[i]; } } return -1; }
解题思路：由于链表中的结点带有随机指针，就可以利用Map中存放键值对的形式，将原有链表的结点记为Key，新复制的链表结点记为Value，先遍历原链表，并创建新复制的结点，将两者添加到map中去，再次遍历链表得到原结点对应的新结点，新结点的next和random结点就是原结点next结点和random结点的Value值，最后返回原链表首元结点对应的Value，即为新复制链表的首元结点。
public Node copyRandomList(Node head) { Map<Node,Node> map = new HashMap<>(); Node cur = head; while(cur != null){ Node node = new Node(cur.val); map.put(cur,node); cur = cur.next; } cur = head; while(cur != null){ Node node = map.get(cur); node.next = map.get(cur.next); node.random = map.get(cur.random); cur = cur.next; } return map.get(head); }
c、宝石与石头
解题思路：首先将宝石中的所有字符添加到se中，然后遍历石头，如果set中包含石头中的字符，宝石数加一，重复上述步骤，直至遍历结束。
public int numJewelsInStones(String jewels, String stones) { Set<Character> set = new HashSet<>(); for(int i = 0;i < jewels.length();i++){ char ch = jewels.charAt(i); set.add(ch); } int count = 0; for(int i = 0;i < stones.length();i++){ if(set.contains(stones.charAt(i))){ count++; } } return count; }
d、旧键盘
解题思路：首先可以将实际输出的字符全部存储到set中，再定义一个set对象broken，还需要定义一个StringBuilder对象stringBuilder来确保输出的元素时有序的。遍历输入的字符串，如果broken不包含所遍历的元素就将元素添加到broken中 和StringBuilder中，直至遍历结束。
public static String keyboard(String s1,String s2){ Set<Character> set = new HashSet<>(); Set<Character> broken = new HashSet<>(); StringBuilder stringBuilder = new StringBuilder(); s1 = s1.toUpperCase(); s2 = s2.toUpperCase(); for(int i = 0;i < s2.length();i++){ set.add(s2.charAt(i)); } for(int i = 0;i < s1.length();i++){ if(!set.contains(s1.charAt(i))){ if(!broken.contains(s1.charAt(i))){ broken.add(s1.charAt(i)); stringBuilder.append(s1.charAt(i)); } } } return stringBuilder.toString(); }
e、 前k个高频单词
解题思路：这就是典型的top-k问题，首先遍历字符串数组，将其中出现的字符串和对应出现的次数存放到map中，然后创建一个小根堆，在实现比较器时注意题目要求若两个字符串出现的频率相等就按词典进行排序，但是用小根堆每次弹出的是最小元素，所以最后要对排序的结果逆置，所以若两个字符串出现的频率相等就按词典的逆序进行排序遍历map，先存储k个元素，继续向后遍历，若还有元素的出现次数大于堆顶元素出现的次数，就弹出堆顶元素，将该元素加入到堆中，若元素出现的次数等于堆顶元素出现的次数，就比较元素的key值，遍历结束后，对小根堆进行遍历，将堆顶元素每次弹出到链表中，最后对链表进行逆置。
public List<String> topKFrequent(String[] words, int k) { Map<String,Integer> map = new HashMap<>(); for(int i = 0; i < words.length;i++){ if(map.get(words[i]) == null){ map.put(words[i],1); }else{ int value = map.get(words[i]); map.put(words[i],value+1); } } PriorityQueue<Map.Entry<String,Integer>> priorityQueue =new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() { @Override public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) { if(o1.getValue().compareTo(o2.getValue()) == 0){ return o2.getKey().compareTo(o1.getKey()); } return o1.getValue() - o2.getValue(); } }); int count = 0; for (Map.Entry<String, Integer> stringIntegerEntry : map.entrySet()) { if(count < k){ priorityQueue.offer(stringIntegerEntry); }else{ Map.Entry<String, Integer> peek = priorityQueue.peek(); if(peek.getValue() == stringIntegerEntry.getValue()){ if(peek.getKey().compareTo(stringIntegerEntry.getKey())>0){ priorityQueue.poll(); priorityQueue.offer(stringIntegerEntry); } }else{ int val = peek.getValue(); if(val < stringIntegerEntry.getValue()){ priorityQueue.poll(); priorityQueue.offer(stringIntegerEntry); } } } count++; } List<String> list = new LinkedList<>(); while(!priorityQueue.isEmpty()){ Map.Entry<String, Integer> poll = priorityQueue.poll(); list.add(poll.getKey()); } Collections.reverse(list); return list; }
