琯琯博客 纸上得来终觉浅,绝知此事要躬行。

PHP二叉树(三):红黑树

琯琯
2017-11-06

红黑树

<?php
/**
 * 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 优化技巧

评论

内容导航