老搞不清左旋右旋是往哪邊轉,索性寫成哪個方向的子節點上浮
/** * * 總結:紅黑樹的難點在于插入和刪除后的對于樹規則的修復, * 在新增時主要采取的策略是上浮插入的紅色節點,當遇到cpg連成一條線 并且 cp為紅色的情況 我們可以交換 pg 顏色上浮 p,因為上浮的顏色是r 并不會破壞樹的結構 * 在刪除時主要才去的策略是讓 要么可以涂紅b的黑色讓問題移到p上,要么將p的右側想辦法弄成r 以至于我們交換黑色的b和紅色的p之后填充了另一側的黑色,然后將原來 * 右側的子節點涂黑,不讓右側的節點數發生變化 * 注意點:紅黑樹要么單支黑p紅c,要么有兩個子節點 * * *@author Zhouk*@date 2017年3月7日 下午3:40:23*@describtion BRTree**/public class BRTree<T> { PRivate Node<T> root; public void insert(int index ,T value){ if(root==null){ root = new Node<T>(index, value, false); }else{ insertByStep(root,index,value); } } private Node<T> insertByStep(Node<T> currentParent,int index,T value){ if(index>currentParent.index){ Node<T> rightChild=currentParent.rightChild; if(rightChild==null){ Node<T> insertNode=new Node<T>(index, value,true); insertNode.parent=currentParent; currentParent.rightChild=insertNode; //對于新增節點需要進行 fixed操作 fixedAfterInsert(insertNode); return insertNode; }else if(rightChild.index==index){ rightChild.value=value; return rightChild; }else{ return insertByStep(rightChild, index, value); } }else{ Node<T> leftChild=currentParent.leftChild; if(leftChild==null){ Node<T> insertNode=new Node<T>(index, value,true); insertNode.parent=currentParent; currentParent.leftChild=insertNode; //對于新增節點需要進行 fixed操作 fixedAfterInsert(insertNode); return insertNode; }else if(leftChild.index==index){ leftChild.value=value; return leftChild; }else{ return insertByStep(leftChild, index, value); } } } /** * 添加核心思想是將紅色 節點上浮 * 但是 在 * b b * r:p b => r:c b * b r:c r:p * b * 或者 * b b * b r:p => b r:c * r:c b r:p * b * * 這兩種 情況 下 結果中的是 r:p 不符合 要求 但是出現了 紅色節點下沉的情況 需要特殊處理 * 我們需要將 r:c 涂黑 結果是 r:c 下 黑 多出一個 * 于是 我們將 root的b 涂紅 結果 是 root 另外一個分支 少了一個黑 * 我們將 現在是 黑的 r:c 上浮 解決問題 * 要注意的是 * 那么 要滿足的條件就是 之前的root 節點 接手的那個 節點 必然需要時黑色 * 不然 root已經被涂紅 下移 那么 會出現 兩個 假如 r:c 交給他的節點是紅色就會出現錯誤 * 在r:c 是root 左支 時候 交給 root的 是r:c 的rightChild * 在r:c 是root 右支時交給 root的的是 r:c的 leftChild * 總結如下: * //p:parent g:grandfatehr c:child u:uncle * * 1:u:b p:r為g:b左支 c:r為p:r左支: 涂黑 p 涂紅g 上浮 p=>complete * 2:u:b p:r為g:b左支 c:r為p:r右支: 上浮c p 為 新的 c 轉到 情況1 * 3:u:b p:r為g:b右支 c:r為p:r左支: 上浮 c p 為新的c 轉到情況4 * 4:u:b p:r為g:b右支 c:r為p:r右支 涂黑 p 涂紅 g 上浮p =>complete * * * 剩余情況 就是p:r u:r(p必然是r ,如果為 b 那么 已經結束) * 那么 涂黑 p 和 u 涂紅 g g為新的 c 可能不滿足情況 * @param currentNode */ private void fixedAfterInsert(Node<T> currentNode){ //如果當前節點是root節點 那么 無論什么顏色直接涂黑 if(currentNode.parent==null){ currentNode.color=false; } //如果插入節點的父節點 的顏色為黑 那么 什么也不做 返回 if(!currentNode.parent.color){ return; } //如果 父節點 為紅色 此時必然有祖父節點 else{ //如果叔父節點為 黑色 Node<T> uncleNode=getParentAnotherChild(currentNode.parent); if(uncleNode==null||!uncleNode.color){ //判斷 位置 Node<T> parent=currentNode.parent; Node<T> grandParent=parent.parent; if(grandParent.index>parent.index){ //情況1 if(parent.index>currentNode.index){ grandParent.color=true; parent.color=false; leftChildFloat(parent); } //情況2 else{ rightChildFloat(currentNode); fixedAfterInsert(currentNode.leftChild); } }else{ //情況3 if(parent.index>currentNode.index){ leftChildFloat(currentNode); fixedAfterInsert(currentNode.rightChild); } //情況4 else{ grandParent.color=true; parent.color=false; rightChildFloat(parent); } } } //如果叔父節點為紅色 else{ //將 父親節點 和叔父節點顏色涂黑 祖父節點涂紅 重新開始 fixed操作 uncleNode.color=false; currentNode.parent.color=false; currentNode.parent.color=true; fixedAfterInsert(currentNode.parent.parent); } } } public boolean remove(int i){ Node<T> removeNode=find(i); if(removeNode==null)return false; //假如刪除的不是葉子節點 需要進行fixed操作 deleteAndFixed(removeNode); return true; } /** * @param removeNode 待刪除的節點 * 定義待刪除節點 為 r 定義 右側最小節點的 s * s 可能存在 右支但是 不可能有左支 * 我們交換s和r 的 index 和 value * 現在假如 s為紅色 那么并 不影響平衡 * 但如果 s 為 黑色 那么 原來 s 位置 現在 r 位置就少了一個黑色 * 我們需要讓 現在 r的右側移動一個黑色過來 再刪掉r * 如果 r的兄弟節點 b 為紅色 直接上浮 b ,b 和p(父節點)交換顏色, * * * 交換顏色 上浮的實質: * * 因為 g 節點會移動到另一側 但是顏色是p的顏色 * * 假如p是b,g是r 那么 移動后 g移動過的一側多了原來p的顏色b(用于刪除時填充b) * 而現在 原來p這一側的root變成了 r 少了個b (原來c未移動的子節點為紅色 ,我們可以直接涂黑 達到平衡) * //這就需要 假如左節點上浮 需要 孩子的左孩子為 紅色 * 假如 右節點上浮 需要孩子的右孩子為紅色 * (刪除時僅僅存在這種情況 ,被刪除的是右側最小節點,都是左邊少) * 假如p是r,g是b 那么 移動后 g移動過的一側多了 r (無所謂) * 而現在 原來p這一側的root變成b 也無所謂 * //所以假如在p是r g是b的情況下 我們可以隨意交換移動 * (就像新增時調整一樣,可以用來調整連續r的問題) * * * 解決一側少一個黑的方法 * 0:假如兄弟節點為紅 那么 上浮兄弟節點交換 b和p的顏色 那么原來兄弟節點的子節點 * (紅色的子節點 ,必為黑) * 變成現在的兄弟節點 進入其余b為黑的情況 * 1:假如b 為黑 那么 我需要將當前b的右孩子變成紅色 * 1.1假如左右還是都是黑色 那么 涂紅b p為新的c * 1.2假如左側是紅色 右側是黑色 那么把左側的紅色移動到右側 (交換b和其左側的黑色 然后上浮左側子節點) * 左側子節點 為新的b 其右側為原來的b顏色為原來左側的顏色r 轉入1.3 * 1.3假如左側是右側是紅色 那么 那么我們可以交換p和g顏色 上浮p 涂黑右側子節點 達到平衡 * * * 刪除存在的特殊情況: * 刪除的是root節點 直接刪了 * 要么是單支黑p紅c直接將g的child指向c c的parent指向g * 假如刪除的是葉子節點 直接進入fix操作 */ private void deleteAndFixed(Node<T> removeNode){ //假如是根節點 if(removeNode.parent==null){ root=null; return; } //葉子節點的情況 if(removeNode.leftChild==null&&removeNode.rightChild==null){ fixedAfterDelete(removeNode); if(removeNode.index<removeNode.parent.index){ removeNode.parent.leftChild=null; }else{ removeNode.parent.rightChild=null; } } //黑色紅單支的情況 else if(removeNode.rightChild==null){ Node<T> parent=removeNode.parent; Node<T> leftChild=removeNode.leftChild; if(parent.index>removeNode.index){ parent.leftChild=leftChild; leftChild.parent=parent; leftChild.color=false; }else{ parent.rightChild=leftChild; leftChild.parent=parent; leftChild.color=false; } }else if(removeNode.leftChild==null){ Node<T> parent=removeNode.parent; Node<T> rightChild=removeNode.rightChild; if(parent.index>removeNode.index){ parent.leftChild=rightChild; rightChild.parent=parent; rightChild.color=false; }else{ parent.rightChild=rightChild; rightChild.parent=parent; rightChild.color=false; } } //雙子節點的情況 else{ Node<T> finalRemoveNode=removeNode.rightChild; while(finalRemoveNode.leftChild!=null){ finalRemoveNode=finalRemoveNode.leftChild; } //如果是紅色 不做操作 if (finalRemoveNode.color) { return; }else{ removeNode.value=finalRemoveNode.value; removeNode.index=finalRemoveNode.index; fixedAfterDelete(finalRemoveNode); } if(finalRemoveNode.index<finalRemoveNode.parent.index){ finalRemoveNode.parent.leftChild=null; }else{ finalRemoveNode.parent.rightChild=null; } } } private void fixedAfterDelete(Node<T> finalRemoveNode){ //如果兄弟節點為黑色 注意 兄弟節點不可能為null 為null時當前節點必為紅色 Node<T> brother=getParentAnotherChild(finalRemoveNode); //如果brother為紅色 if(brother.color){ brother.color=false; brother.parent.color=true; rightChildFloat(brother); //任然處理當前節點 fixedAfterDelete(finalRemoveNode); }else{ //子節點全黑 if(!isRed(brother.leftChild)&&!(isRed(brother.rightChild))){ //brother 涂紅 brother.color=true; fixedAfterDelete(brother.parent); }else if(isRed(brother.leftChild)){ brother.leftChild.color=false; brother.color=true; leftChildFloat(brother.leftChild); }else{ brother.color=false; brother.parent.color=true; rightChildFloat(brother); brother.leftChild.color=false; } } } private boolean isRed(Node<T> node){ return node!=null&&node.color; } public Node<T> find(int i){ if(root==null)return null; return findByStep(root,i); } public Node<T> findByStep(Node<T> currentParent,int i){ if(currentParent.index>i){ Node<T> leftChild=currentParent.leftChild; if(leftChild==null)return null; if(leftChild.index==i)return leftChild; return findByStep(leftChild,i); }else{ Node<T> rightChild=currentParent.rightChild; if(rightChild==null)return null; if(rightChild.index==i)return rightChild; return findByStep(rightChild,i); } } /** * 返回兄弟節點 * @param currentNode * @return */ private Node<T> getParentAnotherChild(Node<T> currentNode){ if(currentNode==null||currentNode.parent==null){ return null; } if(currentNode.index<currentNode.parent.index){ return currentNode.parent.rightChild; }else{ return currentNode.parent.leftChild; } } /** * 左側孩子 上浮 * @param itemNode 孩子節點 */ private void leftChildFloat(Node<T> itemNode){ Node<T> parent=itemNode.parent; Node<T> grandParent=parent.parent; Node<T> right=itemNode.rightChild; parent.parent=itemNode; itemNode.rightChild=parent; parent.leftChild=right; if(right!=null){ right.parent=parent; } itemNode.parent=grandParent; if(grandParent!=null){ if(grandParent.index>itemNode.index){ grandParent.leftChild=itemNode; }else{ grandParent.rightChild=itemNode; } } } /** * 右側孩子上浮 * @param itemNode 孩子節點 */ private void rightChildFloat(Node<T> itemNode){ Node<T> parent=itemNode.parent; Node<T> grandParent=parent.parent; Node<T> left=itemNode.leftChild; parent.parent=itemNode; itemNode.leftChild=parent; parent.rightChild=left; if(left!=null){ left.parent=parent; } itemNode.parent=grandParent; if(grandParent!=null){ if(grandParent.index>itemNode.index){ grandParent.leftChild=itemNode; }else{ grandParent.rightChild=itemNode; } } } public static class Node<T>{ int index; T value; Node<T> parent; Node<T> leftChild; Node<T> rightChild; /** * red:true,black:false */ boolean color; public Node(int index, T value, boolean color) { super(); this.index = index; this.value = value; this.color = color; } }}新聞熱點
疑難解答
