系列文章目录
集合及数据结构第十二节（上）———— 二叉搜索树和Map、Set详解
二叉搜索树和Map、Set详解
- 搜索树的概念
- 二叉搜索树的实现
- 性能分析
- 和 java 类集的关系
- 搜索的概念及场景
- 模型
- 关于Map的说明
- 关于Map.Entry<K, V>的说明
- Map 的常用方法说明
- TreeMap的使用案例
- Set的常见方法说明
- TreeSet的使用案例
文章目录
一、搜索树
1.搜索树的概念
二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:
- 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
- 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
- 它的左右子树也分别为二叉搜索树
int[] array ={5,3,4,1,7,8,2,6,0,9};
2.二叉搜索树的实现（ * * * ）
查找操作
代码实现：
//最好情况：查找的是一颗完全二叉树，时间复杂度是O（log2 N）
//最坏情况：查找的是一颗单分支的树时间复杂度是O（N）
public boolean search(int key){// 查找操作
TreeNode cur = root;
while (cur != null){//当节点不为空时
if (cur.val < key){//当cur的val 小于key时，去右边找
cur = cur.right;
} else if (cur.val > key) {//当cur的val大于key时，去左边找
cur = cur.left;
}
else {//cur的val等于key时，直接返回true
return true;
}
}
return false;//循环结束，说明没有要找的key。返回false
}
插入操作
- 如果树为空树，即根 == null，直接插入
- 如果树不是空树，按照查找逻辑确定插入位置，插入新结点
代码实现
public boolean insert(int val){//插入操作
if (root == null){//当当前树为空时，直接插入val并返回true
root = new TreeNode(val);
return true;
}
TreeNode cur = root;
TreeNode parent = null;//用来存放当前节点的父亲节点
TreeNode node = new TreeNode(val);//要插入的数据
while (cur != null){//当cur不为null
if (cur.val < val){//如果当前cur的val值小于要查找的值val
parent = cur;//存放当前节点
cur = cur.right;//看当前cur的右子树是否满足条件
}else if (cur.val > val) {//如果当前cur的val值大于要查找的值val
parent = cur;//存放当前节点
cur = cur.left;//看当前cur的左子树是否满足条件
}else {//如果当前cur的val值等于要查找的值val
return false;//在二叉搜索树中，不能有两个一样的数据，直接返回false
}
}
//循环结束，再判断要插入的位置是左边还是右边
if (parent.val > val){//如果cur的父节点的val大于要查找的值val
parent.left = node; //插入到左边
}else {//如果cur的父节点的val小于要查找的值val
parent.right = node; //插入到右边
}
return true;//返回true说明插入成功
}
删除操作
设待删除结点为 cur, 待删除结点的双亲结点为 parent
- cur.left == null
- cur 是 root，则 root = cur.right
- cur 不是 root，cur 是 parent.left，则 parent.left = cur.right
- cur 不是 root，cur 是 parent.right，则 parent.right = cur.right
- cur.right == null
- cur 是 root，则 root = cur.left
- cur 不是 root，cur 是 parent.left，则 parent.left = cur.left
- .cur 不是 root，cur 是 parent.right，则 parent.right = cur.left
- cur.left != null && cur.right != null
- 需要使用替换法进行删除，即在它的右子树中寻找中序下的第一个结点(关键码最小)，用它的值填补到被 删除节点中，再来处理该结点的删除问题
public void remove(int key) {// 删除操作
TreeNode cur = root;
TreeNode parent = null;//用来存放当前节点的父亲节点
while (cur != null) {//当节点不为空时
if (cur.val < key) {//当cur的val 小于key时，去右边找
parent = cur;//记录当前节点
cur = cur.right;
} else if (cur.val > key) {//当cur的val大于key时，去左边找
parent = cur;//记录当前节点
cur = cur.left;
} else {//cur的val等于key时，开始删除
removeNode(cur, parent);
}
}
}
private void removeNode(TreeNode cur, TreeNode parent) {//删除key（cur）节点
if (cur.left == null) {//如果cur的左子树为空
if (cur == root) {//如果这时的要删除的节点cur是根节点
root = cur.right;//直接让root变成cur的右子树
} else if (cur == parent.left) {//如果这时的要删除的节点cur是parent的左子树
parent.left = cur.right;//让parent的左子树变成cur的右子树
} else {//如果这时的要删除的节点cur是parent的右子树
parent.right = cur.right;
;//让parent的右子树变成cur的右子树
}
} else if (cur.right == null) {//如果cur的右子树为空
if (cur == root) {//如果这时的要删除的节点cur是根节点
root = cur.left;//直接让root变成cur的左子树
} else if (cur == parent.left) {//如果这时的要删除的节点cur是parent的左子树
parent.left = cur.left;//让parent的左子树变成cur的左子树
} else {//如果这时的要删除的节点cur是parent的右子树
parent.right = cur.left;
;//让parent的右子树变成cur的左子树
}
} else {//左右都不为空
TreeNode targetParent = cur;//用来找用来替换的值
TreeNode target = cur.right;//用来找用来替换的值
while (target.left != null) {//当target的左子树不为空时
targetParent = target;//此时的targetParent节点变成target节点
target = target.left;//target节点变成target的左子树
}
//循环结束，说明找到了用来替换要删除节点的节点
cur.val = target.val;//将要删除节点的值替换成找到的节点的值
//删除target
if (targetParent.left == target) {//targetParent的左边等于target
targetParent.left = target.right;
} else {//targetParent的右边等于target
targetParent.right = target.right;
}
}
}
3.性能分析（ * * ）
插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。
对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数，即结点越深，则比较次数越多。
但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树：
4.和 java 类集的关系
TreeMap 和 TreeSet 即 java 中利用搜索树实现的 Map 和 Set；实际上用的是红黑树，而红黑树是一棵近似平衡的二叉搜索树，即在二叉搜索树的基础之上 + 颜色以及红黑树性质验证。
二、搜索
1.搜索的概念及场景
Map和set是一种专门用来进行搜索的容器或者数据结构，其搜索的效率与其具体的实例化子类有关。以前常见的
搜索方式有：
- 直接遍历，时间复杂度为O(N)，元素如果比较多效率会非常慢
- 二分查找，时间复杂度为 ,但搜索前必须要求序列是有序的
上述排序比较适合静态类型的查找，即一般不会对区间进行插入和删除操作了，而现实中的查找比如： - 根据姓名查询考试成绩
- 通讯录，即根据姓名查询联系方式
- 不重复集合，即需要先搜索关键字是否已经在集合中
可能在查找时进行一些插入和删除的操作，即动态查找，那上述两种方式就不太适合了，本节介绍的Map和Set是一种适合动态查找的集合容器。
2.模型
一般把搜索的数据称为关键字（Key），和关键字对应的称为值（Value），将其称之为Key-value的键值对，所以模型会有两种：
- 纯 key 模型，比如：
- 有一个英文词典，快速查找一个单词是否在词典中
- 快速查找某个名字在不在通讯录中
- Key-Value 模型，比如：
- 统计文件中每个单词出现的次数，统计结果是每个单词都有与其对应的次数：<单词，单词出现的次数>
- 梁山好汉的江湖绰号：每个好汉都有自己的江湖绰号
而Map中存储的就是key-value的键值对，Set中只存储了Key。
三、Map 的使用
1. 关于Map的说明
Map是一个接口类，该类没有继承自Collection，该类中存储的是<K,V>结构的键值对，并且K一定是唯一的，不能重复。
2. 关于Map.Entry<K, V>的说明
Map.Entry<K, V> 是Map内部实现的用来存放<key, value>键值对映射关系的内部类，该内部类中主要提供了<key, value>的获取，value的设置以及Key的比较方式
| 方法 | 解释 |
|---|---|
| K getKey() | 返回 entry 中的 key |
| V getValue() | 返回 entry 中的 value |
| V setValue(V value) | 将键值对中的value替换为指定value |
注意：Map.Entry<K,V>并没有提供设置Key的方法
3.Map 的常用方法说明（ * * ）
| 方法 | 解释 |
|---|---|
| V get(Object key) | 返回 key 对应的 value |
| V getOrDefault(Object key, V defaultValue) | 返回 key 对应的 value，key 不存在，返回默认值 |
| V put(K key, V value) | 设置 key 对应的 value |
| V remove(Object key) | 删除 key 对应的映射关系 |
| Set keySet() | 返回所有 key 的不重复集合 |
| Collection values() | 返回所有 value 的可重复集合 |
| Set<Map.Entry<K, V>> entrySet() | 返回所有的 key-value 映射关系 |
| boolean containsKey(Object key) | 判断是否包含 key |
| boolean containsValue(Object value) | 判断是否包含 value |
注意
- Map是一个接口，不能直接实例化对象，如果要实例化对象只能实例化其实现类TreeMap或者HashMap
- Map中存放键值对的Key是唯一的，value是可以重复的
- 在TreeMap中插入键值对时，key不能为空，否则就会抛NullPointerException异常，value可以为空。但
是HashMap的key和value都可以为空。 - Map中的Key可以全部分离出来，存储到Set中来进行访问(因为Key不能重复)。
- Map中的value可以全部分离出来，存储在Collection的任何一个子集合中(value可能有重复)。
- Map中键值对的Key不能直接修改，value可以修改，如果要修改key，只能先将该key删除掉，然后再来进行重新插入。
- TreeMap和HashMap的区别
4.TreeMap的使用案例
import java.util.Collection;
import java.util.Set;
import java.util.TreeMap;
import java.util.Map;
public class Test {
public static void main(String[] args) {
Map<String,Integer> map = new TreeMap<>();//查找的时间复杂度是O（Log2 N）
//往TreeMap里放元素
map.put("晴天",3) ;//晴天出现3次
map.put("雨天",1) ;//雨天出现1次
map.put("阴天",6) ;//阴天出现6次
//通过key获取val值
Integer val = map.get("阴天");
System.out.println(val);//6
Integer val1 = map.get("白天");
System.out.println(val1);//null
//没有key时默认为defaultVale
Integer val2 = map.getOrDefault("白天",9);
System.out.println(val2);//9
//根据key来删除
for(String s : map.keySet()){//删除前
System.out.print(s + " ");
}
System.out.println();
map.remove("雨天");
for(String s : map.keySet()){删除后
System.out.print(s + " ");
}
System.out.println();
//把所有的key放到一个集合
Set<String> set = map.keySet();
System.out.println(set);
//把所有的val放到一个集合
Collection<Integer> ret = map.values();
System.out.println(ret);
//判断是否包含 key
System.out.println(map.containsKey("晴天"));
//判断是否包含 value
System.out.println(map.containsValue(3));
//返回所有的 key-value 映射关系
Set<Map.Entry<String,Integer>> entrySet = map.entrySet();
for (Map.Entry<String,Integer> entry: entrySet) {
System.out.println("key:" + entry.getKey() + "value" + entry.getValue());
}
}
四、Set 的说明
Set 的官方文档
Set与Map主要的不同有两点：Set是继承自Collection的接口类，Set中只存储了Key。
1.Set的常见方法说明
| 方法 | 解释 |
|---|---|
| boolean add(E e) | 添加元素，但重复元素不会被添加成功 |
| void clear() | 清空集合 |
| boolean contains(Object o) | 判断 o 是否在集合中 |
| Iterator iterator() | 返回迭代器 |
| boolean remove(Object o) | 删除集合中的 o |
| int size() | 返回set中元素的个数 |
| boolean isEmpty() | 检测set是否为空，空返回true，否则返回false |
| Object[] toArray() | 将set中的元素转换为数组返回 |
| boolean containsAll(Collection<?> c) | 集合c中的元素是否在set中全部存在，是返回true，否则返回false |
| boolean addAll(Collection<? extends E> c) | 将集合c中的元素添加到set中，可以达到去重的效果 |
注意：
- Set是继承自Collection的一个接口类。
- Set中只存储了key，并且要求key一定要唯一。
- TreeSet的底层是使用Map来实现的，其使用key与Object的一个默认对象作为键值对插入到Map中的。
- Set最大的功能就是对集合中的元素进行去重。
- 实现Set接口的常用类有TreeSet和HashSet，还有一个LinkedHashSet，LinkedHashSet是在HashSet的基础上维护了一个双向链表来记录元素的插入次序。
- Set中的Key不能修改，如果要修改，先将原来的删除掉，然后再重新插入
- TreeSet中不能插入null的key，HashSet可以。
- TreeSet和HashSet的区别：
2.TreeSet的使用案例
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
public class Test {
public static void main(String[] args) {
Set<String> set = new HashSet<>();
//添加元素，但重复元素不会被添加成功
set.add("晴天");
set.add("雨天");
set.add("阴天");
System.out.println(set);//是无序的\
//判断 o 是否在集合中
System.out.println(set.contains("雨天"));
//返回迭代器
Iterator<String> ret = set.iterator();
while (ret.hasNext()){
System.out.println(ret.next());
}
//删除集合中的 O
set.remove("雨天");
System.out.println(set);
//返回set中元素的个数
System.out.println(set.size());
//检测set是否为空，空返回true，否则返回false
System.out.println(set.isEmpty());
//集合c中的元素是否在set中全部存在，是返回true，否则返回false
Set<String> set1 = new HashSet<>();
set1.add("白天");
set1.add("夜晚");
set1.add("阴天");
System.out.println(set.containsAll(set1));
//清空集合
set.clear();
set.add("空");
System.out.println(set);
}
}
