兩個大前提：
- 紅黑樹還是查找樹，為了查找方便，左小右大；
- 保證樹的矮胖結(jié)構(gòu)，所以紅色節(jié)點 向上融合之后，樹是均衡的。
0、來源
紅黑樹的本質(zhì)還是二叉樹，但是因為二叉樹很容易產(chǎn)生傾斜問題，所以有了一種平衡二叉樹——2-3樹，2-3樹的每個節(jié)點可能有2個子節(jié)點（以下稱為2節(jié)點），也可能有3個子節(jié)點（以下稱為3節(jié)點），當新增節(jié)點的時候，有以下幾種狀況：
- 若查找到的節(jié)點為2節(jié)點，則直接添加子節(jié)點，或升為3節(jié)點即可；
- 若查找到的節(jié)點為3節(jié)點，則插入后會變成4節(jié)點，則4節(jié)點向上拆分為3節(jié)點即可；
- 若查找到的3節(jié)點的父節(jié)點，也是3節(jié)點，則可能一路上升到根節(jié)點，這是唯一可以增加樹高度的情況。
所以由此可見，只有第三種情況會增加樹高度，而查找的復雜度是由樹高度決定的，所以2-3樹是一種平衡二叉樹。
而紅黑樹本質(zhì)上與2-3樹完全一致，只是表示方式不同。
1、基本概念
紅黑樹的根本是二叉樹，它有五個特性：
（1）每個節(jié)點或者是黑色，或者是紅色。
（2）根節(jié)點是黑色。
（3）每個葉子節(jié)點（NIL）是黑色。 [注意：這里葉子節(jié)點，是指為空(NIL或NULL)的葉子節(jié)點！]
（4）如果一個節(jié)點是紅色的，則它的子節(jié)點必須是黑色的。
（5）從一個節(jié)點到該節(jié)點的子孫節(jié)點的所有路徑上包含相同數(shù)目的黑節(jié)點。
基本操作
左旋：將旋轉(zhuǎn)節(jié)點設(shè)置成為右子節(jié)點的左子節(jié)點，并將原右子節(jié)點的左子節(jié)點設(shè)為旋轉(zhuǎn)節(jié)點的右節(jié)點。
右旋：將旋轉(zhuǎn)節(jié)點設(shè)置 成為左子節(jié)點 的右子節(jié)點，并將原左子節(jié)點的右節(jié)點設(shè)為旋轉(zhuǎn)節(jié)點的左節(jié)點。
http://blog.csdn.net/xiangzhihong8/article/details/51589032
