一、引入：
????????在理想情況下，二叉搜索樹增刪查改的時(shí)間復(fù)雜度為O(logN)。但是，在插入數(shù)據(jù)的時(shí)候，可能會(huì)導(dǎo)致樹會(huì)傾斜，不同的插入順序會(huì)導(dǎo)致樹的高度不一樣，樹的高度決定了它查找的時(shí)間復(fù)雜度。例如，最壞的情況下是所有的節(jié)點(diǎn)都在一條斜線上，這樣樹的高度為N，查找的時(shí)間復(fù)雜度直接退化為O(N)。
????????基于二叉搜索樹存在的問題，一種新的樹——平衡二叉查找樹產(chǎn)生了。平衡樹在插入和刪除的時(shí)候，會(huì)通過旋轉(zhuǎn)操作將高度保持在logN。其中兩款具有代表性的平衡樹分別為AVL樹和紅黑樹。AVL樹由于實(shí)現(xiàn)比較復(fù)雜，而且插入和刪除性能差，在實(shí)際環(huán)境下的應(yīng)用不如紅黑樹。
最壞情況下例子：當(dāng)插入順序?yàn)?5-6-7-8-9-15-18時(shí)，二叉搜索樹退化為鏈表，當(dāng)查找18時(shí)，需要進(jìn)行7次查找，時(shí)間復(fù)雜度為O(N)。
二、紅黑二叉樹的定義：
????????紅黑樹是每個(gè)節(jié)點(diǎn)都帶有顏色屬性的二叉查找樹，顏色為紅色或黑色。
????????在二叉查找樹強(qiáng)制一般要求以外，對(duì)于任何有效的紅黑樹我們?cè)黾恿巳缦碌念~外要求：
1.節(jié)點(diǎn)是紅色或黑色。
2.根是黑色。
3.所有葉子都是黑色（葉子是NIL節(jié)點(diǎn)）。
4.每個(gè)紅色節(jié)點(diǎn)必須有兩個(gè)黑色的子節(jié)點(diǎn)。（從每個(gè)葉子到根的所有路徑上不能有兩個(gè)連續(xù)的紅色節(jié)點(diǎn)。）
5.從任一節(jié)點(diǎn)到其每個(gè)葉子的所有簡單路徑都包含相同數(shù)目的黑色節(jié)點(diǎn)。
????????正是紅黑樹的這5條性質(zhì)，使一棵n個(gè)節(jié)點(diǎn)的紅黑樹始終保持了logN的高度，使得紅黑樹的查找、插入、刪除的時(shí)間復(fù)雜度最壞為O(logN)。
三、旋轉(zhuǎn)：
????????當(dāng)在對(duì)紅黑樹進(jìn)行插入和刪除等操作時(shí)，對(duì)樹做了修改可能會(huì)破壞紅黑樹的性質(zhì)。為了繼續(xù)保持紅黑樹的性質(zhì)，可以通過對(duì)節(jié)點(diǎn)進(jìn)行重新著色，以及對(duì)樹進(jìn)行相關(guān)的旋轉(zhuǎn)操作，來達(dá)到對(duì)紅黑樹進(jìn)行插入或刪除節(jié)點(diǎn)等操作后繼續(xù)保持它的性質(zhì)或平衡的目的。
????????紅黑樹的旋轉(zhuǎn)操作，準(zhǔn)確地說是二叉樹的旋轉(zhuǎn)操作，也就是在二叉樹中的一種子樹調(diào)整操作,?旋轉(zhuǎn)并不影響對(duì)該二叉樹進(jìn)行中序遍歷的結(jié)果，也就是旋轉(zhuǎn)前后兩棵樹上的節(jié)點(diǎn)直線投影來的序列一樣的，這樣旋轉(zhuǎn)不會(huì)違反節(jié)點(diǎn)的大小關(guān)系(即左小右大)。樹旋轉(zhuǎn)通常應(yīng)用于需要調(diào)整樹的局部平衡性的場合。旋轉(zhuǎn)分為左旋轉(zhuǎn)和右旋轉(zhuǎn)。
左旋轉(zhuǎn)：
如上圖所示：以pivot節(jié)點(diǎn)為圖心，向左旋轉(zhuǎn)，此時(shí)pivot右子節(jié)點(diǎn)Y上升替代pivot原來位置，再將pivot右節(jié)點(diǎn)指向Y左節(jié)點(diǎn)，Y左節(jié)點(diǎn)指向pivot，左旋轉(zhuǎn)操作完成。
右旋轉(zhuǎn)：
右旋與左旋差不多，不做詳細(xì)介紹。
四、插入操作：
首先，所以新增的節(jié)點(diǎn)都標(biāo)記為紅色。（如果標(biāo)記????為黑色，就會(huì)導(dǎo)致根到葉子的路徑上，有一條路徑多一個(gè)額外的黑節(jié)點(diǎn)，破壞了紅黑樹的性質(zhì)5。）
以下插入情景不會(huì)對(duì)紅黑樹造成性質(zhì)破壞：
情景1：插入節(jié)點(diǎn)作為根節(jié)點(diǎn)的子節(jié)點(diǎn)
情景2：插入節(jié)點(diǎn)的父結(jié)節(jié)點(diǎn)是黑色的
以下插入情景需要修復(fù):
情景1：當(dāng)前節(jié)點(diǎn)為根節(jié)點(diǎn)，將根節(jié)點(diǎn)染成黑色即可。
情景2：插入節(jié)點(diǎn)的父節(jié)點(diǎn)為紅色：
????????情景2.1：叔節(jié)點(diǎn)存在，并且為紅色，將父叔節(jié)點(diǎn)染為黑色，將祖父節(jié)點(diǎn)染為紅色，并且再以祖父節(jié)點(diǎn)為當(dāng)前節(jié)點(diǎn)，進(jìn)行遞歸處理，直到當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)為黑色。
????????情景2.2：父節(jié)點(diǎn)為祖父節(jié)點(diǎn)的右子樹，叔節(jié)點(diǎn)不存在，或者為黑色。
????????????????情景2.2.1：插入節(jié)點(diǎn)為其父節(jié)點(diǎn)的右子節(jié)點(diǎn)，以祖父節(jié)點(diǎn)為圈心左旋轉(zhuǎn)，再將父節(jié)點(diǎn)染色為黑色，將祖父節(jié)點(diǎn)染為紅色。
????????????????情景2.2.2：插入節(jié)點(diǎn)為其父節(jié)點(diǎn)的左子節(jié)點(diǎn)，以父節(jié)點(diǎn)為圓心進(jìn)行右旋轉(zhuǎn)，得到情景（2.2.1）然后將父節(jié)點(diǎn)設(shè)置為當(dāng)前節(jié)點(diǎn)進(jìn)行遞歸處理。
????????情景2.3：父節(jié)點(diǎn)為祖父節(jié)點(diǎn)的左子樹，叔節(jié)點(diǎn)不存在，或者為黑色。
? ??????????????情景2.3.1：插入節(jié)點(diǎn)為其父節(jié)點(diǎn)的左子節(jié)點(diǎn)，與情景2.2.1為鏡像結(jié)構(gòu)，只需要將對(duì)應(yīng)的左旋轉(zhuǎn)變成右旋轉(zhuǎn)，右旋轉(zhuǎn)變成左旋轉(zhuǎn)即可。
? ??????????????情景2.3.2：插入節(jié)點(diǎn)為其父節(jié)點(diǎn)的右子節(jié)點(diǎn)。與情景2.2.2為鏡像結(jié)構(gòu)，只需要將對(duì)應(yīng)的左旋變成右旋轉(zhuǎn)，右旋轉(zhuǎn)變成左旋轉(zhuǎn)即可。
五、 插入總結(jié)：
????????在上面兩種修復(fù)情況當(dāng)中第二種是不會(huì)改變所在子樹的黑色路徑長度的，只有第一種情況可能改變黑色路徑長度，因?yàn)樗赡茏訕涓?jié)點(diǎn)涂紅，如果子樹根節(jié)點(diǎn)就是整棵樹的根節(jié)點(diǎn)時(shí)，在修復(fù)結(jié)束后會(huì)被重新設(shè)置成黑色，黑色路徑長度就加1了，但這個(gè)時(shí)候黑色路徑增加針對(duì)的不再是這個(gè)子樹了，而是整顆紅黑樹，所以是不會(huì)破壞性質(zhì)5的。至于性質(zhì)4看修補(bǔ)后的圖中結(jié)點(diǎn)的顏色就知道是不會(huì)破壞了。
????????插入結(jié)束之后，這顆子樹的滿足了性質(zhì)4(不能有兩個(gè)連續(xù)的紅色節(jié)點(diǎn))和性質(zhì)5(從任一節(jié)點(diǎn)到其每個(gè)葉子的所有簡單路徑都包含相同數(shù)目的黑色節(jié)點(diǎn))，又是一顆新的紅黑樹了。
六：簡單實(shí)現(xiàn)：
紅黑樹及節(jié)點(diǎn)節(jié)點(diǎn)定義：
//紅黑定義
public static final boolean RED =true;
public static final boolean BLACK =false;
//樹根的引用
private RBNoderoot;
static class RBNode<K extends Comparable<K>, V> {
????private RBNodeparent;
? ? private RBNodeleft;
? ? private RBNoderight;
? ? private boolean color;
? ? private K key;
? ? private V value;
}
旋轉(zhuǎn)操作：
private void leftRotate(RBNode x) { //左旋方法
RBNode y = x.right;
? ? // 1.將x的右子節(jié)點(diǎn)指向y的左子節(jié)點(diǎn),將y的左子節(jié)點(diǎn)的父節(jié)點(diǎn)更新為x
? ? x.right = y.left;
? ? if (y.left !=null)
????????y.left.parent = x;
? ?if (x.parent !=null) {? //2.當(dāng)x的父節(jié)點(diǎn)（不為空時(shí)） ，更新y的父節(jié)點(diǎn)為x的父節(jié)點(diǎn)，并將x的父節(jié)點(diǎn)指定為y
????????y.parent = x.parent;
? ? ? ? if (x == x.parent.left)
????????????x.parent.left = y;
????????else
? ? ? ? ? ? x.parent.right = y;
? ? }else {
????????this.root = y;
? ? ? ? this.root.parent =null;
? ? }
//3.將x的父節(jié)點(diǎn)更新為y，將y的左子節(jié)點(diǎn)更新為x
? ? x.parent = y;
? ? y.left = x;
}
private void rightRotate(RBNode y) { //右旋方法
????RBNode x = y.left;
? ? //1.將y的左子節(jié)點(diǎn)指向x的右子節(jié)點(diǎn)，并且更新x的右子節(jié)點(diǎn)的父節(jié)點(diǎn)為y
? ? y.left = x.right;
? ? if (x.right !=null)
????????x.right.parent = y;
? ? //2.當(dāng)y的父節(jié)點(diǎn)不為空時(shí)，更新x的父節(jié)點(diǎn)為y的父節(jié)點(diǎn)，更新y的父節(jié)點(diǎn)的指定為x
? ? if (y.parent !=null) {
????????x.parent = y.parent;
? ? ? ? if (y == y.parent.left)
????????????y.parent.left = x;
????????else
? ? ? ? ? ? y.parent.right = x;
? ? }else {
????????this.root = y;
? ? ? ? this.root.parent =null;
? ? }
//3.更新y的父節(jié)點(diǎn)為x，更新x的右子節(jié)點(diǎn)為y
? ? y.parent = x;
? ? x.right = y;
}
插入操作：
public void insert(RBNode node) {
//查找當(dāng)前node的父節(jié)點(diǎn)
? ? RBNode parent =null;
? ? RBNode x =this.root;
? ? while (x !=null) {
????????parent = x;
? ? ? ? //cmp>0 說明node.key 大于 x.key 需要x的右子樹查找
? ? ? ? //cmp==0 說明node.key 等于 x.key 說明需要進(jìn)行替換操作
? ? ? ? //cmp<0 說明node.key 小于 x.key 需要x的左子樹查找
? ? ? ? int cmp = node.key.compareTo(x.key);
? ? ? ? if (cmp >0)?
????????????x = x.right;
? ? ? ? else if (cmp ==0) {
????????????x.setValue(node.getValue());
????????????return;
? ? ? ? }else?
????????????x = x.left;
}
????node.parent = parent;
? ? if (parent !=null) {
????????//判斷node應(yīng)該插入parent的左節(jié)點(diǎn)還是右節(jié)點(diǎn)
? ? ? ? int cmp = node.key.compareTo(parent.key);
? ? ? ? if (cmp >0)
????????????parent.right = node;
????????else
? ? ? ? ? ? parent.left = node;
? ? }else?
????????this.root = node;
? ? //進(jìn)行紅黑樹平衡
? ? insertFixUp(node);
}
修復(fù)：
private void insertFixUp(RBNode node) {
????this.root.setColor(BLACK);
? ? RBNode parent = parentOf(node);
? ? RBNode Gparent = parentOf(parent);
? ? //插入節(jié)點(diǎn)的父節(jié)點(diǎn)為紅色
? ? if (parent !=null && isRed(parent)) {
? ? ? ? ? ?//如果父節(jié)點(diǎn)是紅色，那么一定存在祖父節(jié)點(diǎn)。因?yàn)楦?jié)點(diǎn)不可能是紅色
? ? ? ? RBNode uncle =null;
? ? ? ? if (parent == Gparent.left) {//父節(jié)點(diǎn)為祖父節(jié)點(diǎn)的左子樹
? ? ? ? ? ? uncle = Gparent.right;
? ? ? ? ? ? //叔節(jié)點(diǎn)存在，并且為紅色
? ? ? ? ? ? if (uncle !=null && isRed(uncle)) {
? ? ? ? ? ? ? ? setBlack(parent);
? ? ? ? ? ? ? ? setBlack(uncle);
? ? ? ? ? ? ? ? setRed(Gparent);
? ? ? ? ? ? ? ? insertFixUp(Gparent);
????????????????return;
? ? ? ? ? ? }
? ? ? ? ? ? if (uncle ==null || isBlack(uncle)) {? //叔節(jié)點(diǎn)不存在，或者為黑色
? ? ? ? ? ? ? ? if (node == parent.left) {
????????????????????setBlack(parent);
? ? ? ? ? ? ? ? ? ? setRed(Gparent);
? ? ? ? ? ? ? ? ? ? rightRotate(Gparent);
????????????????????return;
? ? ? ? ? ? ? ? }
????????????if (node == parent.right) { //插入節(jié)點(diǎn)為其父節(jié)點(diǎn)的右子節(jié)點(diǎn)
? ? ? ? ? ? ? ? ? ? leftRotate(parent);
? ? ? ? ? ? ? ? ? ? insertFixUp(parent);
????????????????????return;
? ? ? ? ? ? ? ? }
}
}else { //父節(jié)點(diǎn)為爺節(jié)點(diǎn)的右子數(shù)
? ? ? ? ? ? uncle = Gparent.left;
? ? ? ? ? ? if (uncle !=null && isRed(uncle)) {
????????????????setBlack(parent);
? ? ? ? ? ? ? ? setBlack(uncle);
? ? ? ? ? ? ? ? setRed(Gparent);
? ? ? ? ? ? ? ? insertFixUp(Gparent);
? ? ? ? ? ? ? ? return;
? ? ? ? ? ? }
if (uncle ==null || isBlack(uncle)) {? //插入節(jié)點(diǎn)為其父節(jié)點(diǎn)的左子節(jié)點(diǎn)
? ? ? ? ? ? ? ? if (node == parent.right) {
????????????????????setBlack(parent);
? ? ? ? ? ? ? ? ? ? setRed(Gparent);
? ? ? ? ? ? ? ? ? ? leftRotate(Gparent);
????????????????????return;
? ? ? ? ? ? ? ? }
if (node == parent.left) {? //插入節(jié)點(diǎn)為其父節(jié)點(diǎn)的右子節(jié)點(diǎn)
? ? ? ? ? ? ? ? ? ? rightRotate(parent);
? ? ? ? ? ? ? ? ? ? insertFixUp(parent);
????????????????????return;
? ? ? ? ? ? ? ? ?}
? ? ? ? ? ? ?}
????????}
????}
}
