我们知道，有序数组删除或插入数据较慢（向数组中插入数据时，涉及到插入位置前后数据移动的操作），但根据索引查找数据很快，可以快速定位到数据，适合查询。而链表正好相反，查找数据比较慢，插入或删除数据较快，只需要引用移动下就可以，适合增删。
而二叉树就是同时具有以上优势的数据结构。
该树缺点上面的树是非平衡树，由于插入数据顺序原因，多个节点可能会倾向根的一侧。极限情况下所有元素都在一侧，此时就变成了一个相当于链表的结构。
如图:依次插入节点[100,150,170,300,450,520 ...]
这种不平衡将会使树的层级增多（树的高度增加），查找或插入元素效率变低。
那么只要当插入元素或删除元素时还能维持树的平衡，使元素不至于向一端严重倾斜，就可以避免这个问题。
到此，红黑树闪亮登场， 红黑树就是一种平衡二叉树。
红黑树（Red Black Tree）红黑树是一种平衡二叉树，遵守如下规则来保证红黑树的平衡，保证每个节点在它左边的后代数目和在它右边的后代数目应该是大致相等（最长路径也不会超过最短路径的2倍）。
红黑树的规则红黑树是在二叉查找树基础之上再遵循如下规则的树
每个节点颜色不是黑色就是红色
根节点一定为黑色
两个红色节点不能相邻（红色节点的子节点一定是黑色）
从任意节点到叶子节点的每条路径包含的黑色节点数目相同（黑色高度）
每个叶子节点(NULL节点，空节点)是黑色
当插入或删除节点时，必须要遵守红黑树的规则，根据这些规则来决定是否需要改变树的结构或节点颜色，使其达到平衡。
查找节点并不影响树的平衡，所以红黑树的节点查找和二叉查找树的操作是一样的（请参考二叉查找树）。
如图: 红黑树 - 依次插入节点[100,200,300,400,500,600,700,800]
最终树的结构是大致平衡的，不像二叉查找树那样偏向一侧。
了解变色和旋转如果新插入元素或删除元素后，红黑树的规则被破坏，这时需要对树进行调整来重新满足红黑树规则。调整有变色和旋转（左旋或右旋）两种方式，接下来分别了解这两种方式：
变色
通过改变节点颜色修正红黑树，节点由红变黑或黑变红
旋转
通过改变节点的位置关系修正红黑树
如图: 以右旋为例
左旋则与右旋对称，为逆时针旋转。
图中空节点位置可以是多个节点构成的子树，也可以是一个具体节点。
右旋(来源Java TreeMap):
private void rotateRight(Entry<K,V> p) { 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; } }左旋(来源Java TreeMap):
private void rotateLeft(Entry<K,V> p) { 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; } }红黑树的插入和删除节点请看下一篇： 数据结构之红黑树-动图演示(下) - 更新中 ...