算法：树和图-理论
引入树
在说树之前，我们先回想一下链表，在当前节点保存下一节点的引用，类时的如下:
class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}我们用过链表会发现，我们要想在链表中搜索或者访问一个元素时特别麻烦的，时间时间复杂度是O(N)的，为什么搜索和访问那么慢呢？？ 我们仔细一想
- 1.链表一个线性结构，只能从头到尾的遍历元素得到需要的值，并不像数组可以通过下标取得。
- 2.我们存入数据的时候，这个是一个无序的过程，我们只知道有数据进来就马上存进去。
树
假如从这两点入手的话，那么我们应该可以加快链表的搜索和访问的速度。某些研究人员发现，可以在这个链表的基础上，增加多一个节点的引用，即现在一个节点中有多个不一样的节点引用。
- 1.当前节点存入上一节点和下一节点的引用（双向链表）
- 2.当前节点存入多个下一节点的引用（树）
我们把一个节点中存入多个下一节点的数据结构称为树，首节点称为根节点，如图：
树：每个结点有零个或多个子结点；没有父结点的结点称为根结点；每一个非根结点有且只有一个父结点；除了根结点外，每个子结点可以分为多个不相交的子树。
二叉树
上图是树这种数据结构的定义，我们比较长用到的二叉树有是怎么样的呢？如图：
二叉树：是每个结点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。
上面这图也称完全二叉树
假设这个树有K层，此树前提是二叉树，K-1层必须是满的，K层左边（左子树）必须先满右边才能为空。
那么这样的数据结构是否可以增加访问速度呢？相比链表，在以知元素是在哪个子树，或许可以加快访问速度。在不知元素位置的时候，也是不能加快访问速度的，这还是一种无序的状态，需要访问元素还是需要遍历一次才可以找到。
⼆叉搜索树
某研究人员又发现，假如固定左边子树小于根节点，右边子树大于根节点，让元素存入的时候就排序好，那么访问速度就加快了，我们称这样的树为二叉搜索树。
它或者是一棵空树，或者是具有下列性质的二叉树：
⼆叉搜索树（英语： Binary Search Tree），也称⼆叉搜索树、有序⼆叉树（英语： ordered binary tree），排序⼆叉树（英语：sorted binary tree），是指⼀棵空树或者具有下列性质的⼆叉树： 1. 若任意节点的左⼦树不空，则左⼦树上所有结点的值均⼩于它的根结点的值； 2. 若任意节点的右⼦树不空，则右⼦树上所有结点的值均⼤于它的根结点的值； 3. 任意节点的左、右⼦树也分别为⼆叉查找树。
红黑树
假如有这样一个业务场景，一批已经排序好的数据，要找一个数据结构加快访问和搜索数据，那么二叉搜索树合适吗？？仔细想象。
因为数据是排序好的，假如我们使用这种由序的二叉搜索树之类数据结构，那么最后存完数据后，这颗树就只有左节点或者右节点，实际变成一个链表了。
为了改变二叉搜索树存在的不足，对二叉搜索树进行改进，使整颗树可以自平衡，他将这种排序二叉树称为“对称二叉B树”、“红黑树”。
- 性质1:每个节点要么是红色，要么是黑色。
- 性质2:根节点永远是黑色的。
- 除质3:所有的叶子节点都是空节点(即nil)，并且是黑色的。
- 性质4:每个红色节点的两个子节点都是黑色的。(从每个叶子到根的路径上不会有两个连续的红色节点。)
- 性质5:从任一节点到其子树中每个叶子节点(nil节点)的路径都包含相同数量的黑色节点。
利用颜色规则，通过旋转达到树的平衡。我是看这篇文章大致了解的:教你透彻了解红黑树
下面通过JDK中的TreeMap详细讲解了解一下。
java的树(TreeMap)是怎么实现的？
翻了一下JDK，发现Java并没有自己实现常见的树，二叉树、二叉搜索树等结构，而是在其他已实现的数据结构中，再次利用树这种类型，加快访问搜索速度。查找发现，TreeMap是基于红黑树实现的。所以，我们从此入手。关于Map数据类型可以访问，算法：列表List、映射Map、集合Set-理论
public class TreeMap<K,V> extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, java.io.Serializable{
private final Comparator<? super K> comparator; //比较器
public TreeMap() { comparator = null; } //构造函数之一
private transient Entry<K,V> root; //数据实际保存类
static final class Entry<K,V> implements Map.Entry<K,V> {
K key;
V value;
Entry<K,V> left;
Entry<K,V> right;
Entry<K,V> parent;
boolean color = BLACK;
//还有很多常见的方法getKey、getValue、setValue、equals
}
public V put(K key, V value) { //添加元素方法
Entry<K,V> t = root; //获取根节点
if (t == null) {
compare(key, key); // type (and possibly null) check
root = new Entry<>(key, value, null);
size = 1;
modCount++;
return null;
}
int cmp;
Entry<K,V> parent;
Comparator<? super K> cpr = comparator; //未指定比较器则为空
if (cpr != null) {
do {
parent = t;
cmp = cpr.compare(key, t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
else {
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;//为当前元素类型的比较器
do { //正常二叉树查找父节点，从根节点开始遍历
parent = t;
cmp = k.compareTo(t.key);
if (cmp < 0) //通过比较器后，当前值小于0
t = t.left; //和父节点的左节点进行比较
else if (cmp > 0)
t = t.right;
else // 0 即 key相等
return t.setValue(value); //修改值
} while (t != null);
}
Entry<K,V> e = new Entry<>(key, value, parent); //保存数据到节点中
if (cmp < 0) //根据刚刚获取父节点时，比较的大小
parent.left = e; //，选择存入左右节点
else
parent.right = e;
fixAfterInsertion(e); //上面是正常二叉树插入操作，后面是红黑树操作
size++;
modCount++;
return null;
}
}上面是正常二叉树插入操作，下面是整理二叉树形成红黑树操作。
这个算法直接看容易懵，需要按图服用。下面给出每种情况调用的图例。
情况1，父亲节点在祖父节点左边，且叔叔节点为红色。
情况2，父亲节点在祖父节点左边，叔叔节点不是红色，且当前节点位于父节点的右边
情况3，当前父亲节点在祖父节点右边，且叔叔节点是红色
情况4，当前父亲节点在祖父节点右边，叔叔节点不是红色，且当前节点位于父节点的左边
/** From CLR */
private void fixAfterInsertion(Entry<K,V> x) { //传入刚刚储存的节点
x.color = RED; //设节点为红色，这样只可能违背 红黑树的性质4
while (x != null && x != root && x.parent.color == RED) { //当X的父节点为黑时，满足红黑树性质
if (parentOf(x) == leftOf(parentOf(parentOf(x)))) { //当前节点的父亲节点在左边，才可能调用
//parentOf()返回 (p == null) ? null: p.parent
//leftOf()返回 (p == null) ? null: p.left;
Entry<K,V> y = rightOf(parentOf(parentOf(x))); //获取当前节点祖父节点的右节点，也可以称为叔叔节点
if (colorOf(y) == RED) { //情况1. y为红色时
setColor(parentOf(x), BLACK); //设父节点和叔叔节点为黑色，祖父节点红色
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x)); //改当前节点为 祖父节点 并再次循环
} else { //情况2，叔叔节点为黑或者为空
if (x == rightOf(parentOf(x))) {
x = parentOf(x);
rotateLeft(x); //左旋，为满足下面右旋后顺序正确
}
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
rotateRight(parentOf(parentOf(x))); //右旋
}
} else {
Entry<K,V> y = leftOf(parentOf(parentOf(x))); //获取叔叔节点
if (colorOf(y) == RED) { //情况3，叔叔节点红色
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
} else {
if (x == leftOf(parentOf(x))) { //情况4 ，叔叔节点不是红色
x = parentOf(x);
rotateRight(x);
}
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
rotateLeft(parentOf(parentOf(x)));
}
}
}
root.color = BLACK;
}
private void rotateLeft(Entry<K,V> p) { //左旋 ，情况2 左旋图解
if (p != null) {
Entry<K,V> r = p.right;
p.right = r.left;
if (r.left != null)
r.left.parent = p;
r.parent = p.parent;
if (p.parent == null)
root = r;
else if (p.parent.left == p)
p.parent.left = r;
else
p.parent.right = r;
r.left = p;
p.parent = r;
}
}
private void rotateRight(Entry<K,V> p) { //右旋 ，情况2 右旋图解
if (p != null) {
Entry<K,V> l = p.left;
p.left = l.right;
if (l.right != null) l.right.parent = p;
l.parent = p.parent;
if (p.parent == null)
root = l;
else if (p.parent.right == p)
p.parent.right = l;
else p.parent.left = l;
l.right = p;
p.parent = l;
}
}这个二叉树进行红黑处理，从开始的设置当前节点为红，判断父节点是否红、根节点，根据“性质4:每个红色节点的两个子节点都是黑色的”判断是否需要调整，通过调整节点颜色和旋转，保证二叉树符合所有红黑树的性质，达到一个自动平衡树的状态。
fixAfterInsertion方法逻辑顺序图
引入图
在树的基础上，我们知道当前节点中有多个指向下一节点的引用，假如还存在零个及以上指向上一节点（或者根节点）的引用，我们称之为图。
图
在链表的基础上，当前节点中有多个指向任意节点的引用。 图（Graph）是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G(V,E)，其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。
JDK源码中好像并没有图这种数据结构。
下面给出几个Java实现图的博文。