TreeMap与红黑树

1，红黑树

1）RBTree简介：
平衡二叉查找树balanced BST。
插入和删除时通过旋转将树的高度保持在logN。
应用在：TreeMap、(JDK 1.8链表长度大于等于8时)HashMap
红黑树通过旋转、着色两个操作，实现自平衡。
2）RBTree定义：用于实现自平衡，防止退化为链表
1.节点非红即黑。
2.根节点为黑色。
3.空节点为黑色。
4.每个红色节点必须有两个黑色子节点。(父子节点间不能出现2个连续红色节点)
5.黑高：任意节点到叶子节点，经过的黑色节点数相等。
根据性质4和5 -> 节点到叶子的最长路径不超过最短路径(纯黑)的2倍。
3）RBTree的数据结构：
fixAfterInsertion方法，会先把节点设置为红色。x.color = RED;

image.png
4）旋转操作
左旋：将节点旋转为其右孩子的左孩子。
image.png
image.png
右旋：将节点旋转为其左孩子的右孩子。
image.png
image.png

2，TreeMap插入Entry节点

1）当往红黑树中放入Entry节点。可能会破坏红黑树的性质，需要进行调整。
1.二分查找找到待插入节点的父节点。
2.设置新节点e和parent的父子指针。
3.插入后调整。(着色|旋转)
2）fixAfterInsertion插入后调整的方法。

image.png
image.png
3）左旋和右旋
image.png
image.png

3，TreeMap删除Entry节点

1）删除节点的情况
1.叶子节点直接删除
2.p只有左子树，pL与p的parent连接；p只有右子树，pR与p的parent连接。
3.p左右子树非空。
p的左子树pL设为q的子节点；p的右子树pR设为pL最大节点的子节点。

image.png
使用p的前驱或者后继节点替代p，然后删除原前驱或者后继节点。TreeMap中使用右子树最小的节点与p节点交换。
image.png
2）TreeMap删除节点

4，TreeMap检索Entry

TreeMap：底层使用红黑树，root节点作为成员变量。添加、取出元素的性能都比HashMap低，但Key都是基于Comparator或者Key本身可比较Comparable保持有序。
1）获取firstEntry与lastEntry

image.png
2）根据key检索Entry
image.png
3）获取第一个大于等于key的节点。getHigherEntry找到第一个大于key的节点
image.png
4）获取第一个小于等于key的节点。getLowerEntry找到第一个小于key的节点
image.png
5）获取所有的key、获取后继节点
KeySet实现了Iterable接口
image.png
image.png