PHP二叉樹：紅黑樹

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

/**
 * author:zhongjin
 * time:2016/10/20 11:53
 * description: 紅黑樹
 */
//結點
class Node
{
    public $key;
    public $parent;
    public $left;
    public $right;
    public $IsRed;  //分辨紅節點或黑節點

    public function __construct($key, $IsRed = TRUE)
    {
        $this->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實現的二叉樹圖形化，有瞭視覺上的幫助就能更好的幫助我們進行調試

Related posts:

  1. PHP 編碼規范(25)
  2. 什麼是Session
  3. ApacheReferenceManual5
  4. PHP中如何安裝 Mhash擴展庫
  5. 社區(php&&mysql)五
  6. WML,Apache,和 PHP 的介紹
  7. 如何做到多筆資料的同步
  8. linux下安裝apache與php

發佈留言

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