文章目录查找红黑树1红黑树2插入红黑树(插入的节点颜色一定是红色)3 AVL树和红黑树比较4红黑树插入示例：5 TreeMap源代码：
红黑的树
红黑树是二叉树，但也可以在各节点中添加存储器位来表示节点的颜色，为Red或Black。 通过限制根到叶路径各节点的着色方法，保证红黑树没有比其他路径长两倍的路径，接近平衡。
红黑树的性质
各节点既不是红色也不是黑色； 根节点是黑色的； 如果节点为红色，则两个孩子的节点为黑色。 对于每个节点，从该节点到其所有后代的叶节点的简单路径包括相同数量的黑节点； 叶节点均为黑色(此处叶节点指空节点)； 满足上述性质后，红黑树可以保证最长边的长度=2*最短边的长度。 红黑树中的平衡是相对的平衡，不像AVL树那样是绝对的平衡。 在红黑树上插入/检索的时间的复杂性也是o(log ) ) n )。
红黑树节点的定义
classrbtreenode { rbtreenodeleft=null； RBTreeNode right=null； RBTreeNode parent=null； COLOR color=RED； //节点颜色int val； publicRbtreenode(intval ) { this.val=val； }1红黑树的搜索与二叉搜索树相同。
2红黑树的插入(插入节点的颜色一定是红色的)红黑树是在二叉搜索树的基础上加上了其平衡限制条件，所以红黑树的插入分为两个阶段。
(1). 按照二叉搜索的树规则插入新节点.
(2). 检测新节点插入后，红黑树的性质是否造到破坏.
分为以下三种情况进行讨论。
插入的节点是根节点。 [路线必须是黑色的。 更改颜色即可]插入节点的父节点为黑色。 “无调整，插入结束”插入节点的父节点为红色。 (红色不能相邻，需要进一步调整以划分情况)对于父节点为红色的情况：
1）其父(parent)节点有兄弟(brother)节点存在且是红色的：
此时，只要将其parent.parent更改为红色，将parent、brother更改为黑色即可。 parent.paprent已更改为红色，因此需要递归向上继续调整。
2）其父节点没有brother节点，或者brother节点为黑色
a .如果是同一侧(右转或左转) :
在这种情况下，必须将p.p向右旋转，将parent更改为黑色，将p.p更改为红色。
如果brother为黑色，则推测cur一定不是新插入的节点，而是在调整的过程中变红的节点(对于新插入的节点，由于原树不满足“每个路径黑色的节点相同”的性质，所以不成立)。
所以在这种情况下，cur下面应该有子树。 p.p右转，prent变成黑色，p.p变成红色。
b .不同边的情况(右转或左转) )。
首先，对于parent向左旋转，变为同一边的情况，操作在1 )中进行了叙述。
3 AVL树与红黑树的比较红黑树与AVL树均有效地平衡二叉树，增删修订的时间复杂度均为o(log(n ) )。 红黑树不追求绝对的平衡，最长路径不超过最短路径的2倍即可，相对减少了插入和旋转的次数，因此在频繁追加删除的结构中性能优于AVL树，红黑树的实现比较简单，AVL树的检索性能稍好在java集合框架的" TreeMap "、" TreeSet "下使用了红黑树。
4插入红黑树示例：
5 TreeMap源代码：红黑树的插入：
publicvput(kkey，V value ) { EntryK，V t=root； if(t==null ) {compare(key，key )； //type(andpossiblynull ) check root=newentry (key，value，null )； size=1； 模式计数； 返回空值； (} int cmp； EntryK，V parent； //splitcomparatorandcomparablepathscomparator？ super K cpr=comparator； if(CPR！=null}{do{parent=t； CMP=CPR.compare(key，t.key )； I
f (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) t = t.left; else if (cmp > 0) t = t.right; else 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;}插入之后的调整：
/** From CLR */private void fixAfterInsertion(Entry<K,V> x) { x.color = RED; while (x != null && x != root && x.parent.color == RED) { if (parentOf(x) == leftOf(parentOf(parentOf(x)))) { Entry<K,V> y = rightOf(parentOf(parentOf(x))); if (colorOf(y) == RED) { setColor(parentOf(x), BLACK); setColor(y, BLACK); setColor(parentOf(parentOf(x)), RED); x = parentOf(parentOf(x)); } else { 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) { setColor(parentOf(x), BLACK); setColor(y, BLACK); setColor(parentOf(parentOf(x)), RED); x = parentOf(parentOf(x)); } else { if (x == leftOf(parentOf(x))) { x = parentOf(x); rotateRight(x); } setColor(parentOf(x), BLACK); setColor(parentOf(parentOf(x)), RED); rotateLeft(parentOf(parentOf(x))); } } } root.color = BLACK;}里面封装了很多方法，如取该节点的父节点：
private static <K,V> Entry<K,V> parentOf(Entry<K,V> p) { return (p == null ? null: p.parent);}