一，二叉搜索树
搜索树的特点：
若它的左子树不为空，则左子树上所有节点的值都小于根节点的值 。若它的右子树不为空，则右子树上所有节点的值都大于根节点的值 。它的左右子树也分别为二叉搜索树
实现一棵搜索树（链式储存）：
class BinarySearchTree{
public TreeNode root;
static class TreeNode{
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int val){
this.val=val;
}
}
}
1，搜索：
我们先将根赋值给cur。将目标k与cur进行比较，如果k等于cur的值，那么找到了，返回节点。如果k大于cur，那么要找的只可能在cur的右边，所以cur=cur.right。反之，如果k小于cur，那么要找的只可能在cur的左边，所以cur=cur.left。再次重复上述判断，直到cur等于空，循环结束。二叉树搜索树中没有目标值。
public TreeNode search(int k){
TreeNode cur=root;
while (cur!=null){
if (cur.val<k){
cur=cur.right;
} else if (cur.val>k) {
cur=cur.left;
}else {
return cur;
}
}
return null;
}
2，插入：
先找到要放的位置。我们先将根赋值给cur。将parent定义为null。将val与cur的值进行比较，如果val等于cur的值，已经有重复的节点了，所以这次不做存储，直接return。先用parent将cur记录一下，然后如果val大于cur，那么要放在cur的右边，所以cur=cur.right。反之，先用parent将cur记录一下，如果val小于cur，那么要放在cur的左边，所以cur=cur.left。再次重复上述判断，直到cur等于空，循环结束。找到的目标要存放的位置为parent的左边或者右边，这时要将val与parent值进行比较，如果val大于parent，则把节点放到parent右边，反之，放到左边。
public void insert(int val){
TreeNode node=new TreeNode(val);
if (root==null){
root=node;
return;
}
TreeNode cur=root;
TreeNode parent=null;
while (cur!=null){
parent=cur;
if (cur.val>val){
cur=cur.left;
}else if (cur.val<val){
cur=cur.right;
}else {
return;
}
}
if (val> parent.val){
parent.right=node;
}else {
parent.left=node;
}
}
3，删除：
要先找到要删除的目标，思路与查找相似，唯一不同的是需要记录cur的父亲节点。找到之后我们判断cur的左边是否为空，如果为空可分为三种情况，
（1）cur就是根结点：所以删除根结点，root=cur.right;
（2）cur在parent的左边：所以parent.left=cur.right;
（3）cur在parent的右边：所以parent.right=cur.right;
再判断cur的右边有否为空，同样分为三种情况，
（1）cur就是根结点：所以删除根结点，root=cur.right;
（2）cur在parent的左边：所以parent.left=cur.left;
（3）cur在parent的右边：所以parent.right=cur.left;
其余情况：
需要我们再设置两个变量，分别为target=cur.right，targetP=cur。我们需要在cur为根的子树中找到可以代替cur的节点，即只比cur大一点的节点，或者只比cur小一点的节点，也就是cur的右树的最左树。或者是左树的最右树。我们这里以比cur大一点的节点举例。
我们找到cur大一点的节点为target（不再进行赘述），将target的值赋给cur。然后判断target是否为targetp的左树，如果是：targetP.left=target.right;如果target为targetp的右树（则说明一开始targe的左边就为null），那么：targetP.right=target.right。
-------------------------------------------------------
private void removeNode(TreeNode parent,TreeNode cur){
if (cur.left==null){
if (cur==root){
root=cur.right;
} else if (cur==parent.left) {
parent.left=cur.right;
}else {
parent.right=cur.right;
}
} else if (cur.right==null) {
if (cur==root){
root=cur.left;
} else if (cur==parent.left) {
parent.left=cur.left;
}else {
parent.right=cur.left;
}
}else {
TreeNode target=cur.right;
TreeNode targetP=cur;
while (target.left!=null){
targetP=target;
target=target.left;
}
cur.val=target.val;
if (target==targetP.left){
targetP.left=target.right;
}else {
targetP.right=target.right;
}
}
}
二，map和set
Map和set是一种专门用来进行搜索的容器或者数据结构，其搜索的效率与其具体的实例化子类有关。
1，模型：
（1） 纯 key 模型 ，比如：快速查找一个单词是否在词典中
（2）Key-Value 模型 ，比如：统计文件中每个单词出现的次数
2，map
Map是一个接口类，该类没有继承自Collection，该类中存储的是结构的键值对，并且K一定是唯一的，不能重复。
3，map的常见方法：
（1）V get(Object key) -》返回 key 对应的 value。如果key重复了，就会更新val值
（2）V getOrDefault(Object key, V defaultValue) -》返回 key 对应的 value，key 不存在，返回默认值
（3）V put(K key, V value) -》设置 key 对应的 value
（4）V remove(Object key) -》删除 key 对应的映射关系
（5）Set keySet() -》返回所有 key 的不重复集合
（6）Collection values() -》返回所有 value 的可重复集合
（7）Set<Map.Entry <K, V>> entrySet() -》返回所有的 key-value 映射关系
（8）boolean containsKey(Object key) -》判断是否包含
（9）key boolean containsValue(Object value) -》判断是否包含 value
Map<String ,String> map=new TreeMap<>();
map.put("及时雨","松江");
map.put("及时雨","松江2");//如果k重复了，就会更新val值
map.put("齐天大圣","孙悟空");
String val=map.get("齐天大圣");
System.out.println(val);
String val2=map.getOrDefault("齐天大圣2","hehe");
System.out.println(val2);//如果k不存在，则返回默认值
// System.out.println(map.remove("齐天大圣"));
Set<String> set=map.keySet();//把所有k放到set里面
System.out.println(set);
Set<Map.Entry<String,String>> entries=map.entrySet();
System.out.println(entries);
for (Map.Entry<String,String> enter:entries){
//System.out.print(enter+" ");
System.out.println("k:"+enter.getKey()+" val"+enter.getValue());
}
注意：
（1） Map是一个接口，不能直接实例化对象，如果要实例化对象只能实例化其实现类TreeMap或者HashMap
（2）Map中存放键值对的Key是唯一的，value是可以重复的
（3）在TreeMap中插入键值对时，key不能为空
（4）Map中键值对的Key不能直接修改，value可以修改，如果要修改key，只能先将该key删除掉，然后再来进行重新插入
（5）往treemap中存储元素的时候，可以一定是可比较的
（6）TreeMap和HashMap的区别
4，set
Set与Map主要的不同有两点：Set是继承自Collection的接口类，Set中只存储了Key。
5,set的主要方法：
（1）boolean add(E e) 添加元素，但重复元素不会被添加成功
（2）void clear() 清空集合
（3）boolean contains(Object o) 判断 o 是否在集合中
（4）boolean remove(Object o) 删除集合中的 o
（5）int size() 返回set中元素的个数
（6）boolean isEmpty() 检测set是否为空，空返回true，否则返回false
（7）Object[] toArray() 将set中的元素转换为数组返回
（8）boolean containsAll(Collection<?> c) 集合c中的元素是否在set中全部存在，是返回true，否则返回false
（9）boolean addAll(Collection<?extends E> c) 将集合c中的元素添加到set中，可以达到去重的效果
（10）Iterator<E> iterator() 返回迭代器
Set<String> set=new TreeSet<>();
set.add("abc");
set.add("hell0");
set.add("abc");//set中不能存储重复的元素
System.out.println(set);
Iterator<String> it=set .iterator();
while (it.hasNext()){
System.out.println(it.next());
}
注意：
（1）Set是继承自Collection的一个接口类
（2）Set中只存储了key，并且要求key一定要唯一
（3）TreeSet的底层是使用Map来实现的，其使用key与Object的一个默认对象作为键值对插入到Map中的
（4）Set最大的功能就是对集合中的元素进行去重
（5）TreeSet中不能插入null的key，HashSet可以
（6）Set中的Key不能修改，如果要修改，先将原来的删除掉，然后再重新插入
（7）. TreeSet和HashSet的区别
6，哈希表
一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快 找到该元素。
该方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表
1，哈希冲突：不同关键字通过相同哈 希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。
冲突的发生是必然的，但我们能做的应该是尽量的降低冲突率
2，冲突避免方式
（1）哈希函数设计（尽量均匀分布）
（2）负载因子调节（官方：loadFactor=0.75）
解决哈希冲突两种常见的方法是：闭散列和开散列
闭散列：
也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以 把key存放到冲突位置中的“下一个” 空位置中去。
1. 线性探测：
比如上面的场景，现在需要插入元素，先通过哈希函数计算哈希地址，但是该位置已经放了其他元素，即发生哈希冲突。 线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止
2. 二次探测：
线性探测的缺陷是产生冲突的数据堆积在一块，这与其找下一个空位置有关系，因为找空位置的方式就是挨着往后逐个去找，因此二次探测为了避免该问题，找下一个空位置的方法为：Hi = (Ho + i^2)% m,其中：i = 1,2,3…
研究表明：当表的长度为质数且表装载因子a不超过0.5时，新的表项一定能够插入，而且任何一个位置都不会被探查两次。因此只要表中有一半的空位置，就不会存在表满的问题。在搜索时可以不考虑表装满的情况，但在插入时必须确保表的装载因子a不超过0.5，如果超出必须考虑增容。 因此：比散列最大的缺陷就是空间利用率比较低，这也是哈希的缺陷。
开散列/哈希桶:
开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。
