BST
二叉查找树就是一颗二叉树，他的左节点比父节点要小，右节点比父节点要大。他的高度决定的查找效率。
T key = a search key; //查找的值
Node root = point to the root of a bst; //二叉树的根节点
while(true){
if(root==null){
return null;
}
if(root.value==key){
return root;
}else if(key.compareTo(root.value)<0){
root = root.left;
}else{
root = root.righr;
}
}
return null;
当查找BST时，先进行当前节点比较：
- 如果相等的话就返回当前节点；
- 如果比当前节点小，则继续查找当前节点的左节点；
- 否则就继续查找当前节点的右节点。
直到当前节点指针为空或找到节点，查找结束。
BST的插入操作
Node node = create a new node;
Node root = point to the root of a bst; //二叉树的根节点
Node parent = null;
while(true){
if(root==null) break;
parent = root;
if(node.value.compareTo(root.value)<0){
root = parent.left;
}else{
root = parent.right;
}
}
if(parent!=null){
if(node.value.compareTo(root.value)<0){
parent.left = node;
}else{
parent.right = node;
}
}
插入BST时，先查找要插入的父节点。找到父节点后，通过比较与父节点的大小，决定要插入节点的位置。
BST的删除操作
查找到要删除的节点。
如果待删除的节点是叶子节点，则直接删除。
-
如果待删除的节点不是叶子节点，则先找到待删除节点的中序遍历的后继节点，用该后继节点的值替换待删除的节点的值，然后删除后继节点。
中序遍历：先遍历左节点，然后遍历根节点，最后遍历右节点（根节点放中间）
BST存在的问题
BST存在的问题是，数在插入的时候会导致倾斜，不同的插入顺序会导致数的高度不一样，而树的高度直接影响了树的查找效率。理想的高度是LogN，最坏的情况所有的节点都在一条斜线上，这样树的高度为N。
红黑树Red-Black Tree（RBTree）
基于BST存在的问题，平衡查找二叉树（Balanced BST）产生了。平衡树的插入和删除的时候，会通过旋转操作将高度保持在LogN。其中两款具有代表性的平衡术分别为AVL树和红黑树。AVL树由于实现比较复杂，而且插入和删除性能差，在实际环境下的应用不如红黑树。
红黑树的实际应用非常广泛，如Java中的HashMap和TreeSet，Java 8中HashMap的实现因为用RBTree代替链表（链表长度>8时），性能有所提升。
RBTree的规则定义
1.任何一个节点都有颜色，红色或黑色
2.根节点是黑色的
3.父子节点之间不能出现两个连续的红节点
4.任何一个根节点，遍历到他的子孙节点，所经过的黑色节点数必须相同
5.空节点被认为是黑色的
class Node<T>{
public T value;
public Node<T> parent;
public boolean isRed;
public Node<T> left;
public Node<T> right;
}
因为以上规则的限制，保证了红黑树的自平衡。红黑树从根到叶子节点的最长路径不会超过最短路径的2倍。
RBTree的自平衡策略
当插入或删除节点时，红黑树的规则可能被打破，这时候就需要做出一些调整，来维持RBT的规则定义。调整包括变色，左旋转和右旋转。
变色
为了符合红黑树规则，尝试将节点颜色红色节点变为黑色，或将黑色节点变为红色。
旋转
旋转操作(Rotate)的目的是使节点颜色符合定义，让RBTree的高度达到平衡。
左旋转：被旋转的节点从左侧上升到父节点
右旋转：被旋转的节点从右侧上升到父节点
什么时候用变色，什么时候用旋转呢？
查了一些资料，插入和删除包含了很多情况，比较复杂。这里有个传送们：
30张图带你彻底理解红黑树。
RBTree的插入操作
RBTree与BST的插入方式是一样的，只不过在插入之后，可能会导致树的不平衡，这时需要对树进行旋转操作和颜色修复（这里简称插入修复），使得他符合RBTree的定义。
新插入的节点颜色是红色，插入修复操作如果遇到父节点为黑色则修复操作结束。也就是说，只有在父节点为红色时是需要修复操作的。
当父节点为红色时，插入修复操作分以下三种情况：
- 叔叔节点也为红色。
- 叔叔节点为空，且祖父节点、父节点和新节点处于同一条斜线上。
- 叔叔节点为空，且祖父节点，父节点和新节点不处于同一条斜线上。
插入 - case1
如果叔叔节点也为红色，则将父节点，叔叔节点，祖父节点颜色互换，这样就符合了RBTree的定义。既维持了高度的平衡。下图中插入N节点，经过修复A、B、C节点颜色互换，如果A节点的父节点也为红色，则继续进行修复操作。
插入 - case 2
将B节点右旋，并且和父节点A互换颜色。如果B、C节点都是右节点，则将B节点左旋，然后与父节点A互换颜色就可以了。通过该修复操作的RBTree，高度和颜色都符合红黑树的定义。
插入 - case 3
现将C节点左旋，旋转后就将修复操作转换为 case 2。
插入操作总结
插入操作是一个向根节点回溯的操作，一旦牵涉的所有节点都符合红黑树的规则，则修复操作结束。之所以回回溯，是因为在进行case 1时，会将父节点颜色改变，有可能导致祖父节点不平衡，这时候就需要从祖父节点为起点，根据以上三种case做出调整。调整会一直到节点符合红黑树规则维泽，否则会一直到root节点结束，root节点永远是黑色的。
RBTree的删除操作
删除操作首先要做的是BST的删除操作，如果被删除的节点是叶子节点，则直接删除，如果是非叶子节点，会将该节点的中序遍历后继节点顶替要删除的节点。删除后就需要做删除修复操作，使RBTree符合定义，高度平衡。
删除修复操作在遇到删除节点是红色或到达root节点时结束修复。
删除操作是针对删除节点是黑色才有的（4. 任何一个根节点，遍历到他的子孙节点，经过的黑色节点必须相同），需要做的操作是从他的兄弟节点上借调黑色节点过来，如果没有黑色节点可以调用，则向上追溯，将每一级的黑色节点减1（？？），使红黑树符合定义。
删除操作的总体思想是从兄弟节点借调黑色节点使树保持局部平衡，如果局部平衡达成了，就看整体树是否平衡，如果不平衡就向上追溯调整。
删除修复节点分为有多种情况，下面举两种例子：
- 待删除的节点的兄弟节点是红色的
- 待删除的节点的兄弟节点是黑色的，且兄弟节点所有子节点都是黑色的
...
删除 - case 1
由于兄弟节点是红色的，无法从兄弟节点借调，所以将兄弟节点通过左旋提升到父节点。这样case 1就可以转换成 case 2 ，case 3，case 4进行处理了。
删除 - case 2
由于兄弟节点及其所有的子节点都是黑色，所以可以将兄弟节点变红，这样就可以保证树的局部颜色定义了。继续向上调整，知道整棵树的颜色符合RBTree的定义为止。
删除总结
红黑树的删除是最复杂的操作，复杂在于删除黑色节点的时候，如何从兄弟节点调用，以保证树符合定义。
总结
作为二叉查找树中面众多的实现之一，红黑树通过引入颜色的概念，通过颜色约束的使用，包括变色和旋转，来保持树的高度平衡。即使在最坏的情况下，操作的时间复杂度也为O(LogN)，原因是整个红黑树的高度保持是LogN(因为旋转修复)。
参考文章：
