PHP二叉樹(三):紅黑樹

關於紅黑樹的原理網上的資源就挺多的,而且情況有點小復雜,所以在這裡我就不再陳述瞭,直接上代碼吧:

key = $key;
        $this->parent = NULL;
        $this->left = NULL;
        $this->right = NULL;
        //插入結點默認是紅色
        $this->IsRed = $IsRed;
    }
}

//紅黑樹
class Rbt
{
    public $root;

    /**
     * 初始化樹結構
     * @param $arr 初始化樹結構的數組
     * @return null
     */
    public function init($arr)
    {
        //根節點必須是黑色
        $this->root = new Node($arr[0], FALSE);
        for ($i = 1; $i < count($arr); $i++) {
            $this->Insert($arr[$i]);
        }
    }

    /**
     * (對內)中序遍歷
     * @param $root (樹或子樹的)根節點
     * @return null
     */
    private function mid_order($root)
    {
        if ($root != NULL) {
            $this->mid_order($root->left);
            echo $root->key . "-" . ($root->IsRed ? 'r' : 'b') . '  ';
            $this->mid_order($root->right);
        }
    }

    /**
     * (對外)中序遍歷
     * @param null
     * @return null
     */
    public function MidOrder()
    {
        $this->mid_order($this->root);
    }

    /**
     * 查找樹中是否存在$key對應的節點
     * @param $key 待搜索數字
     * @return $key對應的節點
     */
    function search($key)
    {
        $current = $this->root;
        while ($current != NULL) {
            if ($current->key == $key) {
                return $current;
            } elseif ($current->key > $key) {
                $current = $current->left;
            } else {
                $current = $current->right;
            }
        }
        //結點不存在
        return $current;
    }

    /**
     * 將以$root為根節點的最小不平衡二叉樹做右旋處理
     * @param $root(樹或子樹)根節點
     * @return null
     */
    private function R_Rotate($root)
    {
        $L = $root->left;
        if (!is_null($root->parent)) {
            $P = $root->parent;
            if($root == $P->left){
                $P->left = $L;
            }else{
                $P->right = $L;
            }
            $L->parent = $P;
        } else {
            $L->parent = NULL;
        }
        $root->parent = $L;
        $root->left = $L->right;
        $L->right = $root;
        //這句必須啊!
        if ($L->parent == NULL) {
            $this->root = $L;
        }
    }

    /**
     * 將以$root為根節點的最小不平衡二叉樹做左旋處理
     * @param $root(樹或子樹)根節點
     * @return null
     */
    private function L_Rotate($root)
    {
        $R = $root->right;
        if (!is_null($root->parent)) {
            $P = $root->parent;
            if($root == $P->right){
                $P->right = $R;
            }else{
                $P->left = $R;
            }
            $R->parent = $P;
        } else {
            $R->parent = NULL;
        }
        $root->parent = $R;
        $root->right = $R->left;
        $R->left = $root;
        //這句必須啊!
        if ($R->parent == NULL) {
            $this->root = $R;
        }
    }

    /**
     * 查找樹中的最小關鍵字
     * @param $root 根節點
     * @return 最小關鍵字對應的節點
     */
    function search_min($root)
    {
        $current = $root;
        while ($current->left != NULL) {
            $current = $current->left;
        }
        return $current;
    }

    /**
     * 查找樹中的最大關鍵字
     * @param $root 根節點
     * @return 最大關鍵字對應的節點
     */
    function search_max($root)
    {
        $current = $root;
        while ($current->right != NULL) {
            $current = $current->right;
        }
        return $current;
    }

    /**
     * 查找某個$key在中序遍歷時的直接前驅節點
     * @param $x 待查找前驅節點的節點引用
     * @return 前驅節點引用
     */
    function predecessor($x)
    {
        //左子節點存在,直接返回左子節點的最右子節點
        if ($x->left != NULL) {
            return $this->search_max($x->left);
        }
        //否則查找其父節點,直到當前結點位於父節點的右邊
        $p = $x->parent;
        //如果x是p的左孩子,說明p是x的後繼,我們需要找的是p是x的前驅
        while ($p != NULL && $x == $p->left) {
            $x = $p;
            $p = $p->parent;
        }
        return $p;
    }

    /**
     * 查找某個$key在中序遍歷時的直接後繼節點
     * @param $x 待查找後繼節點的節點引用
     * @return 後繼節點引用
     */
    function successor($x)
    {
        if ($x->left != NULL) {
            return $this->search_min($x->right);
        }
        $p = $x->parent;
        while ($p != NULL && $x == $p->right) {
            $x = $p;
            $p = $p->parent;
        }
        return $p;
    }

    /**
     * 將$key插入樹中
     * @param $key 待插入樹的數字
     * @return null
     */
    public function Insert($key)
    {
        if (!is_null($this->search($key))) {
            throw new Exception('結點' . $key . '已存在,不可插入!');
        }
        $root = $this->root;
        $inode = new Node($key);
        $current = $root;
        $prenode = NULL;
        //為$inode找到合適的插入位置
        while ($current != NULL) {
            $prenode = $current;
            if ($current->key > $inode->key) {
                $current = $current->left;
            } else {
                $current = $current->right;
            }
        }

        $inode->parent = $prenode;
        //如果$prenode == NULL, 則證明樹是空樹
        if ($prenode == NULL) {
            $this->root = $inode;
        } else {
            if ($inode->key < $prenode->key) {
                $prenode->left = $inode;
            } else {
                $prenode->right = $inode;
            }
        }

        //將它重新修正為一顆紅黑樹
        $this->InsertFixUp($inode);
    }

    /**
     * 對插入節點的位置及往上的位置進行顏色調整
     * @param $inode 插入的節點
     * @return null
     */
    private function InsertFixUp($inode)
    {
        //情況一:需要調整條件,父節點存在且父節點的顏色是紅色
        while (($parent = $inode->parent) != NULL && $parent->IsRed == TRUE) {
            //祖父結點:
            $gparent = $parent->parent;

            //如果父節點是祖父結點的左子結點,下面的else與此相反
            if ($parent == $gparent->left) {
                //叔叔結點
                $uncle = $gparent->right;

                //case1:叔叔結點也是紅色
                if ($uncle != NULL && $uncle->IsRed == TRUE) {
                    //將父節點和叔叔結點都塗黑,將祖父結點塗紅
                    $parent->IsRed = FALSE;
                    $uncle->IsRed = FALSE;
                    $gparent->IsRed = TRUE;
                    //將新節點指向祖父節點(現在祖父結點變紅,可以看作新節點存在)
                    $inode = $gparent;
                    //繼續while循環,重新判斷
                    continue;   //經過這一步之後,組父節點作為新節點存在(跳到case2)
                }

                //case2:叔叔結點是黑色,且當前結點是右子節點
                if ($inode == $parent->right) {
                    //以父節點作為旋轉結點做左旋轉處理
                    $this->L_Rotate($parent);
                    //在樹中實際上已經轉換,但是這裡的變量的指向還沒交換,
                    //將父節點和字節調換一下,為下面右旋做準備
                    $temp = $parent;
                    $parent = $inode;
                    $inode = $temp;
                }

                //case3:叔叔結點是黑色,而且當前結點是父節點的左子節點
                $parent->IsRed = FALSE;
                $gparent->IsRed = TRUE;
                $this->R_Rotate($gparent);
            } //如果父節點是祖父結點的右子結點,與上面完全相反
            else {
                //叔叔結點
                $uncle = $gparent->left;

                //case1:叔叔結點也是紅色
                if ($uncle != NULL && $uncle->IsRed == TRUE) {
                    //將父節點和叔叔結點都塗黑,將祖父結點塗紅
                    $parent->IsRed = FALSE;
                    $uncle->IsRed = FALSE;
                    $gparent->IsRed = TRUE;
                    //將新節點指向祖父節點(現在祖父結點變紅,可以看作新節點存在)
                    $inode = $gparent;
                    //繼續while循環,重新判斷
                    continue;   //經過這一步之後,組父節點作為新節點存在(跳到case2)
                }

                //case2:叔叔結點是黑色,且當前結點是左子節點
                if ($inode == $parent->left) {
                    //以父節點作為旋轉結點做右旋轉處理
                    $this->R_Rotate($parent);
                    //在樹中實際上已經轉換,但是這裡的變量的指向還沒交換,
                    //將父節點和字節調換一下,為下面右旋做準備
                    $temp = $parent;
                    $parent = $inode;
                    $inode = $temp;
                }

                //case3:叔叔結點是黑色,而且當前結點是父節點的右子節點
                $parent->IsRed = FALSE;
                $gparent->IsRed = TRUE;
                $this->L_Rotate($gparent);
            }
        }
        //情況二:原樹是根節點(父節點為空),則隻需將根節點塗黑
        if ($inode == $this->root) {
            $this->root->IsRed = FALSE;
            return;
        }

        //情況三:插入節點的父節點是黑色,則什麼也不用做
        if ($inode->parent != NULL && $inode->parent->IsRed == FALSE) {
            return;
        }
    }

    /**
     * (對外)刪除指定節點
     * @param $key 刪除節點的key值
     * @return null
     */
    function Delete($key)
    {
        if (is_null($this->search($key))) {
            throw new Exception('結點' . $key . "不存在,刪除失敗!");
        }
        $dnode = $this->search($key);
        if ($dnode->left == NULL || $dnode->right == NULL) { #如果待刪除結點無子節點或隻有一個子節點,則c = dnode
            $c = $dnode;
        } else { #如果待刪除結點有兩個子節點,c置為dnode的直接後繼,以待最後將待刪除結點的值換為其後繼的值
            $c = $this->successor($dnode);
        }

        //為瞭後面顏色處理做準備
        $parent = $c->parent;

        //無論前面情況如何,到最後c隻剩下一邊子結點
        if ($c->left != NULL) {    //這裡不會出現,除非選擇的是刪除結點的前驅
            $s = $c->left;
        } else {
            $s = $c->right;
        }

        if ($s != NULL) { #將c的子節點的父母結點置為c的父母結點,此處c隻可能有1個子節點,因為如果c有兩個子節點,則c不可能是dnode的直接後繼
            $s->parent = $c->parent;
        }

        if ($c->parent == NULL) { #如果c的父母為空,說明c=dnode是根節點,刪除根節點後直接將根節點置為根節點的子節點,此處dnode是根節點,且擁有兩個子節點,則c是dnode的後繼結點,c的父母就不會為空,就不會進入這個if
            $this->root = $s;
        } else if ($c == $c->parent->left) { #如果c是其父節點的左右子節點,則將c父母的左右子節點置為c的左右子節點
            $c->parent->left = $s;
        } else {
            $c->parent->right = $s;
        }

        $dnode->key = $c->key;

        $node = $s;

        //c的結點顏色是黑色,那麼會影響路徑上的黑色結點的數量,必須進行調整
        if ($c->IsRed == FALSE) {
            $this->DeleteFixUp($node,$parent);
        }
    }

    /**
     * 刪除節點後對接點周圍的其他節點進行調整
     * @param $key 刪除節點的子節點和父節點
     * @return null
     */
    private function DeleteFixUp($node,$parent)
    {
        //如果待刪結點的子節點為紅色,直接將子節點塗黑
        if ($node != NULL && $node->IsRed == TRUE) {
            $node->IsRed = FALSE;
            return;
        }


        //如果是根節點,那就直接將根節點置為黑色即可
        while (($node == NULL || $node->IsRed == FALSE) && ($node != $this->root)) {
            //node是父節點的左子節點,下面else與這裡相反
            if ($node == $parent->left) {
                $brother = $parent->right;

                //case1:兄弟結點顏色是紅色(父節點和兄弟孩子結點都是黑色)
                //將父節點塗紅,將兄弟結點塗黑,然後對父節點進行左旋處理(經過這一步,情況轉換為兄弟結點顏色為黑色的情況)
                if ($brother->IsRed == TRUE) {
                    $brother->IsRed = FALSE;
                    $parent->IsRed = TRUE;
                    $this->L_Rotate($parent);
                    //將情況轉化為其他的情況
                    $brother = $parent->right;  //在左旋處理後,$parent->right指向的是原來兄弟結點的左子節點
                }

                //以下是兄弟結點為黑色的情況

                //case2:兄弟結點是黑色,且兄弟結點的兩個子節點都是黑色
                //將兄弟結點塗紅,將當前結點指向其父節點,將其父節點指向當前結點的祖父結點。
                if (($brother->left == NULL || $brother->left->IsRed == FALSE) && ($brother->right == NULL || $brother->right->IsRed == FALSE)) {
                    $brother->IsRed = TRUE;
                    $node = $parent;
                    $parent = $node->parent;
                } else {
                    //case3:兄弟結點是黑色,兄弟結點的左子節點是紅色,右子節點為黑色
                    //將兄弟結點塗紅,將兄弟節點的左子節點塗黑,然後對兄弟結點做右旋處理(經過這一步,情況轉換為兄弟結點顏色為黑色,右子節點為紅色的情況)
                    if ($brother->right == NULL || $brother->right->IsRed == FALSE) {
                        $brother->IsRed = TRUE;
                        $brother->left->IsRed = FALSE;

                        $this->R_Rotate($brother);
                        //將情況轉換為其他情況
                        $brother = $parent->right;
                    }

                    //case4:兄弟結點是黑色,且兄弟結點的右子節點為紅色,左子節點為任意顏色
                    //將兄弟節點塗成父節點的顏色,再把父節點塗黑,將兄弟結點的右子節點塗黑,然後對父節點做左旋處理
                    $brother->IsRed = $parent->IsRed;
                    $parent->IsRed = FALSE;

                    $brother->right->IsRed = FALSE;
                    $this->L_Rotate($parent);
                    //到瞭第四種情況,已經是最基本的情況瞭,可以直接退出瞭
                    $node = $this->root;
                    break;
                }
            } //node是父節點的右子節點
            else {
                $brother = $parent->left;

                //case1:兄弟結點顏色是紅色(父節點和兄弟孩子結點都是黑色)
                //將父節點塗紅,將兄弟結點塗黑,然後對父節點進行右旋處理(經過這一步,情況轉換為兄弟結點顏色為黑色的情況)
                if ($brother->IsRed == TRUE) {
                    $brother->IsRed = FALSE;
                    $parent->IsRed = TRUE;
                    $this->R_Rotate($parent);
                    //將情況轉化為其他的情況
                    $brother = $parent->left;  //在右旋處理後,$parent->left指向的是原來兄弟結點的右子節點
                }

                //以下是兄弟結點為黑色的情況

                //case2:兄弟結點是黑色,且兄弟結點的兩個子節點都是黑色
                //將兄弟結點塗紅,將當前結點指向其父節點,將其父節點指向當前結點的祖父結點。
                if (($brother->left == NULL || $brother->left->IsRed == FALSE) && ($brother->right == NULL || $brother->right->IsRed == FALSE)) {
                    $brother->IsRed = TRUE;
                    $node = $parent;
                    $parent = $node->parent;
                } else {
                    //case3:兄弟結點是黑色,兄弟結點的右子節點是紅色,左子節點為黑色
                    //將兄弟結點塗紅,將兄弟節點的左子節點塗黑,然後對兄弟結點做左旋處理(經過這一步,情況轉換為兄弟結點顏色為黑色,右子節點為紅色的情況)
                    if ($brother->left == NULL || $brother->left->IsRed == FALSE) {
                        $brother->IsRed = TRUE;
                        $brother->right = FALSE;
                        $this->L_Rotate($brother);
                        //將情況轉換為其他情況
                        $brother = $parent->left;
                    }

                    //case4:兄弟結點是黑色,且兄弟結點的左子節點為紅色,右子節點為任意顏色
                    //將兄弟節點塗成父節點的顏色,再把父節點塗黑,將兄弟結點的右子節點塗黑,然後對父節點左左旋處理
                    $brother->IsRed = $parent->IsRed;
                    $parent->IsRed = FALSE;
                    $brother->left->IsRed = FALSE;
                    $this->R_Rotate($parent);
                    $node = $this->root;
                    break;
                }
            }
        }
        if ($node != NULL) {
            $this->root->IsRed = FALSE;
        }
    }

    /**
     * (對內)獲取樹的深度
     * @param $root 根節點
     * @return 樹的深度
     */
    private function getdepth($root)
    {
        if ($root == NULL) {
            return 0;
        }
        $dl = $this->getdepth($root->left);

        $dr = $this->getdepth($root->right);

        return ($dl > $dr ? $dl : $dr) + 1;
    }

    /**
     * (對外)獲取樹的深度
     * @param null
     * @return null
     */
    public function Depth()
    {
        return $this->getdepth($this->root);
    }
}

調試的時候你們可以調用中序遍歷來做,我在上一篇博客中提供瞭PHP實現的二叉樹圖形化,有瞭視覺上的幫助就能更好的幫助我們進行調試,詳細大傢可以訪問我的上一篇博客:《利用PHP實現二叉樹的圖形顯示》

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *