termone07

本周学习大纲

1.排序
2.集合
3.常见数据结构

本周学习日历

日历	学习内容	时长(h)	其他
星期一	插入排序，递归算法，快速排序，Arrays	2
星期二	collection集合	1
星期三	list集合	1
星期四	数据结构（红黑树）	1
星期五	无	0
星期六	无	0
星期天	常见数据结构（栈，队列，数组，链表）	0.5

完成状态：

已完成本周任务。

学习收获

数据结构（红黑树）

定义

• 红黑树是一种自平衡的二叉查找树，是计算机科学中用到的一种数据结构。
• 1972年出现，当时被称之为平衡二叉B树。后来，1978年被修改为如今的”红黑树”。
• 它是一种特殊的二叉查找树，红黑树的每一个节点上都有存储位表示节点的颜色。
• 每一个节点可以是红或者黑;红黑树不是高度平衡的，它的平衡是通过”红黑规则”进行实现的。

红黑树增删改查的性能都很好

平衡二叉树和红黑树的区别

红黑树	平衡二叉树
是一个二叉树，但不是高度平衡的	高度平衡
条件：特有的红黑规则	当左右子树高度差超过1时，通过旋转保持平衡

数据结构(红黑树)红黑规则

1. 每一个节点或是红色的，或者是黑色的
2. 根节点必须是黑色
3. 如果一个节点没有子节点或者父节点，则该节点相应的指针属性值为Nil，这些Nil视为叶节点，每个叶节点(NiI)是黑色的
4. 如果某一个节点是红色，那么它的子节点必须是黑色(不能出现两个红色节点相连的情况)
5. 对每一个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点。

数据结构(红黑树)添加节点的规则

• 红黑树在添加节点的时候，添加的节点默认是红色的。（效率高）
• 规则：
  

下周学习大纲

1. ArrrayList源码分析
2. LinkedList和迭代器的源码分析
3. 泛型类……
4. 泛型的通配符
5. 二叉树
6. 平衡二叉树
7. TreeSet