<?php

//大部分代码按照自己对算法导论的伪代码的理解编写
namespace zxszl;

/*
红黑树的特性:
（1）每个节点或者是黑色，或者是红色。
（2）根节点是黑色。
（3）每个叶节点（NIL）是黑色。 [注意：这里叶节点，是指为空(NIL或NULL)的子节点！]
（4）如果一个节点是红色的，则它的子节点必须是黑色的。
（5）从一个节点到该节点的叶节点的所有路径上包含相同数目的黑节点。
*/
//参考 https://blog.csdn.net/v_JULY_v/article/details/6105630

class RedBlackNode
{
    public $parent;//父节点
    public $left; //左子节点
    public $right; //右子节点
    public $isRed; //红色节点或者黑色节点

    /**
     * 这里引入两个变量，是为了方便字典数据结构
     * 其中，key作为红黑树的排序依据    
     */
    public $key; //节点值
    public $value; //节点值

    public function __construct ()
    {
        $this->parent = null;
        $this->left = null;
        $this->right = null;
        $this->isRed = true;

        $this->key = null;
        $this->value = null;
    }
}
/**
 * 红黑树 ，左边小节点，右边大节点
 */
class RedBlackTree
{
     /**
     * 深度（树高度）
     * @param RedBlackNode $node
     * @return int
     */
    static public function depth($node)
    {
        if ($node === NULL) {
            return 0;
        }
        $left_d = RedBlackTree::depth($node->left);
        $right_d = RedBlackTree::depth($node->right);
        return ($left_d > $right_d ? $left_d : $right_d) + 1;
    }
    /**
     * 最小节点
     * @return RedBlackNode 最小节点
     */
    static public function minNode($node)
    {
        $current = $node;
        if ($current !== null) {
            while ($current->left !== null) {
                $current = $current->left;
            }
        }
        return $current;
    }

    /**
     * 最大节点
     * @return RedBlackNode 最大节点
     */
    static public function maxNode($node)
    {
        $current = $node;
        if ($current !== null) {
            while ($current->right !== null) {
                $current = $current->right;
            }
        }
        return $current;
    }

    /**
     * 查找指定节点
     * @return RedBlackNode 节点
     */
    public function searchNode($key)
    {
        $current = $this->rootNode;
        while ($current !== NULL) 
        {
            if ($current->key === $key) {
                return $current;
            } elseif ($current->key > $key) {
                $current = $current->left;
            } else {
                $current = $current->right;
            }
        }
        return null;
    }
    /**
     * 插入节点，若$key已经存在，则替换对应节点的$value
     * @return RedBlackNode 插入的节点
     */
    public function insertNode($key,$value)
    {
        //查找节点插入时的父亲节点
        $nodeParent = null;
        do
        {
            $tmp = $this->rootNode;
            while ($tmp !== null)
            {
                $nodeParent = $tmp;
                if ($key === $tmp->key ) {//已经存在key，不必再插入,只要替换value就可以
                    $tmp->value = $value;
                    return; 
                }
                else if ( $key < $tmp->key ) {
                    $tmp = $tmp->left;
                }
                else {
                    $tmp = $tmp->right;
                }
            }
        }while(0);

        //创建新节点,节点为红色
        $node = new RedBlackNode();
        // $node->isRed = true;
        $node->key = $key;
        $node->value = $value;

        //插入节点
        $node->parent = $nodeParent;
        if ($nodeParent === null) {
            $this->rootNode = $node;
        }
        else if ($node->key < $nodeParent->key) {
            $nodeParent->left = $node;
        }
        else {
            $nodeParent->right = $node;
        }
        //修正红黑树
        $this->p_insert_fixup($node);
    }
    /**
     * 删除节点
     */
    public function deleteNode ($key) {
        $z = $this->searchNode($key);
        if ( $z !== null ) //找到$key对应的节点
        {   //$z //待删除节点
            $y = null;
            $x = null;

            ///>>>START $z不为null，那么经过操作，$y一定不为null
            if ($z->left === null || $z->right === null) {
                $y = $z;
            } else {
                $y = RedBlackTree::minNode($z->right); //$z的最小上限
            }
            ///<<<END

            if ( $y->left !== null ) {
                $x = $y->left;
            } else {
                $x = $y->right;
            }

            //删除节点$y
            if ($x !== null){
                $x->parent = $y->parent;
            }

            if ($y->parent === null ) {
                $this->rootNode = $x;
            }
            else if ( $y === $y->parent->left ) {
                $y->parent->left = $x;
            }
            else {
                $y->parent->right = $x;
            }
            $xParent = $y->parent;

            //如果$y不是$z，那么用$y的信息覆盖$z,这样达到删除$z的目的
            if ($y !== $z) {
                $z->key = $y->key;
                $z->value = $y->value;
            }
            //如果删除的节点是黑色，则需要修正
            if ($y->isRed === false) {//$y可能是$z ,也可能是$z的最小上限
                $this->p_delete_fixup($x,$xParent);
            }
        }
    }

    /**
     * 修正红黑树
     * @param RedBlackNode node 插入的节点
     */
    private function p_insert_fixup($node)
    {
        while ($node->parent !== null && $node->parent->isRed === true ) //如果node的父节点是红色 (node是红色)
        {
            $grandParent = $node->parent->parent; //祖父节点，一定存在 (根据红黑树性质，红色节点一定有父节点))
            if ($node->parent === $grandParent->left ) { //node的父节点是左孩子
                $uncle = $grandParent->right;
                //case1：node的父节点是红色，且叔节点是红色
                if ($uncle && $uncle->isRed === true ) {
                    $uncle->isRed = false;
                    $node->parent->isRed = false;
                    $grandParent->isRed = true;
                    $node = $grandParent;
                    continue; //经过这一步之后，组父节点作为新节点存在（跳到case2）
                }
                //case2：node的父节点是红色,叔节点是黑色，node是其父节点的右孩子
                else if ($node === $node->parent->right ) {
                    $node = $node->parent;
                    $this->p_left_rotate($node);
                }
                //case3：node的父节点是红色,叔节点是黑色，node是其父节点的左孩子
                $node->parent->isRed = false;
                $grandParent->isRed = true;
                $this->p_right_rotate($grandParent);
            }
            else { //node的父节点是右孩子
                $uncle = $grandParent->left;
                //case1：node的父节点是红色，且叔节点是红色
                if ($uncle && $uncle->isRed === true ) {
                    $uncle->isRed = false;
                    $node->parent->isRed = false;
                    $grandParent->isRed = true;
                    $node = $grandParent;
                    continue; //经过这一步之后，组父节点作为新节点存在（跳到case2）
                }
                //case2：node的父节点是红色,叔节点是黑色，node是其父节点的左孩子
                else if ($node === $node->parent->left ) {
                    $node = $node->parent;
                    $this->p_right_rotate($node);
                }
                //case3：node的父节点是红色,叔节点是黑色，node是其父节点的左孩子
                $node->parent->isRed = false;
                $grandParent->isRed = true;
                $this->p_left_rotate($grandParent);
            } 
        }
        $this->rootNode->isRed = false;
    }

    /**
     * 修正红黑树
     * @param RedBlackNode $x
     * @param RedBlackNode $xParent
     */
    private function p_delete_fixup($x,$xParent)
    {
        while ( $x !== $this->rootNode && ($x ===null || $x->isRed === false ) )
        {
            if ($x === $xParent->left ) //$x不是根节点，那么$xParent一定存在
            { 
                $w = $xParent->right;
                if ($w !== null ) //若为null，则$w黑色
                {
                    //case1：$x黑, 兄弟节点$w红，父节点黑
                    if ($w->isRed === true ) 
                    {
                        $w->isRed = false;
                        $xParent->isRed = true;
                        $this->p_left_rotate($xParent);
                        $w = $xParent->right; //在左旋处理后，$xParent->right指向的是原来兄弟结点$w的右孩子，黑色
                    }
                    //case2：$x黑色， $w是黑色，且$w两个子节点都是黑色
                    if ( ($w->left===null || $w->left->isRed === false)
                            && ($w->right===null || $w->right->isRed === false) )
                    {
                        $w->isRed = true;
                        $x = $xParent;
                        $xParent = $x->parent;
                    }
                    else 
                    {
                        //case3：$x黑色，$w黑色，$w左子是红色，$w右子是黑色
                        if ( $w->right===null || $w->right->isRed === false )
                        {
                            $w->left->isRed = false;
                            $w->isRed = true;
                            $this->p_right_rotate($w);
                            $w = $xParent->right;
                        }
                        //case4：$x黑色，$w黑色，$w右子是红色，$w左子的颜色任意
                        $w->isRed = $xParent->isRed;
                        $xParent->isRed = false;
                        if ($w->right !== null ) {
                            $w->right->isRed = false;
                        }
                        $this->p_left_rotate($xParent);
                        $x = $this->rootNode;
                        break;//加不加break都可以，因为下次循环条件不满足
                    }
                }
            }
            else //$x是右孩子  $x不是根节点，那么$xParent一定存在
            { 
                $w = $xParent->left;
                if ($w !== null ) //若为null，则$w黑色
                {
                    //case1：$x黑, 兄弟节点$w红，父节点黑
                    if ($w->isRed === true ) 
                    {
                        $w->isRed = false;
                        $xParent->isRed = true;
                        $this->p_right_rotate($xParent);
                        $w = $xParent->left; //在右旋处理后，$xParent->left指向的是原来兄弟结点$w的左孩子，黑色
                    }
                    //case2：$x黑色， $w是黑色，且$w两个子节点都是黑色
                    if ( ($w->left===null || $w->left->isRed === false)
                            && ($w->right===null || $w->right->isRed === false) )
                    {
                        $w->isRed = true;
                        $x = $xParent;
                        $xParent = $x->parent;
                    }
                    else 
                    {
                        //case3：$x黑色，$w黑色，$w左子是黑色，$w右子是红色
                        if ( $w->left===null || $w->left->isRed === false )
                        {
                            $w->right->isRed = false;
                            $w->isRed = true;
                            $this->p_left_rotate($w);
                            $w = $xParent->left;
                        }
                        //case4：$x黑色，$w黑色，$w左子是红色，$w右子的颜色任意
                        $w->isRed = $xParent->isRed;
                        $xParent->isRed = false;
                        if ($w->left !== null ) {
                            $w->left->isRed = false;
                        }
                        $this->p_right_rotate($xParent);
                        $x = $this->rootNode;
                        break;//加不加break都可以，因为下次循环条件不满足
                    }
                }
            }
        }
        if ($x !== null ) {
            $x->isRed = false;
        }
    }

    /**
     * 对指定节点进行左旋操作
     * 左旋中的“左”，意味着“被旋转的节点将变成（自己右孩子的）一个左节点
     *      node                  right
     *      /  \                  /  \ 
     *     a  right   ======>   node  c
     *        /  \              /  \
     *       b    c            a    b
     * 
     * @param RedBlackNode $node
     */
    private function p_left_rotate($node)
    {
        $rightChild = $node->right; //右孩子
        if ($rightChild === null){
            //右孩子为null，左旋结束
            return;
        }
        $rightChild->parent = $node->parent; //将 “node的父亲” 设为 “rightChild的父亲”
        if ($rightChild->parent === null) { 
            //情况1：如果 “rightChild的父亲” 是空节点，则将rightChild设为根节点
            $this->rootNode = $rightChild;
        }
        else if ($node === $node->parent->left ) { 
            //情况2：如果 node是它父节点的左孩子，则将rightChild设为“node的父节点的左孩子”
            $node->parent->left = $rightChild; 
        }
        else {
            // 情况3：(node是它父节点的右孩子) 将rightChild设为“node的父节点的右孩子”
            $node->parent->right = $rightChild; 
        }
        $node->parent = $rightChild; //将 “node的父节点” 设为 “rightChild”

        $node->right = $rightChild->left;    //将 “rightChild的左孩子” 设为 “node的右孩子”
        if ($rightChild->left !== null) {
            $rightChild->left->parent = $node;   //将 “node” 设为 “rightChild的左孩子的父亲”
        }
        $rightChild->left = $node; //将 “node” 设为 “rightChild的左孩子”
    }

    /**
     * 对指定节点进行右旋操作
     * 右旋中的“右”，意味着“被旋转的节点将变成（自己左孩子的）一个右节点”
     *      left                  node
     *      /  \                  /  \ 
     *     a  node   <======    left  c
     *        /  \              /  \
     *       b    c            a    b
     * 
     * @param RedBlackNode $node
     */    
    private function p_right_rotate($node)
    {
        $leftChild = $node->left; //左孩子
        if ($leftChild === null) {
            //左孩子为null，右旋结束
            return;
        }
        $leftChild->parent = $node->parent; //将 “node的父节点” 设为 “leftChild的父节点”
        if ($leftChild->parent === null) {
            // 情况1：如果 “leftChild的父亲” 是空节点，则将leftChild设为根节点
            $this->rootNode = $leftChild;
        }
        else if ($node === $node->parent->left ) {
            // 情况2：如果 node 是它父节点的左孩子，则将leftChild设为“node的父节点的左孩子”
            $node->parent->left = $leftChild;
        }
        else {
            // 情况3：如果 node 是它父节点的右孩子，则将leftChild设为“node的父节点的右孩子”
            $node->parent->right = $leftChild;
        }
        $node->parent = $leftChild; //将leftChild设为“node的父节点”

        $node->left = $leftChild->right; //将 “leftChild的右孩子” 设为"node的左孩子"
        if ( $leftChild->right !== null ){
            $leftChild->right->parent = $node; //将node 设为 “leftChild的右孩子的父节点”
        }
        $leftChild->right = $node;   //将 "node" 设为 “leftChild的右孩子”
    }

    private $rootNode;
}

 $rbTree = new RedBlackTree();
 $testN = 10000;

 function testInsert( $rbTree )
 {
     global $testN;
     $tmpArray = array();
     for ($i = 0 ; $i < $testN ; $i++)
     {
         array_push($tmpArray,$i);
     }
     shuffle($tmpArray);

     for ($i = 0 ; $i < $testN ; $i++)
     {
         $k = $tmpArray[$i];
         $rbTree->insertNode($k,$k);
     }

     for ($i = 0 ; $i < $testN ; $i++)
     {
         $node = $rbTree->searchNode($i);
         if($node === null) {
             echo "not found $i";
         }
         else if ($node->value !== $i ) {
             $value = $node->value;
             echo "found $i,but value is $value";
         }
     }
 }

 function testDelete( $rbTree )
 {
     global $testN;
     $tmpArray = array();
     for ($i = 0 ; $i < $testN ; $i++)
     {
         array_push($tmpArray,$i);
     }
     shuffle($tmpArray);

     for ($i = 0 ; $i < $testN ; $i++)
     {
         $k = $tmpArray[$i];
         $rbTree->deleteNode($k);
     }

     for ($i = 0 ; $i < $testN ; $i++)
     {
         $node = $rbTree->searchNode($i);
         if($node !== null) {
             echo "found $i";
         }
     }
 }

 testInsert($rbTree);
 testDelete($rbTree);