JavaSE 进阶 (6) 集合
泛型-概述
如果在创建集合的时候,不写泛型会怎么样?
 集合/1.png)
图1) 集合/2.png)
图2) 集合/3.png)
图3)泛型概述
泛型:是 JDK5 中引入的特性,它提供了编译时类型安全检测机制
泛型的好处:
- 把运行时期的问题提前到了编译期间
- 避免了强制类型转换
Set-概述
集合类体系结构
 集合/4.png)
图4)Set-基本使用
Set集合概述和特点
Set 集合的特点
- 可以去除重复
- 存取顺序 不一致
- 没有带索引的方法,所以不能使用普通
for循环遍历,也不能通过索引来获取/删除set集合里的元素
Set集合练习
存储字符串并遍历 (所有单列集合都可以使用迭代器进行遍历,所以 set 集合也可以使用)
|
|
存储和取出的顺序不一致
|
|
TreeSet-基本使用
TreeSet集合概述和特点
TreeSet:底层是红黑树结构,所以要求元素必须排序
TreeSet 集合特点
- 不包含重复元素的集合
- 没有带索引的方法
- 可以将元素按照规则进行排序 (
TreeSet虽然 不能保证存和取的顺序,但是可以 对内部的元素进行排序)
TreeSet 集合练习
- 存储
Integer类型的整数,并遍历 - 存储学生对象,并遍历
|
|
|
|
想要使用 TreeSet,需要制定排序规则
TreeSet-自然排序
自然排序Comparable的使用
- 使用 空参构造 创建
TreeSet集合 - 自定义的
Student类实现 Comparable 接口 - 重写里面的 compareTo 方法
public interface Comparable<T>
该接口对实现它的每个类的对象强加一个整体排序。这个排序被称为类的自然排序,类的 compareTo 方法被称为其自然比较方法。
简单来说,一个类实现了 Comparable 接口,那么就可以根据里面 compareTo 方法的返回值,对元素进行排序
|
|
自然排序简单原理图(找中间的比较)
- 如果返回值为负数,表示当前存入的元素是较小值,存左边
- 如果返回值为 0,表示当前存入的元素跟集合中元素重复了,不存
- 如果返回值为正数,表示当前存入的元素是较大值,存右边
 集合/5.png)
图5)将创建的三个对象存入到我们创建的容器 TreeSet 集合中
第一个是 小花,28,容器中没有内容,他直接就存进去了,第二个要存的是 小花花,27
 集合/6.png)
图6)This:表示现在正在存的对象,也就是 小花花,27
O:表示已经存到集合中的元素,也就是 小花,28
第三个是 小小花,29,将正在存的元素与集合中的元素一个一个进行比较
 集合/7.png)
图7) 集合/8.png)
图8) 集合/9.png)
图9)自然排序-练习
案例:按照年龄排序
需求:改写刚刚的学生案例
要求:按照年龄从小到大排,如果年龄一样,则按照姓名首字母排序
如果年龄和姓名都一样,认为是同一个学生对象,不存入
为什么要先按年龄,再按姓名排序呢?
|
|
我们发现 小黑,28 没有存到集合中,这是因为排序规则是按照年龄排序的,小黑的年龄 28 集合中已经有了,于是在添加的时候,就会认为 小花,28 和 小黑,28 是同一个对象,所以 TreeSet 就把第四个对象扔了
|
|
姓名是中文的,中文无法按照首字母排序,需要将姓名换成英文的
this.name 是一个字符串,this.name.compareTo() 用的是字符串 String 里的 compareTo 方法
| int compareTo(String anotherString) | 按字典顺序比较两个字符串 |
|---|
对字符串中的 compareTo 方法进行演示
|
|
TreeSet-比较器排序
比较器排序Comparator的使用
TreeSet的 带参 构造方法使用的是 比较器排序 对元素进行排序的 (如果要使用比较器排序,在创建TreeSet的时候,就不能使用空参,空参是自然排序)- 比较器排序,就是 让集合构造方法接收Comparator的实现类对象,重写
compare(To1,To2)方法 - 重写方法时,一定要注意排序规则必须按照要求的主要条件和次要条件来写
练习
需求:用比较器排序实现下面的需求
要求:自定义 Teacher 老师类,属性为姓名和年龄
请按照年龄排序,如果年龄一样,则按照姓名进行排序,姓名都使用英文字母表示
构造方法
| Constructor | 描述 |
|---|---|
| TreeSet() | 构造一个新的、空的树组,根据其元素的自然排序进行排序。 |
| TreeSet(Collection<? extends E> c) | 构造一个包含指定集合中的元素的新树集,根据其元素的自然排序进行排序。 |
| TreeSet(Comparator<? super E> comparator) | 构造一个新的、空的树集,根据指定的比较器进行排序。 |
| TreeSet(Sortedset |
构造一个包含相同元素的新树,并使用与指定排序集相同的顺序。 |
|
|
o1 代表当前要存入的元素,o2 代表集合中的元素,比较的时候先找集合中处于中间位置的元素比较,如果比中间的位置元素小,就继续与左边的元素比较,反之则与右边的元素比较
TreeSet两种比较方式的对比
自然排序
- 定义:自定义类实现 Comparable 接口,重写 compareTo 方法,根据返回值进行排序
- 使用场景:默认使用自然排序,当自然排序不满足现在的需求时,使用比较器排序(例如:String,Integer…等,Java 已经实现了comparable 的接口,自然排序规则 Java 已经帮你写好了,不需要你去管了,如果不满意,肯定不能更改 Java 源码,所以此时用第二种方式)
比较器排序
- 定义:创建 TreeSet 对象时传递 Comparator 实现类对象,重写 compare 方法,根据返回值进行排序
- 使用场景:当自然排序不满足需求时使用(如需要自定义排序规则,但不能修改 Java 源码)
执行规则:当自然排序与比较器排序同时存在时,按照比较器排序的规则执行
返回值规则
- 如果返回值为 负数,表示当前存入的元素是较小值,存左边
- 如果返回值为 0,表示当前存入的元素跟集合中元素重复了,不存
- 如果返回值为 正数,表示当前存入的元素是较大值,存右边
案例:按照字符串长短排序
需求:请自行选择比较器排序和自然排序两种方式
要求:存入四个字符串,‘c’、‘ab’、‘df’、‘qwer’,按照长度排序,如果一样长则按照首字母排序
|
|
数据结构-二叉树
数据结构-树
Tree Set: 树结构,是 Set 体系中的一员
Array List: 数组结构,是 List 体系中的一员
Linked List: 链表结构,是 List 体系中的一员
Tree Set: 树结构,是 Set 体系中的一员
mindmap
root((Tree Set))
二叉树
二叉查找树
平衡二叉树
红黑树
mindmap
root((Tree Set))
二叉树
二叉查找树
平衡二叉树
红黑树
mindmap
root((Tree Set))
二叉树
二叉查找树
平衡二叉树
红黑树mindmap
root((Tree Set))
二叉树
二叉查找树
平衡二叉树
红黑树
数据结构-二叉树
B 节点是 A 节点的左子节点,C 节点是 A 节点的右子节点
如果某个节点没有父节点,例如 A 节点,或者某个节点没有子节点,例如 B 节点和 C 节点,那么对应的节点地址就会记为 null
 集合/10.png)
图10) 集合/11.png)
图11) 集合/12.png)
图12) 集合/13.png)
图13)数据结构-二叉查找树
 集合/14.png)
图14)二叉查找树
二叉查找树,又称二叉排序树或者二叉搜索树。
特点:
- 每一个节点上最多有两个子节点
- 每一个节点的左子结点都是小于自己的
- 每一个节点的右子结点都是大于自己的
 集合/15.png)
图15) 集合/16.png)
图16)数据结构-二叉查找树添加节点
二叉树查找树添节点
 集合/17.png)
图17)将上面的节点按照二叉查找树的规则存入,规则: 小的存左边、大的存右边、一样的不存
 集合/18.png)
图18) 集合/19.png)
图19)将上面的节点按照二叉查找树的规则存入
 集合/20.png)
图20)数据结构-平衡二叉树
二叉树查找树添节点
 集合/21.png)
图21)将上面的节点按照二叉查找树的规则存入
 集合/22.png)
图22)根节点的左子树和根节点的右子树差的太多了,这样的话,查询效率太低了,因为二叉查找树的查找是从根节点的开始,假如找13,要找好几次
问:怎么才能让二叉树变得合理呢?
答:在二叉查找树的基础上,让左右子树的长度尽量相同,那么这样的树叫做平衡二叉树
 集合/23.png)
图23)定义
- 二叉树左右两个子树的高度差不超过 1
- 任意节点的左右两个子树都是一颗平衡二叉树
 集合/24.png)
图24) 集合/25.png)
图25) 集合/26.png)
图26)平衡二叉树-左旋
平衡二叉树-旋转
- 左旋
- 右旋
旋转的目的:让二叉树再次变成一颗平衡二叉树 (原来就是平衡二叉树,只不过由于添加了一个节点,不再是平衡二叉树,所以需要通过旋转再次变成平衡二叉树)
触发时机:当添加一个节点之后,该树不再是一颗平衡二叉树
平衡二叉树-左旋
 集合/27.png)
图27)此时,当再添加一个节点 12 ,此时二叉树就不是平衡二叉树了,这时候就触发了旋转
 集合/28.png)
图28) 集合/29.png)
图29)复杂的左旋
 集合/30.png)
图30) 集合/31.png)
图31)左旋:就是将根节点的右侧往左拉,原先的右子节点变成新的父节点,并把多余的左子节点出让,给已经降级的根节点当右子节点
平衡二叉树-右旋
平衡二叉树-右旋
 集合/32.png)
图32)此时,添加一个结点 1,由平衡二叉树变成了二叉树,此时触发旋转
 集合/33.png)
图33) 集合/34.png)
图34)复杂的右旋
 集合/35.png)
图35) 集合/36.png)
图36)右旋:将根节点的左侧往右拉,左子节点变成了新的父节点,并把多余的右子节点出让,给已经降级根节点当左子节点
平衡二叉树-左左和左右
平衡二叉树-旋转的四种情况
左左:当根节点左子树的左子树有节点插入,导致二叉树不平衡
右旋
 集合/37.png)
图37)左右:当根节点左子树的右子树有节点插入,导致二叉树不平衡
左旋-右旋
 集合/38.png)
图38)正确的步骤如下
(1) 将选中的区域左旋
 集合/39.png)
图39)(2) 此时,树的情况和左左情况类似,再进行一个整体右旋就可以了,两次旋转完毕就变成了平衡二叉树
 集合/40.png)
图40)平衡二叉树-右右和右左
右右:当根节点右子树的右子树有节点插入,导致二叉树不平衡
左旋
 集合/41.png)
图41)右左:当根节点右子树的左子树有节点插入,导致二叉树不平衡
右旋-左旋
 集合/42.png)
图42)正确的步骤
(1) 将选中的区域右旋
 集合/43.png)
图43)(2) 将整体左旋
 集合/44.png)
图44)红黑树-概述
红黑树
红黑树是一种自平衡的二叉查找树,是计算机科学中用到的一种数据结构
1972年出现,当时被称之为平衡二叉B树,后来,1978年被修改为如今的 ”红黑树”
他是一种特殊的二叉查找树,红黑树的每一个节点上都有存储位表示节点的颜色
每一个节点可以是红或者黑,红黑树不是高度平衡的,他的平衡是通过 ”红黑规则” 进行实现的
 集合/45.png)
图45)平衡二叉树和红黑树的区别
平衡二叉树是高度平衡的:
- 条件:当左右子树高度差超过1时 → 旋转
红黑树是一个二叉查找树:
- 但是不是高度平衡的
- 条件:自己的红黑规则 → 旋转
红黑树说:平衡二叉树每次高度差超过1就要旋转,效率也很低,并且这是强迫症
红黑树
- 平衡二叉B树
- 每一个节点可以是红或者黑
- 红黑树不是高度平衡的,他的平衡是通过 ”自己的红黑规则” 进行实现的
红黑树-红黑规侧
红黑规则
- 每一个节点或是红色的,或是黑色的
- 根节点必须是黑色
- 如果一个节点没有子节点或者父节点,则该节点相应的指针属相值为Nil,这些Nil视为叶节点,每个叶节点(Nil)是黑色的。(例如: 节点13没有父节点,所以他的父节点地址也记为Nil)
- 如果某一个节点是红色,那么他的子节点必须是黑色 (不能出现两个红节点相连的情况)
- 对每一个节点,从该节点到其所有后代叶节点的简单路径上,均包含相同数目的黑色节点。(简单路径不能回头,只能往前)
对上面第5条的解释: 例如节点8,到其后代的所有叶节点,黑色节点的数量都是2
红黑树-添加节点的默认颜色
添加节点
添加的节点的颜色,可以是黑色的,也可以是红色的
假如此时有三个黑色节点
(1) 添加第一个节点20
(2) 添加第二个节点18,此时违反红黑树规则。(对每一个节点,从该节点到其所有后代叶节点的简单路径上,均包含相同数目的黑色节点)
(3) 将节点18改为红色的,使他再次满足红黑树规则
(4) 添加第三个节点23,此时又破坏了红黑树规则。(对每一个节点,从该节点到其所有后代叶节点的简单路径上,均包含相同数目的黑色节点)
(5) 将节点23改为红色即可
通过上面的例子可知,添加三个元素,如果默认元素为黑色,一共需要调整两次
假如此时有三个红色节点
(1) 添加第一个节点20,此时违反红黑树规则。(根节点必须是黑色)
(2) 将节点20改为黑色
(3) 添加第二个节点18
(4) 添加第三个节点23
通过上面的例子可知,添加三个元素,如果默认颜色为红色,一共需要调整一次
添加节点时,默认为红色,效率最高
红黑树-添加节点后如何保证红黑规则1
添加多个节点
(1)节点在添加时,默认为红色,添加效率最高
(2) 添加节点20。(当添加的节点为根节点时,直接变为黑色即可)
(3) 添加第二个节点18。(其父节点为黑色,则不需要做任何操作)
(4) 添加第三个节点23
(5) 添加第四个节点22
其父节点为红色,叔叔节点也是红色,进行以下操作:
- 将父节点23设为黑色,将叔叔节点18设为黑色
- 将祖父节点20设为红色
- 如果祖父节点为根节点,则将根节点再次变为黑色
(6) 添加第五个节点16
(7) 添加节点19和节点24。(其父节点为黑色,不需要任何操作)
小结
红黑树-添加节点后如何保证红黑规则2
探究叔叔节点为黑色时的情景
将节点15和节点14添加到左边的红黑树中
(1) 添加节点15
节点15的父节点为红色,叔叔节点也为红色,进行如下步骤
- 将父节点和叔叔节点变为黑色
- 将祖父节点变为红色
- 如果祖父节点为根节点,则再次变为黑色
(2) 添加节点14
旋转时,叶子节点就当看不到
节点14的父节点为红色,叔叔节点为黑色,进行如下步骤
- 将父节点15设为黑色
- 将祖父节点16设为红色
- 以祖父节点为支点进行旋转 (左边长,则右旋; 右边长,则左旋)
小结