2019獨角獸企業(yè)重金招聘Python工程師標準>>>

【數(shù)據(jù)結(jié)構(gòu)和算法05】 紅-黑樹（看完包懂~）

置頂?2016年04月13日 15:50:25?eson_15?閱讀數(shù)：52681?標簽：?java數(shù)據(jù)結(jié)構(gòu)算法紅黑樹?更多

個人分類：?● 結(jié)構(gòu)算法------【數(shù)據(jù)結(jié)構(gòu)】

所屬專欄：?數(shù)據(jù)結(jié)構(gòu)和算法

?版權(quán)聲明：尊重博主原創(chuàng)文章，轉(zhuǎn)載請注明出處 https://blog.csdn.net/eson_15/article/details/51144079

【2018.6.2更新】我新搭建的博客系統(tǒng)上線了（使用SpringBoot搭建的），后面會在新系統(tǒng)中發(fā)表博客，這里也會給出鏈接，歡迎各位朋友收藏交流哈~?
博客地址：http://www.itcodai.com? ? ? ?

?（友情提示，紅-黑樹是基于二叉搜索樹的，如果對二叉搜索樹不了解，可以先看看：二叉搜索樹?）? ? ? ?

二叉搜索樹是個很好的數(shù)據(jù)結(jié)構(gòu)，可以快速地找到一個給定關(guān)鍵字的數(shù)據(jù)項，并且可以快速地插入和刪除數(shù)據(jù)項。但是二叉搜索樹有個很麻煩的問題，如果樹中插入的是隨機數(shù)據(jù)，則執(zhí)行效果很好，但如果插入的是有序或者逆序的數(shù)據(jù)，那么二叉搜索樹的執(zhí)行速度就變得很慢。因為當插入數(shù)值有序時，二叉樹就是非平衡的了，排在一條線上，其實就變成了一個鏈表……它的快速查找、插入和刪除指定數(shù)據(jù)項的能力就喪失了。

為了能以較快的時間 O(logN) 來搜索一棵樹，需要保證樹總是平衡的（或者至少大部分是平衡的），這就是說對樹中的每個節(jié)點在它左邊的后代數(shù)目和在它右邊的后代數(shù)目應(yīng)該大致相等。紅-黑樹的就是這樣的一棵平衡樹，對一個要插入的數(shù)據(jù)項，插入例程要檢查會不會破壞樹的特征，如果破壞了，程序就會進行糾正，根據(jù)需要改變樹的結(jié)構(gòu)，從而保持樹的平衡。那么紅-黑樹都有哪些特征呢？

1. 紅-黑樹的特征

它主要有兩個特征： 1.節(jié)點都有顏色；2.在插入和刪除的過程中，要遵循保持這些顏色的不同排列的規(guī)則。首先第一個特征很好解決，在節(jié)點類中店家一個數(shù)據(jù)字段，例如 boolean 型變量，以此來表示節(jié)點的顏色信息。第二個特征比較復(fù)雜，紅-黑樹有它的幾個規(guī)則，如果遵循這些規(guī)則，那么樹就是平衡的。紅-黑樹的主要規(guī)則如下：

• 1.每個節(jié)點不是紅色就是黑色的；

• 2.根節(jié)點總是黑色的；

• 3.如果節(jié)點是紅色的，則它的子節(jié)點必須是黑色的（反之不一定）；

• 4.從根節(jié)點到葉節(jié)點或空子節(jié)點的每條路徑，必須包含相同數(shù)目的黑色節(jié)點（即相同的黑色高度）。

在紅-黑樹中插入的節(jié)點都是紅色的，這不是偶然的，因為插入一個紅色節(jié)點比插入一個黑色節(jié)點違背紅-黑規(guī)則的可能性更小。原因是：插入黑色節(jié)點總會改變黑色高度（違背規(guī)則4），但是插入紅色節(jié)點只有一半的機會會違背規(guī)則3。另外違背規(guī)則3比違背規(guī)則4要更容易修正。當插入一個新的節(jié)點時，可能會破壞這種平衡性，那么紅-黑樹是如何修正的呢？

2. 平衡性的修正

紅-黑樹主要通過三種方式對平衡進行修正，改變節(jié)點顏色、左旋和右旋。這看起來有點抽象，我們分別來介紹它們。

2.1 變色

改變節(jié)點顏色比較容易理解，因為它違背了規(guī)則3。假設(shè)現(xiàn)在有個節(jié)點E，然后插入節(jié)點A和節(jié)點S，節(jié)點A在左子節(jié)點，S在右子節(jié)點，目前是平衡的。如果此時再插一個節(jié)點，那么就出現(xiàn)了不平衡了，因為紅色節(jié)點的子節(jié)點必須為黑色，但是新插的節(jié)點是紅色的。所以這時候就必須改變節(jié)點顏色了。所以我們將根的兩個子節(jié)點從紅色變?yōu)楹谏?#xff08;至于為什么都要變，下面插入的時候會詳細介紹），將父節(jié)點會從黑色變成紅色。可以用如下示意圖表示一下：

2.2 左旋

通常左旋操作用于將一個向右傾斜的紅色鏈接旋轉(zhuǎn)為向左鏈接。示意圖如下：

左旋有個很萌萌噠的動態(tài)示意圖，可以方便理解：

.3 右旋

右旋可左旋剛好相反，這里不再贅述，直接看示意圖：

當然咯，右旋也有個萌萌的動態(tài)圖：

這里主要介紹了紅-黑樹對平衡的三種修正方式，大家有個感性的認識，那么什么時候該修正呢？什么時候該用哪種修正呢？這將是接下來我們要探討的問題。

3. 紅-黑樹的操作

紅-黑樹的基本操作是添加、刪除和旋轉(zhuǎn)。對紅-黑樹進行添加或刪除后，可能會破壞其平衡性，會用到哪種旋轉(zhuǎn)方式去修正呢？我們首先對紅-黑樹的節(jié)點做一介紹，然后分別對左旋和右旋的具體實現(xiàn)做一分析，最后我們探討下紅-黑樹的具體操作。

3.1 紅-黑樹的節(jié)點

紅-黑樹是對二叉搜索樹的改進，所以其節(jié)點與二叉搜索樹是差不多的，只不過在它基礎(chǔ)上增加了一個boolean型變量來表示節(jié)點的顏色，具體看RBNode類：

public class RBNode<T extends Comparable<T>>{boolean color; //顏色T key; //關(guān)鍵字(鍵值)RBNode<T> left; //左子節(jié)點RBNode<T> right; //右子節(jié)點RBNode<T> parent; //父節(jié)點public RBNode(T key, boolean color, RBNode<T> parent, RBNode<T> left, RBNode<T> right) {this.key = key;this.color = color;this.parent = parent;this.left = left;this.right = right;}public T getKey() {return key;}public String toString() {return "" + key + (this.color == RED? "R" : "B");} }

3.2 左旋的具體實現(xiàn)

上面對左旋的概念已經(jīng)有了感性的認識了，這里就不再贅述了，我們從下面的代碼中結(jié)合上面的示意圖，探討一下左旋的具體實現(xiàn)：

/*************對紅黑樹節(jié)點x進行左旋操作 ******************/ /** 左旋示意圖：對節(jié)點x進行左旋* ? ? p ? ? ? ? ? ? ? ? ? ? ? p* ? ?/ ? ? ? ? ? ? ? ? ? ? ? /* ? x ? ? ? ? ? ? ? ? ? ? ? y* ?/ \ ? ? ? ? ? ? ? ? ? ? / \* lx ?y ? ? ?-----> ? ? ? x ?ry* ? ?/ \ ? ? ? ? ? ? ? ? / \* ? ly ry ? ? ? ? ? ? ? lx ly* 左旋做了三件事：* 1. 將y的左子節(jié)點賦給x的右子節(jié)點,并將x賦給y左子節(jié)點的父節(jié)點(y左子節(jié)點非空時)* 2. 將x的父節(jié)點p(非空時)賦給y的父節(jié)點，同時更新p的子節(jié)點為y(左或右)* 3. 將y的左子節(jié)點設(shè)為x，將x的父節(jié)點設(shè)為y*/ private void leftRotate(RBNode<T> x) {//1. 將y的左子節(jié)點賦給x的右子節(jié)點，并將x賦給y左子節(jié)點的父節(jié)點(y左子節(jié)點非空時)RBNode<T> y = x.right;x.right = y.left;if(y.left != null)?y.left.parent = x;//2. 將x的父節(jié)點p(非空時)賦給y的父節(jié)點，同時更新p的子節(jié)點為y(左或右)y.parent = x.parent;if(x.parent == null) {this.root = y; //如果x的父節(jié)點為空，則將y設(shè)為父節(jié)點} else {if(x == x.parent.left) //如果x是左子節(jié)點x.parent.left = y; //則也將y設(shè)為左子節(jié)點elsex.parent.right = y;//否則將y設(shè)為右子節(jié)點}//3. 將y的左子節(jié)點設(shè)為x，將x的父節(jié)點設(shè)為yy.left = x;x.parent = y;?? ??? ? }

3.3 右旋具體實現(xiàn)

上面對右旋的概念已經(jīng)有了感性的認識了，這里也不再贅述了，我們從下面的代碼中結(jié)合上面的示意圖，探討一下右旋的具體實現(xiàn)：

/*************對紅黑樹節(jié)點y進行右旋操作 ******************/ /** 左旋示意圖：對節(jié)點y進行右旋* ? ? ? ?p ? ? ? ? ? ? ? ? ? p* ? ? ? / ? ? ? ? ? ? ? ? ? /* ? ? ?y ? ? ? ? ? ? ? ? ? x* ? ? / \ ? ? ? ? ? ? ? ? / \* ? ?x ?ry ? -----> ? ? ?lx ?y* ? / \ ? ? ? ? ? ? ? ? ? ? / \* lx ?rx ? ? ? ? ? ? ? ? ? rx ry* 右旋做了三件事：* 1. 將x的右子節(jié)點賦給y的左子節(jié)點,并將y賦給x右子節(jié)點的父節(jié)點(x右子節(jié)點非空時)* 2. 將y的父節(jié)點p(非空時)賦給x的父節(jié)點，同時更新p的子節(jié)點為x(左或右)* 3. 將x的右子節(jié)點設(shè)為y，將y的父節(jié)點設(shè)為x*/ private void rightRotate(RBNode<T> y) {//1. 將y的左子節(jié)點賦給x的右子節(jié)點，并將x賦給y左子節(jié)點的父節(jié)點(y左子節(jié)點非空時)RBNode<T> x = y.left;y.left = x.right;if(x.right != null)?x.right.parent = y;//2. 將x的父節(jié)點p(非空時)賦給y的父節(jié)點，同時更新p的子節(jié)點為y(左或右)x.parent = y.parent;if(y.parent == null) {this.root = x; //如果x的父節(jié)點為空，則將y設(shè)為父節(jié)點} else {if(y == y.parent.right) //如果x是左子節(jié)點y.parent.right = x; //則也將y設(shè)為左子節(jié)點elsey.parent.left = x;//否則將y設(shè)為右子節(jié)點}//3. 將y的左子節(jié)點設(shè)為x，將x的父節(jié)點設(shè)為yx.right = y;y.parent = x;?? ??? ? }

3.4 插入操作

分析完了紅-黑樹中主要的旋轉(zhuǎn)操作，接下來我們開始分析常見的插入、刪除等操作了。這里先分析插入操作。 由于紅-黑樹是二叉搜索樹的改進，所以插入操作的前半工作時相同的，即先找到待插入的位置，再將節(jié)點插入，先來看看插入的前半段代碼：

/*********************** 向紅黑樹中插入節(jié)點 **********************/ public void insert(T key) {RBNode<T> node = new RBNode<T>(key, RED, null, null, null);if(node != null)?insert(node); }//將節(jié)點插入到紅黑樹中，這個過程與二叉搜索樹是一樣的 private void insert(RBNode<T> node) {RBNode<T> current = null; //表示最后node的父節(jié)點RBNode<T> x = this.root; //用來向下搜索用的//1. 找到插入的位置while(x != null) {current = x;int cmp = node.key.compareTo(x.key);if(cmp < 0)?x = x.left;elsex = x.right;}node.parent = current; //找到了位置，將當前current作為node的父節(jié)點//2. 接下來判斷node是插在左子節(jié)點還是右子節(jié)點if(current != null) {int cmp = node.key.compareTo(current.key);if(cmp < 0)current.left = node;elsecurrent.right = node;} else {this.root = node;}//3. 將它重新修整為一顆紅黑樹insertFixUp(node); }

這與二叉搜索樹中實現(xiàn)的思路一模一樣，這里不再贅述，主要看看方法里面最后一步insertFixUp操作。因為插入后可能會導(dǎo)致樹的不平衡，insertFixUp方法里主要是分情況討論，分析何時變色，何時左旋，何時右旋。我們先從理論上分析具體的情況，然后再看insertFixUp方法的具體實現(xiàn)。

如果是第一次插入，由于原樹為空，所以只會違反紅-黑樹的規(guī)則2，所以只要把根節(jié)點涂黑即可；如果插入節(jié)點的父節(jié)點是黑色的，那不會違背紅-黑樹的規(guī)則，什么也不需要做；但是遇到如下三種情況時，我們就要開始變色和旋轉(zhuǎn)了：

• 1.插入節(jié)點的父節(jié)點和其叔叔節(jié)點（祖父節(jié)點的另一個子節(jié)點）均為紅色的；

• 2.插入節(jié)點的父節(jié)點是紅色，叔叔節(jié)點是黑色，且插入節(jié)點是其父節(jié)點的右子節(jié)點；

• 3.插入節(jié)點的父節(jié)點是紅色，叔叔節(jié)點是黑色，且插入節(jié)點是其父節(jié)點的左子節(jié)點。

下面我們先挨個分析這三種情況都需要如何操作，然后再給出實現(xiàn)代碼。

對于情況1：插入節(jié)點的父節(jié)點和其叔叔節(jié)點（祖父節(jié)點的另一個子節(jié)點）均為紅色的。此時，肯定存在祖父節(jié)點，但是不知道父節(jié)點是其左子節(jié)點還是右子節(jié)點，但是由于對稱性，我們只要討論出一邊的情況，另一種情況自然也與之對應(yīng)。這里考慮父節(jié)點是祖父節(jié)點的左子節(jié)點的情況，如下左圖所示：

對于這種情況，我們要做的操作有：將當前節(jié)點(4)的父節(jié)點(5)和叔叔節(jié)點(8)涂黑，將祖父節(jié)點(7)涂紅，變成上右圖所示的情況。再將當前節(jié)點指向其祖父節(jié)點，再次從新的當前節(jié)點開始算法（具體等下看下面的程序）。這樣上右圖就變成了情況2了。

對于情況2：插入節(jié)點的父節(jié)點是紅色，叔叔節(jié)點是黑色，且插入節(jié)點是其父節(jié)點的右子節(jié)點。我們要做的操作有：將當前節(jié)點(7)的父節(jié)點(2)作為新的節(jié)點，以新的當前節(jié)點為支點做左旋操作。完成后如左下圖所示，這樣左下圖就變成情況3了。

對于情況3：插入節(jié)點的父節(jié)點是紅色，叔叔節(jié)點是黑色，且插入節(jié)點是其父節(jié)點的左子節(jié)點。我們要做的操作有：將當前節(jié)點的父節(jié)點(7)涂黑，將祖父節(jié)點(11)涂紅，在祖父節(jié)點為支點做右旋操作。最后把根節(jié)點涂黑，整個紅-黑樹重新恢復(fù)了平衡，如右上圖所示。至此，插入操作完成！

我們可以看出，如果是從情況1開始發(fā)生的，必然會走完情況2和3，也就是說這是一整個流程，當然咯，實際中可能不一定會從情況1發(fā)生，如果從情況2開始發(fā)生，那再走個情況3即可完成調(diào)整，如果直接只要調(diào)整情況3，那么前兩種情況均不需要調(diào)整了。故變色和旋轉(zhuǎn)之間的先后關(guān)系可以表示為：變色->左旋->右旋。

至此，我們完成了全部的插入操作。下面我們看看insertFixUp方法中的具體實現(xiàn)（可以結(jié)合上面的分析圖，更加利與理解）：

?private void insertFixUp(RBNode<T> node) { ?RBNode<T> parent, gparent; //定義父節(jié)點和祖父節(jié)點 ?//需要修整的條件：父節(jié)點存在，且父節(jié)點的顏色是紅色 ?while(((parent = parentOf(node)) != null) && isRed(parent)) { ?gparent = parentOf(parent);//獲得祖父節(jié)點 ?//若父節(jié)點是祖父節(jié)點的左子節(jié)點，下面else與其相反 ?if(parent == gparent.left) { ? ? ? ? ? ? ? ? ?RBNode<T> uncle = gparent.right; //獲得叔叔節(jié)點 ?//case1: 叔叔節(jié)點也是紅色 ?if(uncle != null && isRed(uncle)) { ?setBlack(parent); //把父節(jié)點和叔叔節(jié)點涂黑 ?setBlack(uncle); ?setRed(gparent); //把祖父節(jié)點涂紅 ?node = gparent; //將位置放到祖父節(jié)點處 ?continue; //繼續(xù)while，重新判斷 ?} ?//case2: 叔叔節(jié)點是黑色，且當前節(jié)點是右子節(jié)點 ?if(node == parent.right) { ?leftRotate(parent); //從父節(jié)點處左旋 ?RBNode<T> tmp = parent; //然后將父節(jié)點和自己調(diào)換一下，為下面右旋做準備 ?parent = node; ?node = tmp; ?} ?//case3: 叔叔節(jié)點是黑色，且當前節(jié)點是左子節(jié)點 ?setBlack(parent); ?setRed(gparent); ?rightRotate(gparent); ?} else { //若父節(jié)點是祖父節(jié)點的右子節(jié)點,與上面的完全相反，本質(zhì)一樣的 ?RBNode<T> uncle = gparent.left; ?//case1: 叔叔節(jié)點也是紅色 ?if(uncle != null & isRed(uncle)) { ?setBlack(parent); ?setBlack(uncle); ?setRed(gparent); ?node = gparent; ?continue; ?} ?//case2: 叔叔節(jié)點是黑色的，且當前節(jié)點是左子節(jié)點 ?if(node == parent.left) { ?rightRotate(parent); ?RBNode<T> tmp = parent; ?parent = node; ?node = tmp; ?} ?//case3: 叔叔節(jié)點是黑色的，且當前節(jié)點是右子節(jié)點 ?setBlack(parent); ?setRed(gparent); ?leftRotate(gparent); ?} ?} ?//將根節(jié)點設(shè)置為黑色 ?setBlack(this.root); ? } ?

?

4.完整源碼

??????? 終于分析完了插入和刪除操作的所有東西。另外，紅-黑樹還有一些其他操作，比如：查找特定值、遍歷、返回最值、銷毀樹等操作我將放到源碼中給大家呈現(xiàn)出來，詳見下面紅-黑樹的完整代碼。

?

package tree; /*** @description implementation of Red-Black Tree by Java* @author eson_15* @param <T>* @date 2016-4-18 19:27:28*/ public class RBTree<T extends Comparable<T>> {private RBNode<T> root; //根節(jié)點private static final boolean RED = false; //定義紅黑樹標志private static final boolean BLACK = true;//內(nèi)部類：節(jié)點類public class RBNode<T extends Comparable<T>>{boolean color; //顏色T key; //關(guān)鍵字(鍵值)RBNode<T> left; //左子節(jié)點RBNode<T> right; //右子節(jié)點RBNode<T> parent; //父節(jié)點public RBNode(T key, boolean color, RBNode<T> parent, RBNode<T> left, RBNode<T> right) {this.key = key;this.color = color;this.parent = parent;this.left = left;this.right = right;}public T getKey() {return key;}public String toString() {return "" + key + (this.color == RED? "R" : "B");}}public RBTree() {root = null;}public RBNode<T> parentOf(RBNode<T> node) { //獲得父節(jié)點return node != null? node.parent : null;}public void setParent(RBNode<T> node, RBNode<T> parent) { //設(shè)置父節(jié)點if(node != null)?node.parent = parent;}public boolean colorOf(RBNode<T> node) { //獲得節(jié)點的顏色return node != null? node.color : BLACK;}public boolean isRed(RBNode<T> node) { //判斷節(jié)點的顏色return (node != null)&&(node.color == RED)? true : false;}public boolean isBlack(RBNode<T> node) {return !isRed(node);}public void setRed(RBNode<T> node) { //設(shè)置節(jié)點的顏色if(node != null)?node.color = RED;}public void setBlack(RBNode<T> node) {if(node != null) {node.color = BLACK;}}public void setColor(RBNode<T> node, boolean color) {if(node != null)node.color = color;}/***************** 前序遍歷紅黑樹 *********************/public void preOrder() {preOrder(root);}private void preOrder(RBNode<T> tree) {if(tree != null) {System.out.print(tree.key + " ");preOrder(tree.left);preOrder(tree.right);}}/***************** 中序遍歷紅黑樹 *********************/public void inOrder() {inOrder(root);}private void inOrder(RBNode<T> tree) {if(tree != null) {preOrder(tree.left);System.out.print(tree.key + " ");preOrder(tree.right);}}/***************** 后序遍歷紅黑樹 *********************/public void postOrder() {postOrder(root);}private void postOrder(RBNode<T> tree) {if(tree != null) {preOrder(tree.left);preOrder(tree.right);System.out.print(tree.key + " ");}}/**************** 查找紅黑樹中鍵值為key的節(jié)點 ***************/public RBNode<T> search(T key) {return search(root, key); //?? ??? ?return search2(root, key); //使用遞歸的方法，本質(zhì)一樣的}private RBNode<T> search(RBNode<T> x, T key) {while(x != null) {int cmp = key.compareTo(x.key);if(cmp < 0)?x = x.left;else if(cmp > 0)?x = x.right;else?return x;}return x;}//使用遞歸private RBNode<T> search2(RBNode<T> x, T key) {if(x == null)return x;int cmp = key.compareTo(x.key);if(cmp < 0)return search2(x.left, key);else if(cmp > 0)?return search2(x.right, key);elsereturn x;}/**************** 查找最小節(jié)點的值 ?**********************/public T minValue() {RBNode<T> node = minNode(root);if(node != null)return node.key;return null;}private RBNode<T> minNode(RBNode<T> tree) {if(tree == null)return null;while(tree.left != null) {tree = tree.left;}return tree;}/******************** 查找最大節(jié)點的值 *******************/public T maxValue() {RBNode<T> node = maxNode(root);if(node != null)return node.key;return null;}private RBNode<T> maxNode(RBNode<T> tree) {if(tree == null)return null;while(tree.right != null)tree = tree.right;return tree;}/********* 查找節(jié)點x的后繼節(jié)點,即大于節(jié)點x的最小節(jié)點 ***********/public RBNode<T> successor(RBNode<T> x) {//如果x有右子節(jié)點，那么后繼節(jié)點為“以右子節(jié)點為根的子樹的最小節(jié)點”if(x.right != null)?return minNode(x.right);//如果x沒有右子節(jié)點，會出現(xiàn)以下兩種情況：//1. x是其父節(jié)點的左子節(jié)點，則x的后繼節(jié)點為它的父節(jié)點//2. x是其父節(jié)點的右子節(jié)點，則先查找x的父節(jié)點p，然后對p再次進行這兩個條件的判斷RBNode<T> p = x.parent;while((p != null) && (x == p.right)) { //對應(yīng)情況2x = p;p = x.parent;}return p; //對應(yīng)情況1}/********* 查找節(jié)點x的前驅(qū)節(jié)點，即小于節(jié)點x的最大節(jié)點 ************/public RBNode<T> predecessor(RBNode<T> x) {//如果x有左子節(jié)點，那么前驅(qū)結(jié)點為“左子節(jié)點為根的子樹的最大節(jié)點”if(x.left != null)?return maxNode(x.left);//如果x沒有左子節(jié)點，會出現(xiàn)以下兩種情況：//1. x是其父節(jié)點的右子節(jié)點，則x的前驅(qū)節(jié)點是它的父節(jié)點//2. x是其父節(jié)點的左子節(jié)點，則先查找x的父節(jié)點p，然后對p再次進行這兩個條件的判斷RBNode<T> p = x.parent;while((p != null) && (x == p.left)) { //對應(yīng)情況2x = p;p = x.parent;}return p; //對應(yīng)情況1}/*************對紅黑樹節(jié)點x進行左旋操作 ******************//** 左旋示意圖：對節(jié)點x進行左旋* ? ? p ? ? ? ? ? ? ? ? ? ? ? p* ? ?/ ? ? ? ? ? ? ? ? ? ? ? /* ? x ? ? ? ? ? ? ? ? ? ? ? y* ?/ \ ? ? ? ? ? ? ? ? ? ? / \* lx ?y ? ? ?-----> ? ? ? x ?ry* ? ?/ \ ? ? ? ? ? ? ? ? / \* ? ly ry ? ? ? ? ? ? ? lx ly* 左旋做了三件事：* 1. 將y的左子節(jié)點賦給x的右子節(jié)點,并將x賦給y左子節(jié)點的父節(jié)點(y左子節(jié)點非空時)* 2. 將x的父節(jié)點p(非空時)賦給y的父節(jié)點，同時更新p的子節(jié)點為y(左或右)* 3. 將y的左子節(jié)點設(shè)為x，將x的父節(jié)點設(shè)為y*/private void leftRotate(RBNode<T> x) {//1. 將y的左子節(jié)點賦給x的右子節(jié)點，并將x賦給y左子節(jié)點的父節(jié)點(y左子節(jié)點非空時)RBNode<T> y = x.right;x.right = y.left;if(y.left != null)?y.left.parent = x;//2. 將x的父節(jié)點p(非空時)賦給y的父節(jié)點，同時更新p的子節(jié)點為y(左或右)y.parent = x.parent;if(x.parent == null) {this.root = y; //如果x的父節(jié)點為空，則將y設(shè)為父節(jié)點} else {if(x == x.parent.left) //如果x是左子節(jié)點x.parent.left = y; //則也將y設(shè)為左子節(jié)點elsex.parent.right = y;//否則將y設(shè)為右子節(jié)點}//3. 將y的左子節(jié)點設(shè)為x，將x的父節(jié)點設(shè)為yy.left = x;x.parent = y;?? ??? ?}/*************對紅黑樹節(jié)點y進行右旋操作 ******************//** 左旋示意圖：對節(jié)點y進行右旋* ? ? ? ?p ? ? ? ? ? ? ? ? ? p* ? ? ? / ? ? ? ? ? ? ? ? ? /* ? ? ?y ? ? ? ? ? ? ? ? ? x* ? ? / \ ? ? ? ? ? ? ? ? / \* ? ?x ?ry ? -----> ? ? ?lx ?y* ? / \ ? ? ? ? ? ? ? ? ? ? / \* lx ?rx ? ? ? ? ? ? ? ? ? rx ry* 右旋做了三件事：* 1. 將x的右子節(jié)點賦給y的左子節(jié)點,并將y賦給x右子節(jié)點的父節(jié)點(x右子節(jié)點非空時)* 2. 將y的父節(jié)點p(非空時)賦給x的父節(jié)點，同時更新p的子節(jié)點為x(左或右)* 3. 將x的右子節(jié)點設(shè)為y，將y的父節(jié)點設(shè)為x*/private void rightRotate(RBNode<T> y) {//1. 將y的左子節(jié)點賦給x的右子節(jié)點，并將x賦給y左子節(jié)點的父節(jié)點(y左子節(jié)點非空時)RBNode<T> x = y.left;y.left = x.right;if(x.right != null)?x.right.parent = y;//2. 將x的父節(jié)點p(非空時)賦給y的父節(jié)點，同時更新p的子節(jié)點為y(左或右)x.parent = y.parent;if(y.parent == null) {this.root = x; //如果x的父節(jié)點為空，則將y設(shè)為父節(jié)點} else {if(y == y.parent.right) //如果x是左子節(jié)點y.parent.right = x; //則也將y設(shè)為左子節(jié)點elsey.parent.left = x;//否則將y設(shè)為右子節(jié)點}//3. 將y的左子節(jié)點設(shè)為x，將x的父節(jié)點設(shè)為yx.right = y;y.parent = x;?? ??? ?}/*********************** 向紅黑樹中插入節(jié)點 **********************/public void insert(T key) {RBNode<T> node = new RBNode<T>(key, RED, null, null, null);if(node != null)?insert(node);}//將節(jié)點插入到紅黑樹中，這個過程與二叉搜索樹是一樣的private void insert(RBNode<T> node) {RBNode<T> current = null; //表示最后node的父節(jié)點RBNode<T> x = this.root; //用來向下搜索用的//1. 找到插入的位置while(x != null) {current = x;int cmp = node.key.compareTo(x.key);if(cmp < 0)?x = x.left;elsex = x.right;}node.parent = current; //找到了位置，將當前current作為node的父節(jié)點//2. 接下來判斷node是插在左子節(jié)點還是右子節(jié)點if(current != null) {int cmp = node.key.compareTo(current.key);if(cmp < 0)current.left = node;elsecurrent.right = node;} else {this.root = node;}//3. 將它重新修整為一顆紅黑樹insertFixUp(node);}private void insertFixUp(RBNode<T> node) {RBNode<T> parent, gparent; //定義父節(jié)點和祖父節(jié)點//需要修整的條件：父節(jié)點存在，且父節(jié)點的顏色是紅色while(((parent = parentOf(node)) != null) && isRed(parent)) {gparent = parentOf(parent);//獲得祖父節(jié)點//若父節(jié)點是祖父節(jié)點的左子節(jié)點，下面else與其相反if(parent == gparent.left) {?? ??? ??? ??? ?RBNode<T> uncle = gparent.right; //獲得叔叔節(jié)點//case1: 叔叔節(jié)點也是紅色if(uncle != null && isRed(uncle)) {setBlack(parent); //把父節(jié)點和叔叔節(jié)點涂黑setBlack(uncle);setRed(gparent); //把祖父節(jié)點涂紅node = gparent; //將位置放到祖父節(jié)點處continue; //繼續(xù)while，重新判斷}//case2: 叔叔節(jié)點是黑色，且當前節(jié)點是右子節(jié)點if(node == parent.right) {leftRotate(parent); //從父節(jié)點處左旋RBNode<T> tmp = parent; //然后將父節(jié)點和自己調(diào)換一下，為下面右旋做準備parent = node;node = tmp;}//case3: 叔叔節(jié)點是黑色，且當前節(jié)點是左子節(jié)點setBlack(parent);setRed(gparent);rightRotate(gparent);} else { //若父節(jié)點是祖父節(jié)點的右子節(jié)點,與上面的完全相反，本質(zhì)一樣的RBNode<T> uncle = gparent.left;//case1: 叔叔節(jié)點也是紅色if(uncle != null & isRed(uncle)) {setBlack(parent);setBlack(uncle);setRed(gparent);node = gparent;continue;}//case2: 叔叔節(jié)點是黑色的，且當前節(jié)點是左子節(jié)點if(node == parent.left) {rightRotate(parent);RBNode<T> tmp = parent;parent = node;node = tmp;}//case3: 叔叔節(jié)點是黑色的，且當前節(jié)點是右子節(jié)點setBlack(parent);setRed(gparent);leftRotate(gparent);}}//將根節(jié)點設(shè)置為黑色setBlack(this.root);}/*********************** 刪除紅黑樹中的節(jié)點 **********************/public void remove(T key) {RBNode<T> node;if((node = search(root, key)) != null)remove(node);}private void remove(RBNode<T> node) {RBNode<T> child, parent;boolean color;//1. 被刪除的節(jié)點“左右子節(jié)點都不為空”的情況if((node.left != null) && (node.right != null)) {//先找到被刪除節(jié)點的后繼節(jié)點，用它來取代被刪除節(jié)點的位置RBNode<T> replace = node;// ?1). 獲取后繼節(jié)點replace = replace.right;while(replace.left != null)?replace = replace.left;// ?2). 處理“后繼節(jié)點”和“被刪除節(jié)點的父節(jié)點”之間的關(guān)系if(parentOf(node) != null) { //要刪除的節(jié)點不是根節(jié)點if(node == parentOf(node).left)?parentOf(node).left = replace;elseparentOf(node).right = replace;} else { //否則this.root = replace;}// ?3). 處理“后繼節(jié)點的子節(jié)點”和“被刪除節(jié)點的子節(jié)點”之間的關(guān)系child = replace.right; //后繼節(jié)點肯定不存在左子節(jié)點！parent = parentOf(replace);color = colorOf(replace);//保存后繼節(jié)點的顏色if(parent == node) { //后繼節(jié)點是被刪除節(jié)點的子節(jié)點parent = replace;} else { //否則if(child != null)?setParent(child, parent);parent.left = child;replace.right = node.right;setParent(node.right, replace);}replace.parent = node.parent;replace.color = node.color; //保持原來位置的顏色replace.left = node.left;node.left.parent = replace;if(color == BLACK) { //4. 如果移走的后繼節(jié)點顏色是黑色，重新修整紅黑樹removeFixUp(child, parent);//將后繼節(jié)點的child和parent傳進去}node = null;return;}}//node表示待修正的節(jié)點，即后繼節(jié)點的子節(jié)點（因為后繼節(jié)點被挪到刪除節(jié)點的位置去了）private void removeFixUp(RBNode<T> node, RBNode<T> parent) {RBNode<T> other;while((node == null || isBlack(node)) && (node != this.root)) {if(parent.left == node) { //node是左子節(jié)點，下面else與這里的剛好相反other = parent.right; //node的兄弟節(jié)點if(isRed(other)) { //case1: node的兄弟節(jié)點other是紅色的setBlack(other);setRed(parent);leftRotate(parent);other = parent.right;}//case2: node的兄弟節(jié)點other是黑色的，且other的兩個子節(jié)點也都是黑色的if((other.left == null || isBlack(other.left)) &&?(other.right == null || isBlack(other.right))) {setRed(other);node = parent;parent = parentOf(node);} else {//case3: node的兄弟節(jié)點other是黑色的，且other的左子節(jié)點是紅色，右子節(jié)點是黑色if(other.right == null || isBlack(other.right)) {setBlack(other.left);setRed(other);rightRotate(other);other = parent.right;}//case4: node的兄弟節(jié)點other是黑色的，且other的右子節(jié)點是紅色，左子節(jié)點任意顏色setColor(other, colorOf(parent));setBlack(parent);setBlack(other.right);leftRotate(parent);node = this.root;break;}} else { //與上面的對稱other = parent.left;if (isRed(other)) {// Case 1: node的兄弟other是紅色的 ?setBlack(other);setRed(parent);rightRotate(parent);other = parent.left;}if ((other.left==null || isBlack(other.left)) &&(other.right==null || isBlack(other.right))) {// Case 2: node的兄弟other是黑色，且other的倆個子節(jié)點都是黑色的 ?setRed(other);node = parent;parent = parentOf(node);} else {if (other.left==null || isBlack(other.left)) {// Case 3: node的兄弟other是黑色的，并且other的左子節(jié)點是紅色，右子節(jié)點為黑色。 ?setBlack(other.right);setRed(other);leftRotate(other);other = parent.left;}// Case 4: node的兄弟other是黑色的；并且other的左子節(jié)點是紅色的，右子節(jié)點任意顏色setColor(other, colorOf(parent));setBlack(parent);setBlack(other.left);rightRotate(parent);node = this.root;break;}}}if (node!=null)setBlack(node);}/****************** 銷毀紅黑樹 *********************/public void clear() {destroy(root);root = null;}private void destroy(RBNode<T> tree) {if(tree == null)?return;if(tree.left != null)?destroy(tree.left);if(tree.right != null)?destroy(tree.right);tree = null;}/******************* 打印紅黑樹 *********************/public void print() {if(root != null) {print(root, root.key, 0);}}/** key---節(jié)點的鍵值* direction--- 0:表示該節(jié)點是根節(jié)點* ? ? ? ? ? ? ?1:表示該節(jié)點是它的父節(jié)點的左子節(jié)點* ? ? ? ? ? ? ?2:表示該節(jié)點是它的父節(jié)點的右子節(jié)點*/private void print(RBNode<T> tree, T key, int direction) {if(tree != null) {if(0 == direction)?System.out.printf("%2d(B) is root\n", tree.key);elseSystem.out.printf("%2d(%s) is %2d's %6s child\n",?tree.key, isRed(tree)?"R":"b", key, direction == 1?"right":"left");print(tree.left, tree.key, -1);print(tree.right, tree.key, 1);}} }

?????? 下面附上測試程序吧：

?

?

package test;import tree.RBTree;public class RBTreeTest {private static final int a[] = {10, 40, 30, 60, 90, 70, 20, 50, 80};private static final boolean mDebugInsert = true; ? ?// "插入"動作的檢測開關(guān)(false，關(guān)閉；true，打開)private static final boolean mDebugDelete = true; ? ?// "刪除"動作的檢測開關(guān)(false，關(guān)閉；true，打開)public static void main(String[] args) {int i, ilen = a.length;RBTree<Integer> tree = new RBTree<Integer>();System.out.printf("== 原始數(shù)據(jù): ");for(i=0; i<ilen; i++)System.out.printf("%d ", a[i]);System.out.printf("\n");for(i=0; i<ilen; i++) {tree.insert(a[i]);// 設(shè)置mDebugInsert=true,測試"添加函數(shù)"if (mDebugInsert) {System.out.printf("== 添加節(jié)點: %d\n", a[i]);System.out.printf("== 樹的詳細信息: \n");tree.print();System.out.printf("\n");}}System.out.printf("== 前序遍歷: ");tree.preOrder();System.out.printf("\n== 中序遍歷: ");tree.inOrder();System.out.printf("\n== 后序遍歷: ");tree.postOrder();System.out.printf("\n");System.out.printf("== 最小值: %s\n", tree.minValue());System.out.printf("== 最大值: %s\n", tree.maxValue());System.out.printf("== 樹的詳細信息: \n");tree.print();System.out.printf("\n");// 設(shè)置mDebugDelete=true,測試"刪除函數(shù)"if (mDebugDelete) {for(i=0; i<ilen; i++){tree.remove(a[i]);System.out.printf("== 刪除節(jié)點: %d\n", a[i]);System.out.printf("== 樹的詳細信息: \n");tree.print();System.out.printf("\n");}}}}

?

5.紅-黑樹的復(fù)雜度

????????前面也說了，當數(shù)據(jù)以升序或降序插入時，二叉搜索樹的性能就會下降到最低，但是紅-黑樹的自我修復(fù)功能保證了即使在最壞的情況下，也能保證時間復(fù)雜度在O(logN)的級別上。

??????? 至此，紅-黑樹的所有內(nèi)容基本上討論完了，如有錯誤之處，歡迎留言指正~

?

? ? ? ??【正在看本人博客的這位童鞋，我看你氣度不凡，談吐間隱隱有王者之氣，日后必有一番作為！下面有個“頂”字，你就順手把它點了吧~相的準，我分文不收；相不準，你也好回來找我~嘎嘎嘎】

?

?

_____________________________________________________________________________________________________________________________________________________

-----樂于分享，共同進步！

-----本文動態(tài)圖出自：http://www.cnblogs.com/yangecnu/p/Introduce-Red-Black-Tree.html

-----本文部分參考于博客專家July的這篇文章：http://blog.csdn.net/v_july_v/article/details/6105630

-----更多文章請看：http://blog.csdn.net/eson_15

轉(zhuǎn)載于:https://my.oschina.net/u/3425573/blog/3008174

總結(jié)

以上是生活随笔為你收集整理的【数据结构和算法05】 红-黑树（转发）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。