Red-Black Tree · 贰白

我才没有停更呢！红黑树，走着！

数据结构是指逻辑意义上的数据结构组织方式及其相应的处理方式。

逻辑意义：实现层面，比如树，存储时可能是数组
数据组织方式：表、树、图、散列
处理方式：以某种特定的算法实现数据的增删改查及遍历

算法复杂度

O(1)、O(logn)、O(n)、O(nlogn)、O(n2)、O(2n)、O(n!)

数据结构的好与坏

AVL树&红黑树：取决于场景和数据量

让算法复杂度成为一种立体的思维习惯。算法的规模和调用频率。

什么是树

一个节点，即只有根节点，也可以是一棵树
其中任何一个节点与下面所有节点构成的树称为子树
根节点没有父节点，而叶子节点没有子节点
除根节点外，任何节点有且仅有一个父节点
任何节点可以有0~n个子节点

二叉查找树特性

左子树所有节点的值均小于或等于根节点的值
右子树所有节点的值均大于或等于根节点的值
左、右子树本身又各都是二叉查找树

二叉树如何找数据10

首先从根节点开始，比较10与9，由于10>9，则在右子树查找
比较10与13，由于10<13，则在左子树查找
比较10与11，由于10<11，则在左子树查找
查找到10

利用二分查找思想，经过三次，效率高。如果是列表的话，查找次数不止三次，正是因为这个特性，二叉查找树得到广泛应用。

二叉树如何找数据

前序遍历：根左右

中序遍历：左根右

后序遍历：左右根

二叉查找树的中序遍历就是有序序列，落到数轴上，即124789。

长歪的二叉查找树

都是大于上一个节点，都挂在右节点，说是树，其实是列表，几乎变成了线性，构建、查找树均效率低。那就需要把树变得扁一些，重新构建树，解决多次插入新节点导致的不平衡问题，也就是平衡二叉树。

平衡二叉树

性质

树的左右高度差的绝对值不能超过1
任何往下递归的左、右子树，必须符合第一条性质
没有任何节点的空树或只有根节点的树也是平衡二叉树

红黑树与AVL树

AVL树：是以苏联数学家Adelson-Velsky和Landis名字命名的平衡二叉树算法

插入和修改都不频繁，查询频繁。

红黑树：是于1972年发明的，当时称为对称二叉B树，1978年得到优化，正式命名为红黑树。它的特征是在每个节点上增加一个属性来表示节点的颜色，可以是红色和黑色。频繁插入和删除效率高。

AVL树与红黑树是兄弟关系，谁也不属于谁

红黑树

自平衡的二叉查找树

红黑树以各方面都不差的性能，在JDK集合中广泛使用(TreeMap和TreeSet底层实现，HashMap_JDK8)

节点只能是红色或黑色
根节点必须是黑色(旋转时很重要)
每个叶子节点都是黑色的空节点(NIL节点)
- nothing is leave，叶子节点的虚节点
- 旋转时，必须要判断叔叔节点的颜色，以决定旋转方向
一条路径上不能出现相邻的两个红色节点
每个红色节点的两个子节点都是黑色的(从每个叶子到根的所有路径上不能有两个连续的红色节点)
从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点
在任何递归子树内，根节点到叶子节点的所有路径上包含相同数目的黑色

红黑树从根到叶子的最长路径不会超过最短路径的2倍

插入新节点

红黑树在插入和删除节点时，会导致红黑树性质发生改变，需要调整树的结构。

操作
- 变色
- 旋转
  - 左旋
    - 逆时针旋转红黑树的两个节点，使得父节点被自己的右子节点取代，而自己称为左子节点
  - 右旋
    - 顺时针旋转红黑树的两个节点，使得父节点被自己的左子节点取代，而自己成为右子节点
过程
- 红黑树的根节点始终为黑色，插入节点默认为红色（黑色也可以，但是会增加路径上的黑色结点，很容易破坏红黑树性质，调整很麻烦，所以选择红色）
- 插入红色节点

插入新节点后的操作

如果父结点为黑色，红黑树性质继续保持，操作完成。
如果父结点为红色时，叔叔节点时红色，则重新着色
如果父节点是红色，叔叔节点是黑色，而新节点是父节点的右节点时，进行左旋
如果父节点是红色，叔叔节点是黑色，而新节点是父节点的左节点时，进行右旋

应用

ConcurrentHashMap中定义了5种节点类型，分别为Node(常规节点类型)、Null、ReservationNode、TreeBin(要挂红黑树啦，下面是红色或黑色的TreeNode)、ForwardingNode(在扩容时，迁移完会放一个节点，如果这个节点放在桶里，会转发到迁移后的表里)。

下图为ConcurrentHashMap中底层实现，树与链表间的转换，使得拥有高效率的查询。

转为树

当binCount大于等于TREEIFY_THRESHOLD时，转化为树。

转为链表

如果是小于，则变为列表。

TreeMap底层的红黑树实现，新节点默认为红色，判断当树不平衡时，进行变色及旋转操作。

TreeMap

集合框架图

集合是数据结构的载体

常用集合

HashSet、HashMap
TreeSet、TreeMap
- TreeSet其实就是TreeMap，只不过是TreeSet把value固定为Present，就是new Object()。浪费存储，new Object()大约占12个字节，和虚拟机有关，可以用visualVM分析。

1
2
3

public TreeSet() {
	this(new TreeMap<>());
}

1
2
3

public boolean add(E e) {
	return m.put(e, PRESENT)==null;
}

1	private static final Object PRESENT = new Object();

LinkedList、ArrayList
- LinkedList实现了Deque接口
- ArrayList的subList方法有坑，在subList场景中，高度注意对父集合元素的增加或删除，均会导致对子列表的遍历，增加、删除产生ConcurrentModificationException异常

List parent = new ArrayList();
parent.add(1);
parent.add(2);
parent.add(3);

List list = parent.subList(1, 2);
parent.add(4);
list.forEach(System.out::println);

Exception in thread "main" java.util.ConcurrentModificationException
at java.base/java.util.ArrayList$SubList.checkForComodification(ArrayList.java:1284)
at java.base/java.util.ArrayList$SubList.listIterator(ArrayList.java:1153)
at java.base/java.util.AbstractList.listIterator(AbstractList.java:311)
at java.base/java.util.ArrayList$SubList.iterator(ArrayList.java:1149)
at java.base/java.lang.Iterable.forEach(Iterable.java:74)

其它

为什么要关注位运算。float的浮点型的实现。0.8f-0.7是否等于0.7f-0.6f。不等于。因为float有精度损失。
如何在单位愉快的实施代码规约？1.立法透明；大家都参与2.执法严厉；制定了就要严格执行，包括奖惩机制，组织上也要支持，技术负责人和老板要支持，要知道代码约定的意义。3.方法不要超过80行
如何高效阅读源码？1.让你的使用方式是正确的，避免错误的使用；2.出问题时快速定位问题；有可能是底层、也有可能是框架原理性的问题；3.使用断点调试(watch查看值)
数据结构在增删改查时很少用，有啥用？1.数据结构和集合是两回事，不同的集合可以用相同的数据结构来实现。2.业务判断，数据结构是否适合业务快速迭代，快速run起来。
ArrayList和HashMap走天下，有什么问题？数据结构的增删改查有侧重，要恰当的使用数据结构，多看看并法包。
CopyOnWriteArrayList，简称COW，在写的时候会复制一份出来，读的时候读原始数据。写的时候通知读，数据要发生改变啦。写的时候是利用了volatile，保证了线程的可见性。
怎么看待设计模式？设计模型的三种模式：创建(解决对象创建和使用之间的耦合度)、结构(解决对象的结构和功能之间的耦合问题)和行为(解决对象不变变化对使用者带来的耦合问题)。比如享元模式，是为了把变和不变的地方分离开来。例如下围棋时，棋子可以放在盒子里继续使用，它的材质、大小、形状、厂家是一样，但是位置、颜色是会发生变化的
如何解决线程和线程池的恐惧？1.线程和线程池各自有状态，例如线程有running、block、wait；线程池有terminate、stop、running等。线程池解决了高效复用线程的问题。线程提高了进程的使用效率。虽然多线程跑的时候不太可控，但正因为多线程的存在，才可以不受控于CPU的核数。
领域驱动的难点？很难抽象出比较好的业务模型

贰白