一、二叉搜索树
1、概念
（1）二叉搜索树 要么是一棵空树，要么就得满足左子树上所有结点的值都小于根结点的值，右子树上所有结点的值都大于根结点的值，即左边比我小，右边比我大。二叉树的左右子树也分别都是二叉搜索树。
（2）二叉搜索树 的存储结构（物理结构）：链式存储
（3）二叉搜索树 查找元素的效率很高，每次砍一半，效率是二叉树的高度logn。但当这个二叉搜索树是单支树时，查找效率就变成 n 了。所以有了红黑树来解决单支树的查找效率问题。
2、实现一棵二叉搜索树
- 1、查找
- 2、插入
- 3、删除
删除的思路：
首先找到要删除的节点cur，分为3种情况：要删除的节点没有左子树，要删除的节点没有右子树，要删除的节点左右子树都有，分别进行讨论。
这三种情况中也有分支，分为3种：cur 是root，cur是父结点prev的左子结点，cur是父结点prev的右子结点。
对于要删除的节点左右子树都有的情况，使用“替罪羊法”进行删除，找到cur左子树中的最大值（即左子树的最右边）或右子树的最小值（即右子树的最左边），这个结点mCur就是“替罪羊”，把此节点的值赋给cur，变成删除mCur这个节点。如果mCur是右子树的最左边，那么mCur要么没有子树，要么只有右子树（即没有左子树），这就好做了。
public class MyBinarySearchTree {
static class TreeNode{
private int val;
private TreeNode left;
private TreeNode right;
public TreeNode(int val){
this.val = val;
}
}
public TreeNode root = null;
//1、查找：时间复杂度 O(logn)
public TreeNode search(int data){
TreeNode cur = root;
while(cur != null){
if(data < cur.val){
cur = cur.left;
}else if(data > cur.val){
cur = cur.right;
}else{
return cur;
}
}
return null;
}
//2、插入
public boolean add(int data){
TreeNode node = new TreeNode(data);
if(root == null){
root = node;
return true;
}
TreeNode prev = null;
TreeNode cur = root;
while(cur != null){
if(data < cur.val){
prev = cur;
cur = cur.left;
}else if(data > cur.val){
prev = cur;
cur = cur.right;
}else{
return false;
}
}
if(data < prev.val){
prev.left = node;
}else{
prev.right = node;
}
return true;
}
//3、删除
//替罪羊法
public void remove(int data){
TreeNode prev = null;
TreeNode cur = root;
while(cur != null){
if(data < cur.val){
prev = cur;
cur = cur.left;
}else if(data > cur.val){
prev = cur;
cur = cur.right;
}else{
//找到了，进行删除，cur就是要删除的节点
removeNode(prev,cur);
}
}
}
public void removeNode(TreeNode prev,TreeNode cur){
//分为3种情况：要删除的节点没有左子树，要删除的节点没有右子树，要删除的节点左右子树都有
if(cur.left == null){
if(cur == root){
root = root.right;
}else if(cur == prev.left){
prev.left = cur.right;
}else{
prev.right = cur.right;
}
}else if(cur.right == null){
if(cur == root){
root = root.left;
}else if(cur == prev.left){
prev.left = cur.left;
}else{
prev.right = cur.left;
}
}else{
//cur 的左树和右树都不为空
//找右树的最小值的节点（即右树的最左边），将值赋给data，替换成删除这个节点
TreeNode mPrev = cur;
TreeNode mCur = cur.right;
while(mCur.left != null){
mPrev = mCur;
mCur = mCur.left;
}
//mCur就是右树的最左边，mCur要么没有子树，要么只有右树
cur.val = mCur.val;
if(mCur == mPrev.left){
mPrev.left = mCur.right;
}else{
mPrev.right = mCur.right;
}
}
}
}
二、Map 和 Set
1、Map
1、Map是接口，不能直接实例化，只能实例化其实现类TreeMap或HashMap
2、Map是key-value模型，里面存的是<K,V>结构的键值对
3、Map中存放的键值对，key是不可重复的，value是可以重复的。第二次放入已经存在的key，会进行value值覆盖。
4、Map中的key可以全部分离出来，存储到Set中
5、Map中的value可以全部分离出来，存储到Collection中
6、Map中的key不能修改，value可以修改。如果想修改key，只能删掉重新插入。
Map.Entry<K,V>：键值对的类型
Map.Entry<K,V> 是Map接口的一个内部接口，用来存放<key, value>键值对映射关系。相当于，把key-value看做是一个整体，这个键值对的类型就是Map.Entry<K,V>
TreeMap 实现了 Map接口，TreeMap中的内部类 Entry<K,V> 实现了Map.Entry<K,V>，重写了Map.Entry<K,V>中的抽象方法。
Map.Entry<K,V> 接口中的方法：
- K getKey()：返回键值对中的 key
- V getValue()：返回键值对中的 value
- V setValue(V value)：把键值对中的value替换为指定 value
Map中的方法：
- V put(key,value)：设置key对应的value
- V get(key)：返回 key 对应的 value，key 不存在，返回 null
- V getOrDefault(key,defaultValue)：返回 key 对应的 value，key 不存在，返回默认值
- V remove(key)：删除 key 对应的映射关系，即删除这个键值对
- boolean containsKey(key)：判断是否包含 key
- boolean containsValue(value)：判断是否包含 value
- Set<K> keySet()：返回所有 key 的不重复集合
- Collection<V> values()：返回所有 value 的集合
- Set<Map.Entry<K,V>> entrySet()：返回所有的 key-value 映射关系。调用这个函数，会将key-value变成一个整体，并将其乱序放入Set集合中，Set集合中的每个元素都是Map.Entry<K,V>类型。
public static void main(String[] args) {
TreeMap<String,Integer> map = new TreeMap<>();
//1、设置 key 对应的 value
map.put("hello",6);
map.put("abc",6);
map.put("world",3);//hello 左边是 abc，右边是 world
System.out.println(map);
//2、返回 key 对应的 value,key 不存在，返回 null
Integer value = map.get("hello");
System.out.println("hello = "+value);
//3、返回 key 对应的 value,key 不存在，返回 默认值
Integer v = map.getOrDefault("h",0);
System.out.println("h = "+v);
//4、删除 key 对应的映射关系，即删除这对键值对
map.remove("world");
System.out.println(map);
//5、判断是否包含 key
boolean flag = map.containsKey("world");
System.out.println("key中是否包含world呢："+flag);
//6、判断是否包含 value
boolean flag2 = map.containsValue(6);
System.out.println("value中是否包含6呢："+flag2);
//7、返回所有 key 的不重复集合
Set<String> set = map.keySet();
System.out.println("所有 key 的不重复集合："+set);
//8、返回所有 value 的集合
Collection<Integer> collection = map.values();
System.out.println("所有 value 的集合："+collection);
//9、返回所有的 key-value 映射关系
// 相当于把key-value看成一个整体，放进 Set 这个集合里
Set<Map.Entry<String,Integer>> entrySet = map.entrySet();
//entry 是 key-value这个整体，entrySet是装 键值对的 集合
System.out.println("输出所有的键值对：");
for (Map.Entry<String,Integer> entry:entrySet) {
//遍历集合，拿到的每个元素都是一对键值对
System.out.println(entry.getKey()+"="+entry.getValue());
}
} 
2、Set
1、Set是接口，不能直接实例化，只能实例化其实现类TreeSet或HashSet
2、Set是纯key模型
3、Set的底层是使用Map来实现的，使用key和Object的一个默认对象作为键值对插入到Map中
4、key不能重复，第二次放入已经存在的key，key还是只有一个
5、Set中的key不能修改，如果想修改key，只能删掉重新插入。
6、Set的应用场景：对集合中的元素进行去重
Set中的方法：
- boolean add(key) 添加
- boolean remove(key) 删除
- boolean contains(key) 是否包含某元素
3、Map 和 Set 的区别和联系
1、Map和Set都是接口，都不能直接实例化，只能实例化其实现类
2、Map是key-value模型，Set是纯key模型
3、Map和Set中的key都不能重复
4、Map和Set中的key都不能修改，想修改只能删掉重新插入
5、Map适合用于统计元素个数（如：统计元素出现的次数或统计第一个不重复的元素），Set适合用于对元素进行去重（如：统计不重复的元素或第一个重复的元素）
三、TreeSet 和 TreeMap
TreeSet 和 TreeMap 的区别和联系：
1、TreeSet 和 TreeMap 背后的数据结构是红黑树，红黑树是一棵特殊的二叉搜索树。
2、TreeSet是纯 key 模型，TreeMap是 key-value 模型，里面存的是<K,V>结构的键值对
3、往TreeSet 或 TreeMap 里放元素时，key必须是可以比较的，否则会报类型转换异常
4、往TreeSet 或 TreeMap 里放元素时，key不能为null，否则会报空指针异常
4、TreeSet 和 TreeMap 中都不会存在两个相同的key，key是不可重复的，也不能修改
四、HashSet 和 HashMap
1、哈希表（或散列表）
如果想从一组元素中查找某个元素，我们可能会想到以下方法：
1、将元素存储数组，然后遍历数组进行查找，时间复杂度O(n)
2、如果元素是有序的，使用二分查找，时间复杂度是O(logn)
3、利用搜索树进行查找，时间复杂度是O(logn)
有一种数据结构，查找元素的时间复杂度可以达到O(1)，它就是哈希表。
哈希表的概念：
哈希表是通过哈希函数映射得到的一种结构，哈希表本身是一个数组。
通过哈希函数使元素的存储位置与它的key之间能够建立一一映射的关系，在查找时通过该函数可以不经过任何比较，一次直接从表中得到要搜索的元素，时间复杂度可以达到O(1)
但是，可能会出现不同的key通过哈希函数计算得到相同的哈希地址，就会出现哈希冲突/哈希碰撞
2、哈希冲突/哈希碰撞
由于哈希表底层数组的容量往往是小于实际要存储的key的数量的，所以哈希冲突/哈希碰撞是必然存在的。但我们可以降低哈希冲突发生的概率。
降低哈希冲突率的方法：
1、设计合理的哈希函数：
直接定制法：取key的某个线性函数为散列地址：Hash（key）= A*key + B
除留余数法：设散列表中允许的地址数为m，Hash(key) = key% p(p<=m)
2、调节负载因子
因为负载因子越大，冲突率越高，而负载因子=填入表中的元素个数/哈希表的长度，
哈希表中的元素个数不可修改，那么就只能调节哈希表的长度。
哈希表中数组越大，冲突率就越小。一般情况下，哈希表有一个默认的负载因子0.75f，负载因子超过0.75f，会将哈希表中的数组进行扩容来降低负载因子。
上述两种方式只能降低哈希冲突发生的概率，那么如何解决哈希冲突呢？
3、解决哈希冲突 —— 开散列（哈希桶）
解决哈希冲突的两种常见的方法是：闭散列和开散列
闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空
位置，那么可以 把key存放到冲突位置中的“下一个” 空位置中去。寻找空位置的方法有两种：线性
探测和二次探测。
在Java中，我们使用的是开散列的方法，也叫做哈希桶。
开散列（哈希桶）：开散列法又叫链地址法(开链法)，首先对key集合用散列函数计算散列地址，
具有相同地址的key归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表
链接起来，各链表的头结点存在哈希表中。开散列中每个桶中放的都是发生哈希冲突的元素。
哈希桶是数组+链表的结构，把冲突的放到对应的一个链表里面。在合适的情况下，链表会变成红
黑树。jdk1.7及以前，采用的是头插法；jdk1.8开始采用的是尾插法。
4、HashSet 和 HashMap 的区别和联系：
1、HashSet 和 HashMap 背后的数据结构是 数组+链表
2、HashSet是纯 key 模型，HashMap是 key-value 模型，里面存的是<K,V>结构的键值对
3、往HashSet或 HashMap 里放元素时，key不需要可比较
4、往HashSet或 HashMap 里放元素时，key可以为null
5、HashSet 和 HashMap 中都不会存在两个相同的key，key是不可重复的，也不能修改
5、HashMap的一些说明
1、HashMap调用不带参数的构造方法，默认容量是0。第一次put的时候，才会给HashMap分配内存，内存大小是16
2、HashMap调用一个参数（参数是容量）的构造方法，分配的内存不是你传的容量，是>=容量，且最接近容量的2的次幂。
3、hashcode和equals的区别：两个对象的hashcode相同，equals不一定相同；两个对象的equals相同，说明肯定是同一个对象，hashcode一定相同。
4、当HashMap满了时，需要注意什么？要将哈希表中的每个元素都重新进行哈希。
5、什么时候会变成树？链表的长度>=8，哈希表的容量>=64 同时满足才会从链表变成树
五、TreeMap(或TreeSet) 和 HashMap(或HashSet) 的区别和联系
1、背后的数据结构不同，TreeMap背后的数据结构是红黑树，HashMap背后的数据结构是 数组+链表
2、往TreeMap 里放元素时，key必须是可以比较的；往HashMap 里放元素时，key不需要可比较
3、往TreeMap 里放元素时，key不能为null；往HashMap 里放元素时，key可以为null
4、TreeMap 和 HashMap 中都不会存在两个相同的key，key是不可重复的，也不能修改
5、TreeMap查找/插入/删除的时间复杂度是O(logn)，HashMap查找/插入/删除的时间复杂度O(1)
六、题目
1、统计10w个数据当中，不重复的数据 Set
public static void func(int[] array){
//去重，Set是天然去重的，把数据放到Set里
HashSet<Integer> set = new HashSet<>();
for (int i = 0; i < array.length; i++) {
set.add(array[i]);
}
System.out.println(set);
}2、统计10w个数据当中，第一个重复的数据 Set
public static void func2(int[] array){
HashSet<Integer> set = new HashSet<>();
for (int i = 0; i < array.length; i++) {
if(!set.contains(array[i])){
set.add(array[i]);
}else{
System.out.println(array[i]);
return;
}
}
}3、统计10w个数据当中，每个数据出现的次数 Map
public static void func3(int[] array){
HashMap<Integer,Integer> map = new HashMap<>();
//使用map，遍历数组，如果map中没有此数据，就放进去，如果已经有此数据了，value就+1
for (int i = 0; i < array.length; i++) {
if(!map.containsKey(array[i])){
map.put(array[i],1);
}else{
int value = map.get(array[i]);
map.put(array[i], value+1);
}
}
//走到这，map中存的就是每个数据，以及对应出现的次数
Set<Map.Entry<Integer,Integer>> entrySet = map.entrySet();
for (Map.Entry<Integer,Integer> entry:entrySet) {
System.out.println("key："+ entry.getKey()+" 出现了："+entry.getValue()+"次！");
}
}4、字符串中第一个只出现一次的字符 Map
public int first(String s){
HashMap<Character,Integer> map = new HashMap<>();
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
if(!map.containsKey(ch)){
map.put(ch,1);
}else{
int value = map.get(ch);
map.put(ch,value+1);
}
}
//走到这，map里放的就是字符和对应的个数
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
if(map.get(ch) == 1){
return i;
}
}
return -1;
}5、数组中只出现一次的数字，其余数字都出现两次 Set
public int singleNumber(int[] nums) {
HashSet<Integer> set = new HashSet<>();
for(int i=0; i<nums.length;i++){
if(!set.contains(nums[i])){
set.add(nums[i]);
}else{
set.remove(nums[i]);
}
}
//set中存的就是只出现一次的元素
for (Integer x : set) {
return x;
}
return -1;
}6、随机链表的复制 Map
public Node copyRandomList(Node head) {
//key是老节点，value是新节点
HashMap<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){
map.get(cur).next = map.get(cur.next);
map.get(cur).random = map.get(cur.random);
cur = cur.next;
}
return map.get(head);
}7、宝石与石头 Set
public int numJewelsInStones(String jewels, String stones) {
HashSet<Character> set = new HashSet<>();
int count = 0;
for (int i = 0; i < jewels.length(); i++) {
set.add(jewels.charAt(i));
}
for (int i = 0; i < stones.length(); i++) {
char ch = stones.charAt(i);
if(set.contains(ch)){
count++;
}
}
return count;
}8、坏键盘打字 Set
public static void func(String s1,String s2){
String str1 = s1.toUpperCase();
String str2 = s2.toUpperCase();
HashSet<Character> set = new HashSet<>();
for (int i = 0; i < str2.length(); i++) {
set.add(str2.charAt(i));
}
HashSet<Character> ret = new HashSet<>();
for (int i = 0; i < str1.length(); i++) {
char ch = str1.charAt(i);
//应该输出的，实际输出的里没有
if(!set.contains(ch) && !ret.contains(ch)){
ret.add(ch);
System.out.print(ch);
}
}
}9、前K个高频单词 Map
（1）概括题目：
返回给定单词中前k个出现次数最多的单词，返回的答案要按照次数由高到低排序，（其实就是比较次数的大小，大的放前面）若几个单词次数相同，按字典顺序排序（其实就是比较单词的大小，小的放前面）
一句话：要返回，前k个出现次数最多的单词，次数从大到小，次数相同时，单词从小到大。
（2）分析题目：
前k个出现次数最多的单词：
首先我们要统计单词出现的次数，然后建立大小为k的小根堆（因为找的是前k个出现次数最多的单词，所以建立小根堆）。让小根堆里最终放的就是前k个出现次数最多的单词，然后从堆中弹出元素。
如何让小根堆里最终放的就是前k个出现次数最多的单词呢？
已知堆中需要的是次数从大到小，次数相同时，单词从小到大的元素，为了满足堆的需要，
首先将前k个元素入堆，从k+1个元素开始，开始和堆顶元素进行比较，如果次数比堆顶元素大，就先出后入堆。如果次数和堆顶元素相同，看单词大小，单词比堆顶元素小，就先出后入堆。其他情况不入堆，什么都不做。那么，堆中存放的就是前k个出现次数最多的单词且次数相同时，存的是单词小的那个。
这里的比较，是判断此元素能不能放进堆，确定堆中的具体元素。
次数从大到小：
我们建立的是小根堆，每次弹出的都是最小值，次数是从小到大的，不满足题意，得进行翻转。
次数相同时，单词从小到大：
已知要进行翻转，翻转后要满足，次数从大到小，次数相同时，单词从小到大。那么，翻转之前的就是前k个出现次数最多的单词，次数从小到大，次数相同时，单词从大到小。
由于从堆中弹出的每次都是堆顶元素，为了使从堆里弹出的元素满足上述条件，在堆中就得按照上述条件放。每入堆或出堆一个元素，都要对堆进行调整，让堆中元素始终是上述条件存放的。上述条件就是堆的调整方式：从堆顶往下看，次数从小到大，次数相同时，单词从大到小存放。
这里的比较，是判断已经入堆或出堆后，每个元素应该呆在哪个位置。
两处比较，目的不同，一次是判断这个元素能不能放进堆，一次是判断这个元素放进堆后要处于堆中哪个位置。如：堆的大小是2，堆中的元素是 abc 1，要放的元素是 hello 1，能放吗？能。要调整吗？要。大单词要处于上方。调整后堆中的元素为 hello 1，abc 1。接着，要放的元素是 world 2，能放吗？能，要先出堆顶元素，再入堆。要调整吗？要。每入堆或出堆一个元素，都需要调整。最终调整后的堆中元素为 abc 1，world 2
（3）需要用到的集合：
统计单词出现的次数：
使用HashMap统计单词和出现的次数，其中每个元素的类型是Map.Entry<String,Integer>
建立大小为k的小根堆：
使用PriorityQueue，PriorityQueue中每个元素的类型是Map.Entry<String,Integer>。堆的调整方式的指定，就是PriorityQueue中比较器比较方式的指定（比较器中的参数o1接收的时是要调整的元素）
最终堆中存放的就是前k个出现次数最多的单词，怎么拿出来？
使用ArrayList，弹出每个元素，把单词放进ArrayList<String>，最终Arraylist<String>里存的就是前k个出现次数最多的单词。
对集合ArrayList进行翻转：
使用操作集合的工具类Collections（Collections.reverse();）
（4）代码：
public List<String> topKFrequent(String[] words, int k) {
//1、统计单词出现的次数
HashMap<String,Integer> map = new HashMap<>();
for (String word : words) {
if(!map.containsKey(word)){
map.put(word,1);
}else{
Integer value = map.get(word);
map.put(word,value+1);
}
}
//2、建立小根堆，小根堆里每个元素是一个Entry
PriorityQueue<Map.Entry<String,Integer>> minHeap = new PriorityQueue<>(k,
new Comparator<Map.Entry<String, Integer>>() {
@Override
public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
//次数小的靠进堆顶
//次数相等时，单词大的靠近堆顶
if(o1.getValue().equals(o2.getValue())){
return o2.getKey().compareTo(o1.getKey());
}
return o1.getValue().compareTo(o2.getValue());
}
});
for (Map.Entry<String,Integer> entry : map.entrySet()) {
if(minHeap.size() < k){
minHeap.offer(entry);
}else{
//和堆顶元素比，次数大的往里放，次数相等的，单词小的往里放
Map.Entry<String,Integer> top = minHeap.peek();
if(entry.getValue().compareTo(top.getValue()) > 0){
minHeap.poll();
minHeap.offer(entry);
}else{
if(entry.getValue().compareTo(top.getValue()) == 0){
if(entry.getKey().compareTo(top.getKey()) < 0){
minHeap.poll();
minHeap.offer(entry);
}
}
}
}
}
//3、把单词放进ArrayList
List<String> list = new ArrayList<>();
while(!minHeap.isEmpty()){
Map.Entry<String,Integer> entry = minHeap.poll();
list.add(entry.getKey());
}
//4、翻转ArrayList
Collections.reverse(list);
return list;
}