基于234樹手撕TreeMap紅黑樹原始碼（3萬字長文帶你走進紅黑深處的細節）-有解無憂

紅黑樹

- 紅黑樹優勢到底在哪
- 紅黑樹和234樹的映射關系
- - 什么是234B
  - 234節點的對應
  - 234樹的生長
  - 234樹的洗掉
  - 映射關系
  - 轉化Test
- 紅黑樹性質
- 節點類和基本方法
- 紅黑樹的左右旋
- - 左旋圖1
  - 左旋圖2
  - 左旋代碼
  - 右旋圖
  - 右旋代碼
- 新增節點
- - AVL樹方法搜索位置
  - 紅黑插入的情況圖解（以左為例）
  - 紅黑插入的情況圖流程圖
  - 代碼詳解
  - 新增代碼整合（put）
- 洗掉節點
- - 尋找該節點（getNode）
  - 洗掉定位節點（deleteNode）
  - - 洗掉節點情況分析
    - 代碼分解
    - - 情況三
      - replace的分析和確定
      - if處理情況二
      - else處理情況一
    - 代碼deleteNode整合
  - 洗掉后的平衡調整（fixAfterRemove）
  - - 兄弟為黑色有紅子節點情況1---3
    - (假)兄弟為紅色情況 4
    - 兄弟為黑色且無紅節點情況5
    - - 七個思考：
      - 代碼
    - 思考：父節點紅且兄弟無紅色子節點
    - - 思路
      - 圖解
    - fixAfterRemove流程圖
    - 整合調整的代碼（fixAfterRemove）
  - 三種方法整合（remove）
  - 洗掉代碼整合
- 完整代碼和測驗
- - RBTreeTest
  - TreeOperation
  - RBTree

紅黑樹測驗連接
234樹測驗鏈接

紅黑樹優勢到底在哪

紅黑樹的查詢性能略微遜色于AVL樹，因為紅黑樹比AVL樹會稍微不平衡，造成多出一層來，也就是說紅黑樹的查詢性能只比相同內容的avl樹最多多出一次的比較，但是：紅黑樹在插入和洗掉上基本可以完虐AVL樹,AVL樹每次插入洗掉會進行大量的平衡度計算，而對于紅黑樹依照維持紅黑性質所做的紅黑變換和旋轉操作所需要的開銷相較于AVL樹要小得多，紅黑樹最多使用三次旋轉能完成所有的添加和洗掉操作，

紅黑樹和234樹的映射關系

什么是234B

234樹特點：

嚴格的平衡樹
在每個節點上沒有子節點或者有且僅有與之對應的子節點數量
每一個葉子節點對應的樹的層數是一定的
遵循向上生長的原則

234節點的對應

每一個藍色底盤就是一個234樹的一個節點，每個節點中的每個橙色就是一個節點中的元素，在填充234樹時要么沒有子節點要么將節點中的每個黑色線均填充子節點，否則就不滿足B樹平衡.
在這里插入圖片描述

234樹的生長

添加元素時會進行查找到合適的位置，放在適合的節點
若加上該元素后該節點中有了四個元素（5節點式），就要將原來的節點中三個元素中間的元素作為父節點上提，并將對于原節點左右元素分別作為父節點左右子節點
對于上提的父節點與原節點父節點元素結合，若結合后是四個元素，重復步驟 2

234樹的洗掉

若在節點中洗掉指定元素并不改變樹的結構會直接洗掉，后不做其他操作（下圖第一步）
若洗掉指定節點后會影響節點平衡就會向與之最近的多余節點的節點借，但并非直接借，而是通過父節點間接借
若在整個樹中沒有可以借的節點就會通過降低層數的方式維持輸的平衡

映射關系

在這里插入圖片描述

一個紅黑樹只對應一個234樹，一個234樹可能對應多個紅黑樹，
紅黑樹的紅色節點不可能連續
一個234樹中的節點對應到紅黑樹上只有一個黑色節點，因此在紅黑樹的任意節點到該節點的葉子節點路徑上黑色節點個數一定是一樣的

轉化Test

這是一個帶顏色的234樹：
在這里插入圖片描述
轉化為紅黑為：（標號為該路徑上有幾個黑色節點）

紅黑樹性質

節點為紅色和黑色
根節點為黑色

這兩條可理解為紅黑樹定義

所有葉子均為黑色

對這一條可能有些疑問，實際上在處理紅黑樹的的節點時，若該節點為葉子節點，就會在后邊填補倆個黑色空節點，在上述舉例時只不過被省略了，

在這里插入圖片描述

左右紅色節點下均有兩個黑色節點

第三條的介入時只成立

從任意節點到該節點所有的葉子節點的簡單路徑上的黑的節點個數一定（黑色平衡）

根據234樹的平衡，每個節點對應在紅黑樹的節點時有且只有一個黑色節點

節點類和基本方法

public class RBTree<K extends Comparable<K>,V>{
    private RBNode root;//先定義根節點
    private static final boolean BLACK=true;//黑色為真
    private static final boolean RED=false;//紅色為假

	//獲取節點顏色
	private static boolean getColor(RBNode rbNode){
        //空節點時為黑，因為最后層為黑
        //這樣可以避免在后續復雜處理時出現空指標
        return rbNode==null?BLACK:rbNode.color;
    }
    //設定節點顏色
    private static void setColor(RBNode rbNode, boolean b){
        if(rbNode!=null){
            rbNode.color=b;
        }
    }
    //獲取父節點
    private static RBNode parentOf(RBNode rbNode){
        return rbNode==null?null:rbNode.parent;
    }
    //獲取左子節點
    private static RBNode leftOf(RBNode rbNode){
        return rbNode==null?null:rbNode.left;
    }
    //獲取右子節點
    private static RBNode rightOf(RBNode rbNode){
        return rbNode==null?null:rbNode.right;
    }
    
	//節點類放在了RBTree類中當作了內部類
	//該類的泛型K鍵值（TreeMap中的鍵）繼承Comparable介面，用于后續比較
	static class RBNode<K extends Comparable<K>,V>{
	    K key;
	    V value;
	    private boolean color;
	    RBTree.RBNode parent;//父親節點
	    RBTree.RBNode left;//左節點
	    RBTree.RBNode right;//右節點
	
		//創建構造器
	    public RBNode(K key, V value, RBTree.RBNode parent) {
	        this.key = key;
	        this.value = value;
	        this.color = BLACK;
	        this.parent = parent;
	    }
	
		//可自己呼叫前序遍歷時顯示鍵值對的值
	    @Override
	    public String toString() {
	        return "RBNode{" +
	                "key=" + key +
	                ", value=" + value +
	                ", color=" + (color?"BLACK":"RED") +
	                '}';
	    }
	
		//一些 get  set 方法
	    public RBTree.RBNode getLeft() {
	        return left;
	    }
	    public RBTree.RBNode getRight() {
	        return right;
	    }
	    public boolean isColor() {
	        return color;
	    }
	    public V getValue() {
	        return value;
	    }
	}
}

關于為什么有這些私有方法，是因為在后續程序中不管是左右旋，還是節點顏色判斷將不會擔心空指標例外，

紅黑樹的左右旋

左旋圖1

在這里插入圖片描述

左旋圖2

p節點為以p節點進行左旋轉
藍色箭頭為該子樹的父節點
綠色節點為顏色位置的節點，可能為空

l為用來代替p的節點
將p顏色給l，并將p置為紅色
改變父節點指向，將l左子樹給p的右樹
將l的左指向p

結果：

注：每一次左右節點的交換都要改變父親父節點的指向，同時要注意父親節點的左還是右指向該孩子節點，上圖省略了

于是有了下面代碼：

左旋代碼

//以p節點為旋轉點
private  void leftRotate(RBNode p)  {
   if(p!=null){
       RBNode l=p.right;
       setColor(l, p.color);
       setColor(p, RED);
       p.right = l.left;
       //上句交換了指向，所以要修改父節點指向，方向已知
       if (l.left != null) {
           l.left.parent = p;
        }
        l.parent = p.parent;
        //上句交換了指向，所以要修改父節點指向，方向未知，所以要判斷方向
        if (p.parent == null) {//若無說明p節點為根節點，讓根節點指向l即可
            root = l;
        } else if (p.parent.left == p) {//若是父節點左
            p.parent.left = l;
        } else {//若是父節點右
            p.parent.right = l;
        }
        l.left = p;
        //處理父節點，且不可能為空
        p.parent = l;
    }
}

右旋圖

在這里插入圖片描述

右旋代碼

同理左旋，不在贅述

private void rightRotate(RBNode p)  {
    RBNode r = p.left;
    setColor(r, getColor(p));
    setColor(p, RED);
    p.left = r.right;
    if (r.right != null) {
        r.right.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.right = p;
    p.parent = r;
}

新增節點

AVL樹方法搜索位置

在RBTree類中創建put方法，先進行查找：

class RBTree<K extends Comparable<K>,V>{
    public void put(K key,V value){
        if(key==null){
            throw new RuntimeException("空指標例外");
        }
        //若root為空，說明第一個元素，那么直接對root修改
        if(null == root){
        	//顏色默認黑
            root=new RBNode<>(key,value==null?key:value,null);
            return;
        }
        //com記錄比較值，用于記錄插入節點的位置是父節點的方向左還是右
        int com;
        //記錄插入節點的父節點，因為插入節點不可能立即成為根結點（后續調整可能成為父節點），所以父節點必存在
        RBNode parentTail;
        //從根節點開始搜索，parentTail緊跟其后
        RBNode tail=root;
        do{
            //記錄父節點
            parentTail=tail;
            //將插入值和tail搜索的值及進行比較，用com記錄
            com=key.compareTo((K) tail.key);
            if(com<0){
                //向左搜索
                tail=leftOf(tail);
            }else if (com>0){
                //向右搜索
                tail=rightOf(tail);
            }else {
                //若相同就直接覆寫當前值，因為并未改變樹的平衡，并直接結束程式
                tail.value=value==null?key:value;
                return;
            }
        }while (tail!=null);//終止搜索條件
        //創建一個新節用于存盤進來的資料
        RBNode newRBNode=new RBNode<>(key,value==null?key:value,parentTail);
        //根據com大小進行父節點的左右賦值操作
        if (com<0){
            parentTail.left=newRBNode;
        }else {
            parentTail.right=newRBNode;
        }
    }
   fixAfterPut(newRBNode);
}

是不是以為這樣就完了？（怎么可能有一句代碼我還沒見過！！！）

在這里插入圖片描述
對，沒錯，還有fixAfterPut函式！！！

那我們就看看用AVL搜索后的結果可能出現的所有情況吧！

紅黑插入的情況圖解（以左為例）

根據插入節點對應在234樹上的情況有：

在這里插入圖片描述

添加的顏色要優先置為紅，防止直接對紅黑樹平衡造成影響
在父節點為黑色的時候，無需操作，
父親節點為紅時，就要判斷叔叔節點是否存在
- 叔叔節點不存在（第三種），判斷該節點是父親什么節點做一次或兩次旋轉
- 叔叔節點存在就轉換顏色（第四種），將爺爺節點作為新節點判斷進入回圈
根置黑

情況三的第二個：
在這里插入圖片描述
情況三的第三個：

在這里插入圖片描述
情況四的第一個：

情況四的第二個：

紅黑插入的情況圖流程圖

在這里插入圖片描述

代碼詳解

關于root空的這一種情況在查找前已經排除，

    private void fixAfterPut(RBNode newRBNode) {
    	//將新增節點置為紅色
        setColor(newRBNode,RED);
        //若新增節點的父節點為黑，直接退出
        //若沒有這個判斷也可，因為不會進入回圈，不過這樣好理解
        if(getColor(parentOf(newRBNode))==BLACK){
            return;
        }
        //新增節點不為根節點，且父節點為紅色
        //（父節點為紅色是作為出回圈條件，毫無影響第一次進回圈
        while (newRBNode != root&&getColor(parentOf(newRBNode))==RED){
        	//添加指向爺爺和父親的指標，便于理解
            RBNode grandFather=parentOf(parentOf(newRBNode));
            RBNode father=parentOf(newRBNode);
            
            //判斷父親是爺爺的左節點還是右節點，依次判斷叔叔在爺爺節點的左右
            if(leftOf(grandFather)==father){
            	//確定叔叔節點，可能為null
                RBNode uncle=rightOf(grandFather);
                
                //叔叔節點慷訓是紅
                //（不可能為黑，若黑那么之前的樹不平衡）
                if(getColor(uncle)==RED){
                	//撐死式換顏色
                    setColor(grandFather,RED);
                    setColor(uncle,BLACK);
                    setColor(father,BLACK);
                    //將爺爺換成新增節點，重新回圈
                    newRBNode=grandFather;
                }else {//叔叔節點空：
                	//是否需要進行左旋調整
                    if(rightOf(father)==newRBNode){
                        leftRotate(father);
                        //指向新節點位置
                        newRBNode=father;
                    }
                    
                    //根據爺爺節點右旋即可
                    //右旋后newRBNode節點的父親就是黑色了
                    //這里不需要手動變顏色，因為在旋轉時已經變過了，不過要小心驗證
                    rightRotate(grandFather);
                }
            }else {//跟上一段代碼雷同
                RBNode uncle=leftOf(grandFather);
                if(getColor(uncle)==RED){
                    setColor(grandFather,RED);
                    setColor(uncle,BLACK);
                    setColor(father,BLACK);
                    newRBNode=grandFather;
                }else {
                    if(leftOf(father)==newRBNode){
                        rightRotate(father);
                        newRBNode=father;
                    }
                    leftRotate(grandFather);
                }
            }
        }
        //將根節點置為黑，防止其他操作變成了紅色
        setColor(root,BLACK);
    }

新增代碼整合（put）

    public void put(K key,V value){
        if(null == root){
            root=new RBNode<>(key,value==null?key:value,null);
            return;
        }
        int com;
        RBNode tail=root;
        RBNode parentTail;
        if(key==null){
            throw new RuntimeException("空指標例外");
        }
        do{
            parentTail=tail;
            com=key.compareTo((K) tail.key);
            if(com<0){
                tail=leftOf(tail);
            }else if (com>0){
                tail=rightOf(tail);
            }else {
                tail.value=value==null?key:value;
                return;
            }
        }while (tail!=null);
        RBNode newRBNode=new RBNode<>(key,value==null?key:value,parentTail);
        if (com<0){
            parentTail.left=newRBNode;
        }else {
            parentTail.right=newRBNode;
        }

        fixAfterPut(newRBNode);
    }

    private void fixAfterPut(RBNode newRBNode) {
        setColor(newRBNode,RED);
        while (newRBNode != root&&getColor(parentOf(newRBNode))==RED){
            RBNode grandFather=parentOf(parentOf(newRBNode));
            RBNode father=parentOf(newRBNode);
            if(leftOf(grandFather)==father){
                RBNode uncle=rightOf(grandFather);
                //慷訓者黑色不進入
                if(getColor(uncle)==RED){
                    setColor(grandFather,RED);
                    setColor(uncle,BLACK);
                    setColor(father,BLACK);
                    newRBNode=grandFather;
                }else {
                    if(rightOf(father)==newRBNode){
                        leftRotate(father);
                        newRBNode=father;
                    }
                    rightRotate(grandFather);
                }
            }else {
                RBNode uncle=leftOf(grandFather);
                if(getColor(uncle)==RED){
                    setColor(grandFather,RED);
                    setColor(uncle,BLACK);
                    setColor(father,BLACK);
                    newRBNode=grandFather;
                }else {
                    if(leftOf(father)==newRBNode){
                        rightRotate(father);
                        newRBNode=father;
                    }
                    leftRotate(grandFather);
                }
            }
        }
        setColor(root,BLACK);
    }

洗掉節點

洗掉的步驟：

獲取對應的Key值的被洗掉節點（getNode）
確定洗掉節點后通過一個函式進行洗掉操作（deleteNode）
再創建一個函式用于洗掉后對紅黑樹的平衡調整（fixAfterRemove）
將上述的三種方法整合（remove）

尋找該節點（getNode）

尋找的方法并沒有對紅黑樹平衡有任何影響，所以可以看成AVL樹進行查詢，直接看代碼

    private RBNode getNode(K key){
        RBNode tail=root;//起始為根節點的指標用于后續的查找定方向
        if(root==null){
        	//root空就不可能有對應的值
            throw new RuntimeException("不可能空");
        }
        //查找的節點不為空就繼續向左右查找
        while (tail!=null){
        	//通過比較進行左右的位置確定
            int cmp=key.compareTo((K)tail.key);
            if(cmp<0){
            	//向左查找
                tail=leftOf(tail);
            }else if (cmp>0){
            	//向右查找
                tail=rightOf(tail);
            }else {
            	//說明查找到結果，就講該值回傳
                return tail;
            }
        }
        //出了回圈就意味著沒有該值，回傳空
        return  null;
    }

洗掉定位節點（deleteNode）

洗掉節點情況分析

注：node為洗掉節點，replace表示node洗掉后代替node的節點

情況一：洗掉節點無子節點

在這里插入圖片描述

情況二：洗掉節點有一個子節點
在這里插入圖片描述
情況三：洗掉節點有兩個子節點

注：情況一和情況二下洗掉節點node為紅時均不需要調整，只有是黑的才調整！！！

代碼分解

因為情況三最終都會通過前驅后后繼轉到情況一或情況二，所以我們只需要在進行情況一情況二前進行情況三的討論，

情況三

前驅節點

//node為需要被洗掉的節點，尋找它的前驅節點，
private RBNode pre(RBNode node){
	//由于比node小的在node的左邊，而這些值最大的在node左子樹的最右邊
	//由于node節點有兩個子節點，所以無需判斷node左是否為空
    RBNode l=leftOf(node);
    //向右找最大值
    while (l.right!=null){
       l=l.right;
    }
    return l;
}

后繼節點

private RBNode suc(RBNode node){
	//由于比node大的在node的右邊，而這些值最小的在node右子樹的最左邊
	//由于node節點有兩個子節點，所以無需判斷node右是否為空
    RBNode r=rightOf(node);
    while (r.left!=null){
        r=r.left;
    }
    return r;
}

情況三---->情況一二

if(leftOf(node)!=null&&rightOf(node)!=null){
     RBNode pre = pre(node);//這里使用前驅節點
     //進行賦值,因為pre在賦值node后就會作為新的node被洗掉，所以它的值不重要
     node.key=pre.key;
     node.value=pre.value;
     //后繼節點作為新的被洗掉節點
     node=pre;
}

replace的分析和確定

replace作為node洗掉后代替node的節點，該如何確定呢？

在node有節點時指向非空節點（情況二）
若無節點，就指向null（情況一）

寫法一

RBNode replace;
//當左空右不空，replace指向右（情況二）
if(leftOf(node)==null&&rightOf(node)!=null){
    replace=rightOf(node);
//當右空左不空，replace指向左（情況二）
}else if (leftOf(node)!=null&&rightOf(node)==null){
    replace=leftOf(node);
}else {//左右都空（情況一）
    replace=null;
}
/*
leftOf(node)!=null&&rightOf(node)！=null情況去哪了？
這種情況為情況三的，在前面已經轉換為了情況一或二所以不可能存在
*/

寫法二
寫法一的代碼寫成三目運算子是這樣的：

RBNode replace=leftOf(node)!=null?leftOf(node):rightOf(node);

if處理情況二

//現在只剩情況一和二，關于情況一和二的區別就是replace是否為null
if(replace!=null){//情況二進入

	//將node父節點（是否存在和左右不定，需要討論）的子節點指向replace
	//以達到洗掉node的效果
    replace.parent=parentOf(node);
    //當情況二下洗掉的節點node是根節點時（情況三不可能，因為轉換成洗掉前驅結點不可能為根節點）
    //此時根節點下只有一個紅色節點,replace為紅色節點
    //parentOf(node)為空，replace.parent也為null
    //所以要判斷node是否為根節點，即判斷parentOf(node)==null是否成立
    if(parentOf(node)==null){
    	//若是根節點yong紅色replace替換，在后來因為洗掉的node為黑會調整顏色
        root=replace;
    }else if(node==leftOf(parentOf(node))){//洗掉節點為父節點的左子節點
        node.parent.left=replace;
    }else {//洗掉節點為父節點的右子節點
        node.parent.right=replace;
    }
    //處理掉和洗掉節點node的所有指標關系
    node.left=node.right=node.parent= null;
    
    //??????????????????調整B??????????????????
    //情況二下的洗掉節點為黑色，包含了洗掉節點為根節點情況
    if(getColor(node)==BLACK){
        //replace!=null已判斷成立，那么該replace節點必為紅色
        //因為原來的node節點只有一個方向有子節點，這個子節點就是replace，為保持黑色平衡所以為紅
        //實際上這種情況只要一句話就可以了，不過為了模塊化放在了函式里
        //進入fixAfterRemove后因為replace必定為紅，所以進入不了fixAfterRemove中的回圈(fixAfterRemove函式在后面)
        fixAfterRemove(replace);

		/*
		如果進入fixAfterRemove處理也可以，只需要直接將replace變為黑色
		用下面這句話代替 fixAfterRemove
		setColor(replace,BLACK);
		?????????建議用setColor(replace,BLACK);這樣可以更好的理解
		*/
    }
}

else處理情況一

//進入else意味著需要洗掉的節點node無子結點，就是情況一
//由于無子節點，這里replace==null，僅僅提示一下，好像沒什么用
else {
	
	//??????????????????調整A??????????????????
	//紅色時無需調整只要進行子節點和父節點的指標調整就行
	//node黑色才進入調整
    if(getColor(node)==BLACK){
        fixAfterRemove(node);
    }
    
    //調整后對于子節點父節點指標調整
    //But你怎么知道他有父節點？所以要討論
    if(parentOf(node)!=null) {
        if (node == leftOf(parentOf(node))) {//洗掉節點右節點為后繼
            node.parent.left = null;
        } else {
            node.parent.right = null;
        }
        node.parent = null;
    }else {
    	//node沒有父節點就是根節點，并且無子節點
    	//說明要洗掉根節點，就要直接變空
        root=null;
    }
}

注：將上面的代碼按順序放在函式名為deleteNode里面就好了

代碼deleteNode整合

    private RBNode deleteNode(RBNode node) {
        if (leftOf(node) != null && rightOf(node) != null) {
            RBNode pre = pre(node);
            node.key = pre.key;
            node.value = pre.value;
            node = pre;
        }
        RBNode replace = leftOf(node) != null ? leftOf(node) : rightOf(node);
        if (replace != null) {
            replace.parent = parentOf(node);
            if (parentOf(node) == null) {
                root = replace;
            } else if (node == leftOf(parentOf(node))) {
                node.parent.left = replace;
            } else {
                node.parent.right = replace;
            }
            node.left = node.right = node.parent = null;
            if (getColor(node) == BLACK) {
                fixAfterRemove(replace);
            }
        }
        else {
            if (getColor(node) == BLACK) {
                fixAfterRemove(node);
            }
            if (parentOf(node) != null) {
                if (node == leftOf(parentOf(node))) {
                    node.parent.left = null;
                } else {
                    node.parent.right = null;
                }
                node.parent = null;
            } else {
                root = null;
            }
        }
        return null;
    }

洗掉后的平衡調整（fixAfterRemove）

hahahahahahahaha最難理解的紅黑調整，它來了！！！
在這里插入圖片描述

牢記：
1.洗掉節點為黑色，這里用黃色表示
2.這里只舉例洗掉節點為父節點左子節點的情況
3.我們的代碼在左 / 右旋的時候能改變顏色，將被繞著旋轉的節點顏色給右 / 左子節點后自己變成紅色

什么時候才需要調整？
答：洗掉節點為黑色，并且該黑節點無子節點

調整的根本目標是什么？
答：尋找能被移動的節點（紅色），變成黑色來彌補我們洗掉黑色節點的一側帶來的黑色不平衡問題，

兄弟為黑色有紅子節點情況1—3

這種黑色兄弟節點對應在234樹中為兄弟節點，
兄弟節點無子紅節點在最后討論
兄弟節點的子節點不可能是黑色，因為不平衡，
洗掉節點為4黑色，用黃色表示洗掉的節點

在這里插入圖片描述

問題：關于為什么父節點可以是紅色或黑色？
在進行左右旋的時候原來父節點的顏色會保留在旋轉后的父節點中，原來的父節點會變成紅色，所以不會影響整體黑色節點層數，

//因為假設的是洗掉節點為父節點的左，所以兄弟必為右
RBNode rBro=rightOf(parentOf(node));
//getColor(leftOf(rBro))==RED這句話在后來可以省略，因為我們在后來優先判斷兄弟節點左右均為黑
//借點空的時候默認回傳BLACK
if(getColor(rightOf(rBro))==BLACK&&getColor(leftOf(rBro))==RED){
	//左旋兄弟節點
    rightRotate(rBro);
    //將指標指向當前兄弟節點
    rBro=rightOf(parentOf(node));
}
//進行左旋
leftRotate(parentOf(node));
//平衡顏色
setColor(parentOf(node),BLACK);
setColor(rightOf(rBro),BLACK);

(假)兄弟為紅色情況 4

問：為什么不能讓兄弟為紅的節點轉到左邊變成黑色？
答：若兄弟為紅色，那么該紅色節點下必定是兩個黑色，如果該紅色直接走了，那么兩個黑色節點無法處理，所以要左旋變成兄弟為黑色，
為什么叫做假兄弟？
答: 該紅色節點在234樹中為父親的元素
在這里插入圖片描述

//判斷是否是真正的兄弟,RED顏色就是假的兄弟，該兄弟節點在234樹上為父親的
if(getColor(rBro)==RED){
	//繞父親節點左旋
    leftRotate(parentOf(node));
    //將指標調整為真兄弟
    rBro=rightOf(parentOf(node));
}

兄弟為黑色且無紅節點情況5

在聊該情況前我們有幾個思考：

七個思考：

思考一：什么時候存在兄弟為黑色且無紅節點這種情況？
答： (假)兄弟為紅色情況 4 旋轉之后，后者本來就存在，所以該判斷必定在 (假)兄弟為紅色情況 4之后

思考二：洗掉該黑色節點對對應的234樹有什么影響？
答：映射在234樹上就相當于洗掉了其中的一整個節點，造成了234樹不平衡，

思考三：234樹處理的大致思路是什么？
答：將洗掉節點路徑上增加一個節點（該節點值間接的來自兄弟節點中的元素）或者將整個樹減少一層，234樹中的節點對應著紅黑樹中黑色節點

思考四：若節點間接來自兄弟節點，那么就會將4節點變成3節點，3節點變成2節點，但是兄弟節點原來的子節點數量卻保持不變，不會使樹不遵守B樹原則嗎？
答：不會，我們在將兄弟節點的值間接變成洗掉樹節點的時候有一個子樹的父節點發生了變化（注意-76的父親節點），這在紅黑樹中對應著左右旋操作（并非一定是一次）
在這里插入圖片描述

思考五：那么增加節點的問題234樹自己怎么處理的？
答：尋找洗掉節點的兄弟節點，若兄弟節點大于1的元素，就會對這個兄弟元素（-756）操作，兄弟節點大于1在紅黑樹中對應著兄弟節點存在紅子節點

在這里插入圖片描述

思考六：如果最近的那個節點沒有多余元素呢？
答：將父親節點看成洗掉的節點回圈向上繼續尋找，但是程序中將只有一個元素的兄弟節點和父節點合并，若node到了根節點的子節點，判斷node兄弟節點（根節點另一個方向）是否有多余元素，若有就會在此時交換值并結束，但是如果仍然沒有，此時的兄弟節點就會和根節點結合作為根節點，這樣就減小了另一側整體的層數，也就是通過降低樹深度達到平衡的效果，

在這里插入圖片描述
思考七：思考六中關于234樹的操作反應在紅黑樹上是什么樣的？
答：在到跟節點之前，所有兄弟節點的左右子節點為黑色（真黑色或null）的兄弟節點都變成紅色（對應在234樹中的兄弟和父節點合并），直到找到兄弟節點的子節點存在紅色節點，然后根據兄弟為黑色有紅節點情況1—3

思考七圖解1：
目標：洗掉節點1（四十右邊的省略）
在這里插入圖片描述
思考七圖解2：
因為1的兄弟節點為5，5的左右子節點為空（即為黑色）不滿足轉化條件，將兄弟節點5變成紅色，指標指向上一個元素3，

思考七圖解3：
因為3的兄弟節點為8，8的左右子節點為黑色不滿足轉化條件，將兄弟節點8變成紅色，指標指向上一個元素6，
在這里插入圖片描述
思考七圖解4：
因為6的兄弟節點為29，29的左右子節點存在紅色，滿足轉化條件，根據 兄弟為黑色有紅色子節點情況 1—3，進行左旋后換顏色即可，

思考七圖解5：
進行左旋后的情況，

思考七圖解6：
換顏色（將旋轉節點左右子節點置為黑），完成，此時就符合黑色平衡
在這里插入圖片描述
續思考七：要是到達根節點時任然完不成呢？
答：該操作必定在根節點前平衡，別忘了我們變成平衡樹的方式有兩種：
一就是通過增加黑色節點（思考七的程序）
二是通過下降紅黑樹的黑色層數 （對應234樹的節點層數）

在根節點附近的情況有三種：
1：root根節點的另一個方向的子節點為紅色：
和 (假)兄弟為紅色情況 4情況相同
和思考七的程序相同，不過此時的父節點為根節點，在左右旋的時候
在這里插入圖片描述

2：root根節點的另一個方向的子節點為黑色且該黑色節點子節點存在紅色節點：
和 兄弟為黑色有紅子節點情況1—3情況相同
在這里插入圖片描述
3：root根節點的另一個方向的子節點為黑色且該黑色節點子節點不存在紅色節點：
這種情況走正常的程式是不滿足的情況，會將8置為紅，黃色指標繼續向上，指向根節點，此時會強制退出回圈，
強制退出它平衡了嗎？
答：平衡了，之前根節點7節點左邊少一個黑的，這時讓8變成紅，就在根節點7右邊減少了黑的，所以平衡了
在這里插入圖片描述

代碼

代碼最簡單，但是，，，，理解有難度

//慷訓者為兩黑時進入程式，執行后會直接進入下一次回圈
//回圈條件node!=root&&getColor(node)==BLACK
if(getColor(leftOf(rBro))==BLACK&&getColor(rightOf(rBro))==BLACK){
    setColor(rBro,RED);
    node=parentOf(node);
}

思考：父節點紅且兄弟無紅色子節點

思路

這種情況只要將該紅色父節點下兩邊的樹的黑色都減少一層（洗掉的一側已經減少，只要將另一側減少一層黑色），再將該紅色父節點變成黑色即可，
該紅色父節點變成黑色意味著：在左右的子節點路徑上同時增加了一個黑色節點

圖解

第一步：該節點兄弟子節點為黑，不滿足，將兄弟變紅，向上走
在這里插入圖片描述
第二步：該節點兄弟子節點仍為黑，不滿足，將兄弟變紅，向上走

第三步：該節點為紅，就直接將該節點變成黑色，就平衡了，
平衡結果：

該程序對應在234樹中就是這種情況，不過要注意234樹原來的（002，005）節點在紅黑樹中是005為黑色在上面，002為紅色的在下面
在這里插入圖片描述

fixAfterRemove流程圖

在這里插入圖片描述

整合調整的代碼（fixAfterRemove）

    private void fixAfterRemove(RBNode node) {
        while (node != root && getColor(node) == BLACK) {
        	//洗掉節點是父節點的左節點
            if (node == leftOf(parentOf(node))) {
                RBNode rBro = rightOf(parentOf(node));
                //(假)兄弟為紅色 情況四
                if (getColor(rBro) == RED) {
                    leftRotate(parentOf(node));
                    rBro = rightOf(parentOf(node));
                }
			
				//兄弟為黑色且無紅色節點 情況5
                if (getColor(leftOf(rBro)) == BLACK && getColor(rightOf(rBro)) == BLACK) {
                    setColor(rBro, RED);
                    node = parentOf(node);
                } else {//兄弟為黑色有紅色節點 情況1---3
                    if (getColor(rightOf(rBro)) == BLACK) {
                        rightRotate(rBro);
                        rBro = rightOf(parentOf(node));
                    }
                    leftRotate(parentOf(node));
                    setColor(parentOf(node), BLACK);
                    setColor(rightOf(rBro), BLACK);
                    break;
                }
            } else {//洗掉節點是父節點的右節點
                RBNode lBro = leftOf(parentOf(node));
                if (getColor(lBro) == RED) {
                    rightRotate(parentOf(node));
                    lBro = leftOf(node);
                }
                if (getColor(rightOf(lBro)) == BLACK && getColor(leftOf(lBro)) == BLACK) {
                    setColor(lBro, RED);
                    node = parentOf(node);
                } else {//兩紅或者一紅
                    if (getColor(leftOf(lBro)) == BLACK) {
                        leftRotate(lBro);
                        lBro = leftOf(parentOf(node));
                    }
                    rightRotate(parentOf(node));
                    setColor(parentOf(node), BLACK);
                    setColor(leftOf(lBro), BLACK);
                    break;
                }
            }
        }
        //替代借點為紅色，直接變黑，該節點下面必不可能還有節點
        setColor(node, BLACK);
    }

三種方法整合（remove）

public V remove(K key) {
    RBNode node = getNode(key);
    if (node == null) {
       return null;
    }
    V oldValue = (V) node.value;
    deleteNode(node);
    return oldValue;
}

洗掉代碼整合

    public V remove(K key) {
        RBNode node = getNode(key);
        if (node == null) {
            return null;
        }
        V oldValue = (V) node.value;
        deleteNode(node);
        return oldValue;
    }


    private RBNode getNode(K key) {
        RBNode tail = root;
        if (root == null) {
            throw new RuntimeException("不可能空");
        }
        while (tail != null) {
            int cmp = key.compareTo((K) tail.key);
            if (cmp < 0) {
                tail = leftOf(tail);
            } else if (cmp > 0) {
                tail = rightOf(tail);
            } else {
                return tail;
            }
        }
        return null;
    }

    private RBNode deleteNode(RBNode node) {
        if (leftOf(node) != null && rightOf(node) != null) {
            RBNode pre = pre(node);
            node.key = pre.key;
            node.value = pre.value;
            node = pre;
        }
        RBNode replace = leftOf(node) != null ? leftOf(node) : rightOf(node);
        if (replace != null) {
            replace.parent = parentOf(node);
            if (parentOf(node) == null) {
                root = replace;
            } else if (node == leftOf(parentOf(node))) {
                node.parent.left = replace;
            } else {
                node.parent.right = replace;
            }
            node.left = node.right = node.parent = null;
            if (getColor(node) == BLACK) {
                fixAfterRemove(replace);
            }
        }
        else {
            if (getColor(node) == BLACK) {
                fixAfterRemove(node);
            }
            if (parentOf(node) != null) {
                if (node == leftOf(parentOf(node))) {
                    node.parent.left = null;
                } else {
                    node.parent.right = null;
                }
                node.parent = null;
            } else {
                root = null;
            }
        }
        return null;
    }

    private void fixAfterRemove(RBNode node) {
        while (node != root && getColor(node) == BLACK) {
            if (node == leftOf(parentOf(node))) {
                RBNode rBro = rightOf(parentOf(node));
                if (getColor(rBro) == RED) {
                    leftRotate(parentOf(node));
                    rBro = rightOf(parentOf(node));
                }
                if (getColor(leftOf(rBro)) == BLACK && getColor(rightOf(rBro)) == BLACK) {
                    setColor(rBro, RED);
                    node = parentOf(node);
                } else {
                    if (getColor(rightOf(rBro)) == BLACK) {
                        rightRotate(rBro);
                        rBro = rightOf(parentOf(node));
                    }
                    leftRotate(parentOf(node));
                    setColor(parentOf(node), BLACK);
                    setColor(rightOf(rBro), BLACK);
                    break;
                }
            } else {
                RBNode lBro = leftOf(parentOf(node));
                if (getColor(lBro) == RED) {
                    rightRotate(parentOf(node));
                    lBro = leftOf(node);
                }
                if (getColor(rightOf(lBro)) == BLACK && getColor(leftOf(lBro)) == BLACK) {
                    setColor(lBro, RED);
                    node = parentOf(node);
                } else {//兩紅或者一紅
                    if (getColor(leftOf(lBro)) == BLACK) {
                        leftRotate(lBro);
                        lBro = leftOf(parentOf(node));
                    }
                    rightRotate(parentOf(node));
                    setColor(parentOf(node), BLACK);
                    setColor(leftOf(lBro), BLACK);
                    break;
                }
            }
        }
        setColor(node, BLACK);
    }

完整代碼和測驗

創建TreeMap包
包下有這三個類：
RBTreeTest
TreeOperation
RBTree
前兩個是測驗類，寫好的，不用管，運行類RBTreeTest即可

RBTreeTest

package TreeMap;
import java.util.Scanner;
public class RBTreeTest {
    public static void main(String[] args) {

        //測驗那個打開那個，不能同時打開

//        insertOpt(); //新增節點

//        deleteOpt(); //洗掉節點
    }

    public static void insertOpt(){
        Scanner scanner=new Scanner(System.in);
        RBTree<String,Object> rbt=new RBTree<>();
        while (true){
            System.out.println("請輸入你要插入的節點:");
            String key=scanner.next();
            System.out.println();
            if(key.length()==1){
                key="00"+key;
            }else if(key.length()==2){
                key="0"+key;
            }
            rbt.put(key,null);
            TreeOperation.show(rbt.getRoot());
        }
    }

    public static void deleteOpt(){
        RBTree<String,Object> rbt=new RBTree<>();
        rbt.put("001",null);
        rbt.put("002",null);
        rbt.put("003",null);
        rbt.put("004",null);
        rbt.put("005",null);
        rbt.put("006",null);
        rbt.put("007",null);
        rbt.put("008",null);
        rbt.put("009",null);
        rbt.put("010",null);
        rbt.put("011",null);
        TreeOperation.show(rbt.getRoot());
        Scanner scanner=new Scanner(System.in);
        while (true){
            System.out.println("請輸入你要洗掉的節點:");
            String key=scanner.next();
            System.out.println();
            if(key.length()==1){
                key="00"+key;
            }else if(key.length()==2){
                key="0"+key;
            }
            rbt.remove(key);
            TreeOperation.show(rbt.getRoot());
        }
    }
}

TreeOperation

package TreeMap;
public class TreeOperation {
    public static int getTreeDepth(RBTree.RBNode root) {
        return root == null ? 0 : (1 + Math.max(getTreeDepth(root.getLeft()), getTreeDepth(root.getRight())));
    }


    private static void writeArray(RBTree.RBNode currNode, int rowIndex, int columnIndex, String[][] res, int treeDepth) {
        if (currNode == null) return;
        if(currNode.isColor()){
                res[rowIndex][columnIndex] = ("\033[30;3m" + currNode.getValue()+"\033[0m") ;
        }else {
                res[rowIndex][columnIndex] = ("\033[31;3m" + currNode.getValue()+"\033[0m") ;
        }
        int currLevel = ((rowIndex + 1) / 2);
        if (currLevel == treeDepth) return;
        int gap = treeDepth - currLevel - 1;
        if (currNode.getLeft() != null) {
            res[rowIndex + 1][columnIndex - gap] = "/";
            writeArray(currNode.getLeft(), rowIndex + 2, columnIndex - gap * 2, res, treeDepth);
        }
        if (currNode.getRight() != null) {
            res[rowIndex + 1][columnIndex + gap] = "\\";
            writeArray(currNode.getRight(), rowIndex + 2, columnIndex + gap * 2, res, treeDepth);
        }
    }


    public static void show(RBTree.RBNode root) {
        if (root == null) {
            System.out.println("EMPTY!");
            System.exit(0);
        }
        int treeDepth = getTreeDepth(root);
        int arrayHeight = treeDepth * 2 - 1;
        int arrayWidth = (2 << (treeDepth - 2)) * 3 + 1;
        String[][] res = new String[arrayHeight][arrayWidth];
        for (int i = 0; i < arrayHeight; i ++) {
            for (int j = 0; j < arrayWidth; j ++) {
                res[i][j] = " ";
            }
        }
        writeArray(root, 0, arrayWidth/2, res, treeDepth);
        for (String[] line: res) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < line.length; i ++) {
                sb.append(line[i]);
                if (line[i].length() > 1 && i <= line.length - 1) {
                    i += line[i].length() > 4 ? 2: line[i].length() - 1;
                }
            }
            System.out.println(sb.toString());
        }
    }
}

RBTree

package TreeMap;

public class RBTree<K extends Comparable<K>,V>{
    private RBNode root;
    private static final boolean BLACK=true;
    private static final boolean RED=false;
    public void put(K key,V value){
        if(null == root){
            root=new RBNode<>(key,value==null?key:value,null);
            return;
        }
        int com;
        RBNode tail=root;
        RBNode parentTail;
        if(key==null){
            throw new RuntimeException("空指標例外");
        }
        do{
            parentTail=tail;
            com=key.compareTo((K) tail.key);
            if(com<0){
                tail=leftOf(tail);
            }else if (com>0){
                tail=rightOf(tail);
            }else {
                tail.value=value==null?key:value;
                return;
            }
        }while (tail!=null);
        RBNode newRBNode=new RBNode<>(key,value==null?key:value,parentTail);
        if (com<0){
            parentTail.left=newRBNode;
        }else {
            parentTail.right=newRBNode;
        }

        fixAfterPut(newRBNode);
    }

    private void fixAfterPut(RBNode newRBNode) {
        setColor(newRBNode,RED);
        while (newRBNode != root&&getColor(parentOf(newRBNode))==RED){
            RBNode grandFather=parentOf(parentOf(newRBNode));
            RBNode father=parentOf(newRBNode);
            if(leftOf(grandFather)==father){
                RBNode uncle=rightOf(grandFather);
                if(getColor(uncle)==RED){
                    setColor(grandFather,RED);
                    setColor(uncle,BLACK);
                    setColor(father,BLACK);
                    newRBNode=grandFather;
                }else {
                    if(rightOf(father)==newRBNode){
                        leftRotate(father);
                        newRBNode=father;
                    }
                    rightRotate(grandFather);
                }
            }else {
                RBNode uncle=leftOf(grandFather);
                if(getColor(uncle)==RED){
                    setColor(grandFather,RED);
                    setColor(uncle,BLACK);
                    setColor(father,BLACK);
                    newRBNode=grandFather;
                }else {
                    if(leftOf(father)==newRBNode){
                        rightRotate(father);
                        newRBNode=father;
                    }
                    leftRotate(grandFather);
                }
            }
        }
        setColor(root,BLACK);
    }

    public V remove(K key) {
        RBNode node = getNode(key);
        if (node == null) {
            return null;
        }
        V oldValue = (V) node.value;
        deleteNode(node);
        return oldValue;
    }

    //獲取該節點
    private RBNode getNode(K key) {
        RBNode tail = root;
        if (root == null) {
            throw new RuntimeException("不可能空");
        }
        while (tail != null) {
            int cmp = key.compareTo((K) tail.key);
            if (cmp < 0) {
                tail = leftOf(tail);
            } else if (cmp > 0) {
                tail = rightOf(tail);
            } else {
                return tail;
            }
        }
        return null;
    }
    
    private RBNode deleteNode(RBNode node) {
        if (leftOf(node) != null && rightOf(node) != null) {
            RBNode pre = pre(node);
            node.key = pre.key;
            node.value = pre.value;
            node = pre;
        }
        RBNode replace = leftOf(node) != null ? leftOf(node) : rightOf(node);
        if (replace != null) {
            replace.parent = parentOf(node);
            if (parentOf(node) == null) {
                root = replace;
            } else if (node == leftOf(parentOf(node))) {
                node.parent.left = replace;
            } else {
                node.parent.right = replace;
            }
            node.left = node.right = node.parent = null;
            if (getColor(node) == BLACK) {
                fixAfterRemove(replace);
            }
        }
        else {
            if (getColor(node) == BLACK) {
                fixAfterRemove(node);
            }
            if (parentOf(node) != null) {
                if (node == leftOf(parentOf(node))) {
                    node.parent.left = null;
                } else {
                    node.parent.right = null;
                }
                node.parent = null;
            } else {
                root = null;
            }
        }
        return null;
    }

    private void fixAfterRemove(RBNode node) {
        while (node != root && getColor(node) == BLACK) {
            if (node == leftOf(parentOf(node))) {
                RBNode rBro = rightOf(parentOf(node));
                if (getColor(rBro) == RED) {
                    leftRotate(parentOf(node));
                    rBro = rightOf(parentOf(node));
                }
                if (getColor(leftOf(rBro)) == BLACK && getColor(rightOf(rBro)) == BLACK) {
                    setColor(rBro, RED);
                    node = parentOf(node);
                } else {
                    if (getColor(rightOf(rBro)) == BLACK) {
                        rightRotate(rBro);
                        rBro = rightOf(parentOf(node));
                    }
                    leftRotate(parentOf(node));
                    setColor(parentOf(node), BLACK);
                    setColor(rightOf(rBro), BLACK);
                    break;
                }
            } else {
                RBNode lBro = leftOf(parentOf(node));
                if (getColor(lBro) == RED) {
                    rightRotate(parentOf(node));
                    lBro = leftOf(node);
                }
                if (getColor(rightOf(lBro)) == BLACK && getColor(leftOf(lBro)) == BLACK) {
                    setColor(lBro, RED);
                    node = parentOf(node);
                } else {
                    if (getColor(leftOf(lBro)) == BLACK) {
                        leftRotate(lBro);
                        lBro = leftOf(parentOf(node));
                    }
                    rightRotate(parentOf(node));
                    setColor(parentOf(node), BLACK);
                    setColor(leftOf(lBro), BLACK);
                    break;
                }
            }
        }
        setColor(node, BLACK);

    }

    //前驅
    private RBNode pre(RBNode node) {
        RBNode l = leftOf(node);
        while (l.right != null) {
            l = l.right;
        }
        return l;
    }
    //后繼
private RBNode suc(RBNode node){
    RBNode r=node.right;
    while (r.left!=null){
        r=r.left;
    }
    return r;
}

    private  void leftRotate(RBNode p)  {
        if(p!=null){
            RBNode l=p.right;
            setColor(l, p.color);
            setColor(p, RED);
            p.right = l.left;
            if (l.left != null) {
                l.left.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.left = p;

            p.parent = l;
        }
    }
private void rightRotate(RBNode p)  {
    RBNode r = p.left;
    setColor(r, getColor(p));
    setColor(p, RED);
    p.left = r.right;
    if (r.right != null) {
        r.right.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.right = p;
    p.parent = r;
}

    private static boolean getColor(RBNode rbNode){
        return rbNode==null?BLACK:rbNode.color;
    }
    private static void setColor(RBNode rbNode, boolean b){
        if(rbNode!=null){
            rbNode.color=b;
        }
    }
    private static RBNode parentOf(RBNode rbNode){
        return rbNode==null?null:rbNode.parent;
    }
    private static RBNode leftOf(RBNode rbNode){
        return rbNode==null?null:rbNode.left;
    }
    private static RBNode rightOf(RBNode rbNode){
        return rbNode==null?null:rbNode.right;
    }

    public void show(){
        if(root==null){
            System.out.println("空");
        }else {
            show(root);
        }
    }
    private void show(RBNode tail){
        if (tail.left!=null){
            show(tail.left);
        }
        System.out.println(tail);
        if (rightOf(tail)!=null){
            show(rightOf(tail));
        }
    }

    public RBNode getRoot() {
        return root;
    }

    static class RBNode<K extends Comparable<K>,V>{
        K key;
        V value;
        private boolean color;
        RBNode parent;
        RBNode left;
        RBNode right;

        public RBNode(K key, V value, RBNode parent) {
            this.key = key;
            this.value = value;
            this.color = BLACK;
            this.parent = parent;
        }

        @Override
        public String toString() {
            return "RBNode{" +
                    "key=" + key +
                    ", value=" + value +
                    ", color=" + (color?"BLACK":"RED") +
                    '}';
        }


        public RBNode getLeft() {
            return left;
        }

        public RBNode getRight() {
            return right;
        }

        public boolean isColor() {
            return color;
        }

        public V getValue() {
            return value;
        }

    }

}

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/297685.html

標籤：java

上一篇：Python爬蟲采集，中介網互聯網網站排行榜，樣本數量：58341

下一篇：C語言 define 定義函式 - C語言零基礎入門教程

基于234樹手撕TreeMap紅黑樹原始碼（3萬字長文帶你走進紅黑深處的細節）

紅黑樹

紅黑樹優勢到底在哪

紅黑樹和234樹的映射關系

什么是234B

234節點的對應

234樹的生長

234樹的洗掉

映射關系

轉化Test

紅黑樹性質

節點類和基本方法

紅黑樹的左右旋

左旋圖1

左旋圖2

左旋代碼

右旋圖

右旋代碼

新增節點

AVL樹方法搜索位置

紅黑插入的情況圖解（以左為例）

紅黑插入的情況圖流程圖

代碼詳解

新增代碼整合（put）

洗掉節點

尋找該節點（getNode）

洗掉定位節點（deleteNode）

洗掉節點情況分析

代碼分解

情況三

replace的分析和確定

if處理情況二

else處理情況一

代碼deleteNode整合

洗掉后的平衡調整（fixAfterRemove）

兄弟為黑色有紅子節點 情況1—3

(假)兄弟為紅色 情況 4

兄弟為黑色且無紅節點 情況5

七個思考：

代碼

思考：父節點紅且兄弟無紅色子節點

思路

圖解

fixAfterRemove流程圖

整合調整的代碼（fixAfterRemove）

三種方法整合（remove）

洗掉代碼整合

完整代碼和測驗

RBTreeTest

TreeOperation

RBTree

兄弟為黑色有紅子節點情況1—3

(假)兄弟為紅色情況 4

兄弟為黑色且無紅節點情況5