資料結構與演算法：Red Black Tree 紅黑樹 part 2

這篇主要在說明紅黑樹的刪除怎麼處理，第一部份的連結。

刪除的步驟與 BST 相同，透過與要刪除節點的 predecessor或 successor 交換，再進行刪除，透過這個方式，降低刪除節點時造成整個樹巨大變更。

這邊複習 successor與 predecessor在BST中的含意是什麼：

successor：在 inorder traversal 中下一個比自己數值大的節點

predecessor：在 inorder traversal 中前一個比自己數值小的節點

在刪除節點的過程中，會用到x、y 與 z三個位置，不同情況下有不同的意義。z 表示最初要刪除的節點位置， y 表示最後實際上會從樹中被移除的節點位置， x 表示 y 節點被刪除後，要遞補至原本 y 位置的節點。

樹的節點轉換(Transplant)

Transplant 用途在於傳入 u與 v兩個節點， v 將會取代 u 的位置，過程會在 transplant 中調整 u.p child 指向與 v.p 指向節點，讓原本 u.p 的child指向 v，同時 v.p指向 u.p

TRANSPLANT(T, u, v)
	if u.p == T.nil
		T.root = v
	elseif u== u.p.left
		u.p.left=v
	else 
		u.p.right =v
	v.p=u.p

刪除功能

方式與二元樹不會差太多，但是需要調整 parent 與 child 指向，同時需要記錄實際被刪除顏色，過程中，這邊會特別先記錄下『 y 節點最初的顏色』，目的是後續修正紅黑樹時使用：

    @Override
    public void deleteElement(T data) {

        TreeNode z = this.findElement(data); //要刪除的資料
        if(z ==null)
            return;
        TreeNode y = z;  // 刪除node後，要補上的節點
        TreeNode x=null;    //要取代原本 Y 位置的節點
        
        //  最後 x 的parent，目的在於 x 可能是 null，但fixup需要 x的 parent 資訊
        TreeNode parentOfX = null;  

        NodeColor successorOriginColor = y.getColor();  // 儲存 Y 原始顏色
        
        if(z.getLeftChild() == null){
            x = z.getRightChild();
            parentOfX = z.getParent();
            transplant(z, z.getRightChild());

            if(parentOfX==null)
                this.root = x;
        }else if(z.getRightChild() ==null){
            x = z.getLeftChild();
            parentOfX = z.getParent();

            if(parentOfX==null)
                this.root = x;
            transplant(z, z.getLeftChild());
        }else{
          	// z 左右節點都不是 null
            y = this.getMin(z.getRightChild()); // 取得 Z 的 successor
            successorOriginColor = y.getColor();
            x = y.getRightChild();

            if(y.getParent() == z) {
                // Y是Z的直屬child
                parentOfX = y;
                if(x!=null)
                    x.setParent(y);
            }else {
                parentOfX = y.getParent();
                // 將 X 取代 Y
                transplant(y, y.getRightChild());
               
                y.setRightChild(z.getRightChild());
                y.getRightChild().setParent(y);
            }
            transplant(z, y); // 將 Y 取代 Z
            y.setLeftChild(z.getLeftChild());
            y.getLeftChild().setParent(y);
            y.setColor(z.getColor());

            if(y.getParent() == null)
                this.root = y;
        }

        // 如果 Y 原始顏色是黑色，才進行 FIXUP
        if(successorOriginColor == NodeColor.BLACK){
            deleteFixup(x, parentOfX);
        }
    }

從刪除的程式來看，如果z位置的子節點少於2個，透過二元樹方式執行刪除，會直接將節點刪除，不會做節點的交換，所以 y 節點位置會等同 z 節點位置，x位置表示刪除 y 後，要補上y位置的節點。(圖片第二個樹的 x 位置畫錯了，應該在 17 的位置才對)

如果z節點位置的子節點有兩個，透過二元樹執行刪除時，會找到 z 節點的 successor 節點位置 y，表示 y 位置節點會取代掉 z位置節點 ( 將 y 節點位置移至 z 節點位置，表示 y 位置的節點實際上被刪除了)，且 y 的顏色也會調整為 z 的顏色，而 x 位置節點表示當 y 取代 z的位置後，要遞補至原本 y 位置的節點。這個過程中，需要記錄最初找到 y 時 y 節點的顏色。

刪除後調整

刪除的第一步驟大致如上，在執行刪除後，可能會違反紅黑樹的規則，所以在刪除後可能需要再做一次修正，這邊會透過 y 最初的顏色來判斷是否需要修正，並透過 x 來判斷如何修正，修正的情境如下：

如果原本 y 位置的節點顏色是紅色，則不需要進行修正，因為刪除紅色節點不會違反紅黑樹規則
如果原本 y 位置的節點顏色是黑色，則需要進行修正，因為會違反紅黑樹規則：從任何節點至葉節點(leaf)的任意簡單路徑上，黑色節點的數量會相同，所以如果過程中， y原本顏色是黑色，被刪除後，會有一個路徑上少一個黑色節點，就會違反這個規則，所以需要進行修正。

違反紅黑樹規則的情境可以分成幾類，這邊先看的程式：

// 因為 x 可能有 null 情況，故這邊連同 parent一同傳入   
private void deleteFixup(TreeNode x, TreeNode parent){
        while(x!= this.root && (x== null || x.getColor() == NodeColor.BLACK )){

            TreeNode w;	// sibling
          	// 如果 x 是在 parent的左邊
            if(parent.getLeftChild() == x){
                w = parent.getRightChild();

                // case I： sibling 是紅色節點，會將 tree調整為 case II III IV 其中一種
                if(w !=null && w.getColor() == NodeColor.RED){
                    w.setColor(NodeColor.BLACK);
                    parent.setColor(NodeColor.RED);
                    leftRotation(parent);
                    w = parent.getRightChild();
                }

              	// case II： sibling 是黑色且 sibling 兩個 child都是黑色
                if( (w.getRightChild()== null || w.getRightChild().getColor()== NodeColor.BLACK) ||
                        (w.getLeftChild()== null || w.getLeftChild().getColor() == NodeColor.BLACK )){
                    w.setColor(NodeColor.RED);
                    x = x.getParent();	// 重新指定 x，在下一個迴圈再依據新的 case 調整
                    parent = x.getParent();
                }else{
                    // case III：sibling是黑色，且sibling 左邊child是紅色，右邊 child是黑色
                    if(w.getRightChild() == null ||w.getRightChild().getColor() == NodeColor.BLACK){
                        w.getLeftChild().setColor(NodeColor.BLACK);
                        w.setColor(NodeColor.RED);
                        rightRotation(w);
                        w = parent.getRightChild();
                    }

                    // case IV：sibling是黑色，且sibling 右邊child是紅色
                    w.setColor(parent.getColor());
                    parent.setColor(NodeColor.BLACK);
                    w.getRightChild().setColor(NodeColor.BLACK);
                    leftRotation(parent);
                    x = this.root; //調整完成，直接指向 root離開迴圈
                }
            }else{
							// 與左邊操作相反，左右對調即可，故省略
            }
        }
				// x 最後都會被調整為黑色，包含 x=root情況
        x.setColor(NodeColor.BLACK);

    }  	

首先，會分為兩個部分來修正，會依據 x 是位於左邊節點還是右邊節點來做處理，接著透過 x 的兄弟節點(sibling) w 來判斷處理方式，這邊一一列出，總共有 4種 case，並且分為左右兩種，左右兩種操作方式相同，只是左右的操作對調：

這邊的 case 是將 y取代z位置，並且 x 補上至 y原本位置後，視當下條件整理出來的情境與調整方式
下列的各個case都是整個樹中的片段，不代表整個樹的樣貌
下列case 規則都是建立在紅黑樹的規則中，如果要驗證，一定要符合條件的紅黑樹來驗證，而不是隨意使用一個不合規則的紅黑樹驗證(我就是做了這件事情所以卡了很久)，所有的case要在合法的紅黑樹才會有效