一.搜索树
1.概念
二叉搜索树又叫二叉排序树，它可以是一颗空树也可以是具有以下性质的二叉树
- 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
- 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
- 它的左子树也分别为二叉搜索树
2.查找
3.插入
1.如果树为空树，直接插入
2.如果树不是空树，按照查找逻辑确定插入位置，插入新节点
插入元素为10的新节点
4.删除
（难点，若要删除节点的左右都有孩子，删除的地方放哪个？）
设待删除的节点为cur，待删除节点的双亲节点为parent
先找到要删除的节点
一.cur.left == null
1.cur是root，则root = cur.right
2.cur不是root，cur是parent.left，则parent.left = cur.right
3.cur不是root，cur是parent.right，则parent.right = cur.right
二.cur.right == null
1.cur是root，则root = cur.left
2.cur不是root，cur是parent.left，则parent.left = cur.left
3.cur不是root，cur是parent.right，则parent.right = cur.left
三.cur.left != null && cur.right != null
1.需要用替换法来删除，就是在它的右子树下寻找中序下的第一个节点（关键码最小），用它的值填补到被删除的节点中，再来处理该节点的问题
（左树最右边的活着右树最左边的元素就可以做替换）
二.搜索
1.概念和场景
Map和Set一般用来动态查找，比如通讯录可能在查找时进行一些插入和删除的操作，此时我们之前学的直接遍历和二分查找等就不好用了
2.模型
一班把搜索的数据成为关键字（key），和关键字对应的成为值（value）
1.纯key模型（TreeSet,HashSet)
快速查找一个东西在不在列表中
2.key-value模型（TreeMap,HashMap)
统计每个东西出现的次数或者每个东西对应的绰号
三.Map
3.1概念
Map是用于保存具有映射关系的数据集合，它具有双列存储的特点，即一次必须添加两个元素，即一组键值对==><Key,Value>，其中Key的值不可重复（当Key的值重复的时候，后面插入的对象会将之前插入的具有相同的Key值的对象覆盖掉），Value的值可重复。Map作为接口，它最常见的实现类是HashMap和TreeMap，作为接口它抽取了所有实现类的共有方法。同时Map不具有带索引的方法，因此无法使用普通for循环来遍历Map集合
注意：
- map是一个接口，不能直接实例化对象，只能实例化其实现类TreeMap和HashMap
- Map中存放键值对的key是唯一的，value是可以重复的
- TreeMap中key不能为空，value可以为空，而HashMap都可以
- Map中的key可以全部分离出来，存储到Set中来进行访问（因为key不能重复）
- Map中value可以全部分离出来，存储到Collection的任何一个子集中（value可能重复）
- value可以直接修改而key不能，要修改key只能先删除key，再重新插入
3.2Map常用方法(具体实现）
具体实现类为HashMap的Map（TreeMap同理）
3.2.1 put和remove
public class Main {public static void main(String[] args) {//Map为双列存储（一次必须同时存储两个元素）,<key,value>key是键，value是值，// 键不可以重复，值可以重复Map<Integer,String> map = new HashMap<>();//用put方法增添数据map.put(1,"one");map.put(2,"two");map.put(3,"tree");//用remove方法删除数据map.remove(1);}
}运行结果
3.2.2调用keySet方法获取所有键的集合(用到set）
public static void main(String[] args) {Map<Integer,String> map = new HashMap<>();//用put方法增添数据map.put(1,"one");map.put(2,"two");map.put(3,"tree");//System.out.println(map);Set<Integer> integers = map.keySet();for (Integer integer : integers){System.out.println(integer);}}运行结果
