🌸个人主页:https://blog.csdn.net/2301_80050796?spm=1000.2115.3001.5343
🏵️热门专栏:🍕 Collection与数据结构 (91平均质量分)https://blog.csdn.net/2301_80050796/category_12621348.html?spm=1001.2014.3001.5482
🧀Java EE(94平均质量分) https://blog.csdn.net/2301_80050796/category_12643370.html?spm=1001.2014.3001.5482
🍭MySql数据库(93平均质量分)https://blog.csdn.net/2301_80050796/category_12629890.html?spm=1001.2014.3001.5482
感谢点赞与关注~~~
目录
- 1. 搜索树
- 1.1 概念
- 1.2 查找结点
- 1.3 插入结点
- 1.4 删除结点(难点)
- 1.5 实现二叉搜索树
- 1.6 性能分析
- 1.7 和Java中Collection的关系
- 2. Map和Set
- 2.1 概念与场景
- 2.2 两种模型
- 2.3 Map的使用
- 2.3.1 关于Map的说明
- 2.3.2 关于Map.Entry<K,V>的说明
- 2.3.3 常用方法
- 2.4 Set的使用
- 2.4.1 常用方法
1. 搜索树
1.1 概念
二叉搜索树又称为二叉排序树,它可以是一颗空树,或者是具有以下性质的二叉树.
- 若他的右树不为空,则它的右子树上的所有结点都大于根结点.
- 若它的左树不为空,则它的左子树上的所有结点都小于根结点.
- 它的左子树和右子树也分别为二叉搜索树.
1.2 查找结点
如果根节点为空,返回false.如果根结点不为空:
- 如果根结点key == 查找key,返回true.
- 如果根结点key < 查找key,到其右子树中查找.
- 如果根结点key > 查找key,到其左子树中查找.
1.3 插入结点
- 如果为空树,直接令root = 所要插入的结点.之后返回true.
- 如果该树不是空树,按照搜索二叉树的性质确定查找逻辑.插入新结点.注意记录cur的父节点,否则无法插入.
1.4 删除结点(难点)
设待删除的结点是cur,带删除的结点的父节点是parent.
- cur的左子树为空
- 要删除的节点是根结点,直接令root = root.right
- 要删除的结点是中间的结点, 单分支,parent.right = cur.right
- 要删除的结点是中间结点,<字型,parent.left = cur.right
- cur的右子树为空
- 要删除的结点是根结点,直接令root = root.left
- 要删除的结点是中间结点,单分支,parent.left = cur.left
- 要删除的结点是中间结点,>字型,parent.right = cur.left
- cur的左右子树都不为空
可以使用替换法进行删除,即它在右子树中寻找最小的结点,或者在左子树中寻找最大的结点,使用找到的结点替换要删除的结点,然后删除找到的最小(大)的结点,之后又分为两种情况(以右子树为例):- 最小的结点与上下的结点组成<型.
- 最小的结点与上下结点形成单分支.
[图解]
1.5 实现二叉搜索树
public class SearchBinaryTree {
//搜索树的结点
public static class Node{
public int key;
public Node left;
public Node right;
public Node(int key) {
this.key = key;
}
}
private Node root = null;
/**
* 查找元素
* @param key 索要查找的元素
* @return 返回Node的哈希值
*/
public Node search(int key){
Node cur = root;
while (cur != null){
if (cur.key == key){
return cur;
} else if (cur.key < key) {
cur = cur.right;
}else {
cur = cur.left;
}
}
return null;//没找到,返回null
}
/**
* 在二叉搜索树中插入指定的值
* @param key 所要插入的值
* @return 返回是否插入成功
*/
public boolean insert(int key){
Node node = new Node(key);
Node cur = root;
Node parent = null;
if (root == null){
root = node;
return true;
}
while (cur != null){
if (cur.key == key){
return false;//二叉搜索树中不允许有两个相同的值,遇到相等返回false
} else if (cur.key < key) {
parent = cur;
cur = cur.right;
}else {
parent = cur;
cur = cur.left;
}
}
//退出循环后,判断结点应该插入在左侧还是右侧
if (parent.key < key){
parent.right = node;
}else {
parent.left = node;
}
return true;
}
/**
* 删除指定值的结点
* @param key 所要删除的值
* @return 返回是否删除成功
*/
public boolean remove(int key){
Node cur = root;
Node parent = null;
if (root == null){
return false;
}
while (cur != null){
if (cur.key == key){
removeNode(parent,cur);
return true;
} else if (cur.key < key) {
parent = cur;
cur = cur.right;
}else {
parent = cur;
cur = cur.left;
}
}
return false;//没找到,返回false
}
/**
* 找到结点之后删除
* @param parent 父结点
* @param cur 当前要删除的结点
*/
private void removeNode(Node parent,Node cur){
if (cur.left == null){//cur的左结点为空
if (cur == root){//当前要删除的结点是根结点
root = root.right;
} else if (parent.right == cur) {//删除的是单分支的中间节点
parent.right = cur.right;
}else {//删除的是<字型的中间结点
parent.left = cur.right;
}
} else if (cur.right == null) {//cur的右结点为空
if (cur == root){//当前要删除的结点是根结点
root = root.left;
} else if (parent.left == cur) {//删除的是单分支的中间节点
parent.left = cur.left;
}else {//删除的是>字型的中间结点
parent.right = cur.left;
}
}else {//左右结点都不为空,使用替换删除法
//在这个结点的右子树中寻找最小的值,用它进行替换,原因:这样右结点的值一定比替换之后的值大
Node t = cur.right;
Node tparent = cur;
//寻找右子树的最小结点,一直向左子树遍历,因为只有左结点的值才比根结点小,
while (t.left != null){//当没有左结点的时候停止遍历
tparent = t;
t = t.left;
}
cur.key = t.key;
//删除替换掉的结点
if (tparent.left == t){//<字型
tparent.left = t.right;
}else {//单分支型
tparent.right = t.right;
}
}
}
}
1.6 性能分析
插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。
对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数，即结点越深，则比较次数越多。
但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树：
最优情况下，二叉搜索树为完全二叉树，其平均比较次数为：log2N
最差情况下，二叉搜索树退化为单支树，其平均比较次数为：N/2
1.7 和Java中Collection的关系
TreeMap 和 TreeSet 即 java 中利用搜索树实现的 Map 和 Set；实际上用的是红黑树，而红黑树是一棵近似平衡的二叉搜索树，即在二叉搜索树的基础之上 + 颜色以及红黑树性质验证，关于红黑树的内容后序再进行讲解。
2. Map和Set
2.1 概念与场景
Map和Set是一种专门用来就那些搜索的容器或者数据结构,其搜索的效率与它们具体的例子有关.
以前常见的搜索方式有：
1. 直接遍历，时间复杂度为O(N)，元素如果比较多效率会非常慢
2. 二分查找，时间复杂度为 ,但搜索前必须要求序列是有序的
上述排序比较适合静态类型的查找，即一般不会对区间进行插入和删除操作了，而现实中的查找比如：
1. 根据姓名查询考试成绩
2. 通讯录，即根据姓名查询联系方式
3. 不重复集合，即需要先搜索关键字是否已经在集合中
可能在查找时进行一些插入和删除的操作，即动态查找，那上述两种方式就不太适合了，本节介绍的Map和Set是一种适合动态查找的集合容器。
2.2 两种模型
一般把搜索的数据称为关键字(key),和关键字对应的值称为值(value),将其称为key-value键值对,所以会有两种模型.
- 纯key模型,容器中只存了key一个值.
- key-value模型,容器中存的是key-value的键值对.
Map中存储的是key-value键值对(有点类似于python中的字典),Set中只存储了key(有点类似于python中的集合).
2.3 Map的使用
2.3.1 关于Map的说明
Map是一个接口类，该类没有继承自Collection，该类中存储的是<K,V>结构的键值对，并且K一定是唯一的，不能重复.
2.3.2 关于Map.Entry<K,V>的说明
Map.Entry<K,V>是Map内部实现的内部类,用来表示Map中Key于Value的映射关系(类似于python字典中的items),该内部类中主要提供了key和value的获取方式,以及value的设置.
| 方法 | 解释 |
|---|---|
| K getKey() | 返回 entry 中的 key |
| V getValue() | 返回 entry 中的 value |
| V setValue(V value) | 将键值对中的value替换为指定value |
[注意]
在Map.Entry<K,V>类中没有提供key的设置方法,即该类中的key一旦确定就不可更改.
2.3.3 常用方法
| 方法 | 解释 |
|---|---|
| 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<K> keySet() | 返回所有 key 的不重复集合(Map中的key不可重复) |
Collection<V> values() | 返回所有 value 的可重复集合(Map中的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的底层结构是红黑树,增删查改的时间复杂度是log2N,HashMap的底层结构是哈希桶.时间复杂度是1,哈希桶直接可以根据索引找到位置,不需要遍历.
- TreeMap和HashMap的线程都不安全.
使用实例:
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;
public class Main {
public static void main(String[] args) {
Map<Integer,String> map = new TreeMap<>();
map.put(1,"一");//添加元素
map.put(2,"二");
map.put(3,"三");
map.put(4,"四");
map.put(5,"五");
System.out.println(map.size());//打印map大小
System.out.println(map.get(5));//获取5对应的value
System.out.println(map.getOrDefault(6,"不存在"));//6不存在,返回默认值
map.remove(5);//删除5对应的键值对
Set<Integer>set = map.keySet();//拿到map的key集合
for(int x:set){
System.out.print(x+" ");
}
for (String x:map.values()){
System.out.println(x+" ");
}
Set<Map.Entry<Integer,String>> set1 = map.entrySet();
for (Map.Entry<Integer,String> x:set1){//把一个不可迭代的对象转换为可迭代对象,经常用
System.out.println("key:"+x.getKey()+" "+"value:"+x.getValue());
}
System.out.println(map.containsKey(1));
System.out.println(map.containsKey(6));
System.out.println(map.containsValue("一"));
System.out.println(map.containsValue("六"));
}
}
运行结果:
2.4 Set的使用
Set和Map最主要的区别有两点:
- Set继承于Collection接口,而Map没有,所以Set可以遍历,Map不可以遍历.
- Set中只存储key,而Map中存的是key-value的键值对.
2.4.1 常用方法
| 方法 | 解释 |
|---|---|
| boolean add(E e) | 添加元素，但重复元素不会被添加成功 |
| void clear() | 清空集合 |
| boolean contains(Object o) | 判断 o 是否在集合中 |
Iterator<E> 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不能修改(这里与python不同.python中的集合是可变的)，如果要修改，先将原来的删除掉，然后再重新插入
- TreeSet中不能插入null的key，HashSet可以.
