昨天已經寫了一個二叉樹，不過那個是一個非平衡二叉樹，對于插入亂序的數據那是有一定的優勢的，不過當插入的數據都是有序的（順序或者是逆序）那執行的效果就不怎么好了。那有沒有辦法去解決這個問題，有，那就是今天要講得紅黑樹，也就是平衡二叉樹。
當插入（或者刪除）一個新節點時，必須要遵循的一定規則，下面介紹一下這些規則：
每個節點不是紅色的就是黑色的。根節點總是黑色的。如果節點時紅色的，則它的子節點必須是黑色的（反之倒不一定必須為真）從根倒葉節點或空節點的每條路徑，必須包含相同數量的黑色節點。了解了上面的規則，現在我們就開始去寫代碼吧。(由于之前沒有學好紅黑樹哪些規則，所以后面的刪除我就省略了，下一次博客在寫紅黑樹的刪除，今天就寫紅黑樹的添加元素)
/** * 節點樹的接口 * @author chenjingbin * * @param <E> 可以比較的類 */public interface Tree<E extends Comparable<E>> { /** * 查找是否有這個元素 * @param e * @return */ boolean search(E e); /** * 插入一個元素 * @param e * @return */ boolean insert(E e); /** * 刪除一個元素 * @param e * @return */ boolean delete(E e); /** *中序遍歷 */ void inorder(); /** * 前序遍歷 */ void PReorder(); /** * 后序遍歷 */ void postorder(); /** * 有多少個節點 * @return */ int getSize(); /** * 判斷是否為空 * @return */ boolean isEmpty(); /** * 清空樹 * @return */ boolean clear();}//拿上一次定義好的接口去使用那就可以了/** * 紅黑樹RABTree * @author chenjingbin *紅黑樹是平衡二叉樹，比較復雜的操作那就是在插入和刪除，會使用到左旋轉和右旋轉 * @param <E> */public class RABTree<E extends Comparable<E>> implements Tree<E> { public static final boolean RED = false; public static final boolean BLACK = true; public RABNode<E> root; public int size ; @Override public boolean search(E e) { // TODO Auto-generated method stub RABNode<E> current = root; while (current != null) { if(e.compareTo(current.element)<0) current = current.left; else if(e.compareTo(current.element)>0){ current = current.right; }else { return true; } } return false; } @Override public boolean insert(E e) { // TODO Auto-generated method stu RABNode<E> t=root; if(t==null){ root = new RABNode<E>(e, null); size++; return true; }else { RABNode<E> parent = null; RABNode<E> current = root; while(current !=null){ if(e.compareTo(current.element)<0){ parent = current; current = current.left; }else if(e.compareTo(current.element)>0){ parent = current; current = current.right; }else //這里面相同的元素那就不用插入，直接返回false return false; } RABNode<E> node = new RABNode<E>(e, parent); if(e.compareTo(parent.element)<0) parent.left = node; else parent.right =node; //上面的代碼和昨天的一樣，不一樣的地方是后面這個函數，因為插入一個節點那就需要去修改使得這棵樹平衡 fixAfterInsertion(node); size++; return true; } } /** * case1:當前節點的父結點是紅色，且當前 節點的祖父節點的另一個子節點（叔叔節點）也是紅色 * 處理策略：（1）將父結點設為黑色（2）將叔叔節點設置為黑色（3）將祖父節點設置為紅色（4）將祖父節點設置為“當前節點”（紅色節點）：即，之后繼續對當前節點進行操作。 * case2：當前節點的父節點是紅色，叔叔節點是黑色，且當前節點是其父節點的右孩子 * 處理策略：（1）將父結點作為新的當前節點（2）以新的當前節點為支點進行左旋轉 * case3：當前節點的父結點是紅色，叔叔節點是黑色，且當前節點是其父結點的左孩子 * 處理策略：（1）將父結點設置為黑色（2）將祖父節點設置為紅色（3）以祖父節點為支點進行右旋轉 */ private void fixAfterInsertion(RABNode<E> x){ x.color = RED ; while(x!= null && x!=root &&x.parent.color ==RED){ if(parentOf(x) == leftOf(parentOf(parentOf(x)))){ RABNode<E> 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{ RABNode<E> 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 ; } @Override public boolean delete(E e) { // TODO Auto-generated method stub /** * 第一步：將紅黑樹當做一顆二叉查找樹，將節點刪除 * 這里面有三種情況：1被刪除節點沒有孩子，即為葉子節點，那么直接刪除 * 2被刪除節點只有一個兒子，那么，直接刪除該節點，并用該節點的唯一子節點去替換他的位置 * 3被刪除節點有兩個孩子，那么先找出他的后繼節點，然后把后繼節點的內容復制給該節點的內容 * 第二步：通過旋轉和重新著色等一系列來修正該樹，使之重新成為一顆紅黑樹 */ //沒有寫完，后面再寫 return false; } //這個方法是拿到比t大一點的節點方法 private RABNode<E> successor(RABNode<E> t){ if(t== null){ return null; }else if(t.right!=null){ //說明t的右邊有節點 RABNode<E> p = t.right; while(p.left!=null){ p= p.left; } return p; }else{ RABNode<E> p = t.parent; RABNode<E> ch=t; while(p!=null&&p.left==ch){ ch = p; p=p.parent; } return p; } } /** * case1:x是黑+黑節點，x 的兄弟節點是紅色（此時x的父結點和x的兄弟節點的子節點都是黑色） * 處理策略： *1將x的兄弟節點設置為黑色2將x的父結點設置為紅色3對x的父結點進行左旋轉4左旋轉后，重新設置x的兄弟節點 *case2：x是黑+黑節點，x的兄弟節點是黑色，x的兄弟節點的兩個孩子都是黑色。 *處理策略：1將x的兄弟節點設置為紅色2設置x的父結點為新的x節點 *case3:x是黑+黑節點，x的兄弟節點是黑色，x的兄弟節點的左孩子是紅色，右孩子是黑色 *處理策略：1將x兄弟節點的左孩子設置為黑色，2將x的兄弟節點設置為紅色3對x的兄弟節點進行右旋轉4右旋后重新設置x的兄弟節點 *case4：x是黑+黑節點，x的兄弟節點是黑色，x的兄弟節點的右孩子是紅色的，x的兄弟節點的左孩子任意顏色 *處理策略：1將x的父結點顏色賦值給x的兄弟節點2將x父結點設置為黑色3將x兄弟節點的右子節點設置為黑色4對x的父結點進行左旋轉5設置x為根節點 */ private void fixAfterDeletion(RABNode<E> p){ //沒有寫完，后面再寫 } @Override public void inorder() { // TODO Auto-generated method stub inorder(root); } private void inorder(RABNode<E> root) { // TODO Auto-generated method stub if(root== null)return; else{ inorder(root.left); System.out.println(root.element+""); inorder(root.right); } } @Override public void preorder() { // TODO Auto-generated method stub preorder(root); } private void preorder(RABNode<E> root) { // TODO Auto-generated method stub if(root== null)return; else{ System.out.println(root.element+""); inorder(root.left); inorder(root.right); } } @Override public void postorder() { // TODO Auto-generated method stub postorder(root); } private void postorder(RABNode<E> root2) { // TODO Auto-generated method stub if(root== null)return; else{ inorder(root.left); inorder(root.right); System.out.println(root.element+""); } } @Override public int getSize() { // TODO Auto-generated method stub return size; } @Override public boolean isEmpty() { // TODO Auto-generated method stub return size == 0; } @Override public boolean clear() { // TODO Auto-generated method stub size = 0; root = null; return true; } /** * 根據e去得到節點 * @param e * @return */ public RABNode<E> getNode(E e){ RABNode<E> current = root; while (current != null) { if(e.compareTo(current.element)<0) current = current.left; else if(e.compareTo(current.element)>0){ current = current.right; }else { return current; } } return null; } //向下執行的時候會執行顏色變換，也就是黑色節點有兩個紅色節點時需要執行顏色變換。 /** * 得到顏色 * @param p * @return */ private boolean colorOf(RABNode<E> p){ return p==null?BLACK:p.color; } /** * 獲取父結點 * @param p * @return */ private RABNode<E> parentOf(RABNode<E> p){ return p==null?null:p.parent; } /** * 獲得左節點 * @param p * @return */ private RABNode<E> leftOf(RABNode<E> p){ return p==null?null:p.left; } /** * 獲得右節點 * @param p * @return */ private RABNode<E> rightOf(RABNode<E> p){ return p==null?null:p.right; } /** * 設置顏色 * @param p * @param c */ private void setColor(RABNode<E> p ,boolean c){ if(p!=null) p.color = c; } /** * 左旋轉 * @param p */ private void rotateLeft( RABNode<E> p){ if( p != null ){ RABNode<E> 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 ; } } /** * 右旋轉 * @param p */ private void rotateRight(RABNode<E> p){ if( p != null){ RABNode<E> 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 .left ==p) p.parent .left = l ; else p.parent .right = l; l.right = p; p.parent = l; } } /** * 定義紅黑樹節點類 * @author chenjingbin * * @param <E> */ static class RABNode<E extends Comparable<E>>{ E element; RABNode<E> right = null; RABNode<E> left = null; RABNode<E> parent; boolean color = BLACK; public RABNode(E e,RABNode<E> parent){ element = e; this.parent =parent; } }}上面的代碼，刪除部分沒有寫，因為還有點搞不懂，那過幾天才去寫，后面一定會補上刪除代碼的部分。在插入節點之前那是跟二叉查找樹一樣的，不同的是在插入之后需要去修改紅黑樹的平衡。下面是介紹如何去處理插入后的修護問題
case1:當前節點的父結點是紅色，且當前 節點的祖父節點的另一個子節點（叔叔節點）也是紅色 處理策略：（1）將父結點設為黑色（2）將叔叔節點設置為黑色（3）將祖父節點設置為紅色（4）將祖父節點設置為“當前節點”（紅色節點）：即，之后繼續對當前節點進行操作。
case2：當前節點的父節點是紅色，叔叔節點是黑色，且當前節點是其父節點的右孩子 處理策略：（1）將父結點作為新的當前節點（2）以新的當前節點為支點進行左旋轉
case3：當前節點的父結點是紅色，叔叔節點是黑色，且當前節點是其父結點的左孩子 處理策略：（1）將父結點設置為黑色（2）將祖父節點設置為紅色（3）以祖父節點為支點進行右旋轉
再上面的代碼中還有比較經典的函數，那就是左旋轉和右旋轉。因為那比較常用到。大家可以好好體會的。
新聞熱點
疑難解答
