紅黑樹算法

　　紅黑樹介紹

　　紅黑樹（Red Black Tree） 是一種自平衡二叉查找樹，是在計算機科學中用到的一種數據結構，典型的用途是實現關聯數組。

　　它是在1972年由Rudolf Bayer發明的，當時被稱為平衡二叉B樹（symmetric binary B-trees）。后來，在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改為如今的“紅黑樹”。

　　紅黑樹和AVL樹類似，都是在進行插入和刪除操作時通過特定操作保持二叉查找樹的平衡，從而獲得較高的查找性能。

　　它雖然是復雜的，但它的最壞情況運行時間也是非常良好的，并且在實踐中是高效的： 它可以在O(log n)時間內做查找，插入和刪除，這里的n 是樹中元素的數目。

　　紅黑色結構

　　它的統計性能要好于平衡二叉樹(有些書籍紅黑樹據作者姓名，Adelson-Velskii和Landis，將其稱為AVL-樹)，因此，紅黑樹在很多地方都有應用。在C++ STL中，很多部分(包括set, multiset, map, multimap)應用了紅黑樹的變體(SGI STL中的紅黑樹有一些變化，這些修改提供了更好的性能，以及對set操作的支持)。其他平衡樹還有：AVL，SBT，伸展樹，TREAP 等等。

  php紅黑樹實現

　　紅黑樹是算法導論中最復雜的算法之一.實際上雖然需要處理的情況很多,但處理的過程和步驟都是固定的,是一些早已被驗證的方法,所以盡管看起來有些復雜,實際處理的時候按照單個case來觀察的話則很簡單.下面的php代碼是按照算法導論中的描述寫的.

<?php

class RBTree
{
    public $root;
    public $nil;//哨兵
    
    public function __construct()
    {
        // construct the sentinel
        $this->nil = array("left" => null ,"right" => null,"parent" => null,"color" => "BLACK","isnil" => true,"data" => "sentinel");// data 無意義
        
        // set sentinel as the root
        $this->root = &$this->nil;
        
    }
    
    public function Isnil(&$n)
    {
        return $n["isnil"];
    }
    
    // 按照算法導論
    /* 
    
    PHP 里面沒有引用這回事,只有別名,引用本身是一種類型,但是別名則不是一種類型
    別名賦值給另外一個變量并不使其成為一個別名,而引用賦值另一個變量,那個變量也是引用
    PHP中變量名都是別名
    $a = 1;
    $b = &a;
    $a 和 $b 地位一樣
    
    別名就如同指針一樣,但又有區別
    
    REB BLACK TREE初始化的時候sentinel會作為root
    sentinel相當于NULL節點,樹中所有在bst中為NULL的指針均指向sentinel ,包括root的parent指針
    */
    public function insert($n)
    {
        $y = &$this->nil;
        $x = &$this->root;//root是一個引用,$x仍然是引用并且引用正確的對象嗎?, $y = $x = $this->root $y仍然引用那個對象?
        //看起來實際情況是 $x 得到的是root所引用對象的拷貝,最終$y也拷貝了一份
        
        while( !$this->Isnil($x) )
        {
            $y = &$x;//每次進入新的子樹,y代表root,第一次循環的時候,y會代表root,同時如果循環一次也未運行,y可以檢測到樹為空
            if ($n["data"] < $x["data"])
                $x = &$x["left"];
            else
                $x = &$x["right"];
        }
        
        
        
        if( $this->Isnil($y))
            $this->root = &$n;
        else if( $n["data"] < $y["data"] )
            $y["left"] = &$n;
        else
            $y["right"] = &$n;
            
        $n["parent"] = &$y;    
        $n["left"] = &$this->nil;//新加入的節點的right left都指向sentinel
        $n["right"] = &$this->nil;
        $n["color"] = "RED";
        $n["isnil"] = false;
        
        $this->insertFixup($n);
        
    }
    
    public function insertFixup(&$node)         
    {    
        
        $n = &$node;
        while ( $n["parent"]["color"]  == "RED" )
        {
            //echo "calling inserFixup,do actually fixup:".$n["data"]."parent:".$n["parent"]["data"]."(".$n["parent"]["color"].")\n";
            // php 中如何表示兩個別名指向同一塊內存
            // 實際上比較兩個別名,PHP是比較它們所指向的值,
            // 如果有兩塊內存,存放了相同的東西,實際上它們的引用應該是不同的
            // 但是PHP里面會認為相同
            
            // 如果兩個引用指向了不同的位置,但是其內容相等,應該有機制可以區別這兩個引用
            // 但是PHP是沒有的
            
            // PHP中似乎不能直接比較兩個引用,一旦比較必然是比較變量本身,
            
            $tmp = &$n["parent"]["parent"];
            if( $n["parent"]["data"] == $tmp["left"]["data"] )
            {
                $y = &$n["parent"]["parent"]["right"];// uncle
                //if uncle is red
                if( $y["color"] == "RED" )
                {
                    $n["parent"]["color"] = "BLACK";
                    $y["color"] = "BLACK";// SET UNCLE to black
                    $n["parent"]["parent"]["color"] = "RED";
                    $n = &$n["parent"]["parent"];
                }
                else  //case 2
                {
                    if ( $n["data"] == $n["parent"]["right"]["data"] )
                    {
                        $n  = &$n["parent"];//將n指向其parent ,然后left rotate
                        $this->leftRotate($n);
                    }
                    $n["parent"]["color"] = "BLACK";
                    $n["parent"]["parent"]["color"] = "RED";
                    $this->rightRotate($n["parent"]["parent"]);                    
                }
            }
            else // 對稱的, n的parent是一個right child
            {
                $y = &$n["parent"]["parent"]["left"];// uncle
                //if uncle is red
                if( $y["color"] == "RED" )
                {
                    $n["parent"]["color"] = "BLACK";
                    $y["color"] = "BLACK";// SET UNCLE to black
                    $n["parent"]["parent"]["color"] = "RED";
                    $n = &$n["parent"]["parent"];
                }
                else  //case 2
                {
                    if ( $n["data"] == $n["parent"]["left"]["data"] )
                    {
                        // 如果n是一個 left child
                        $n  = &$n["parent"];
                        $this->rightRotate($n);
                    }
                    $n["parent"]["color"] = "BLACK";
                    $n["parent"]["parent"]["color"] = "RED";
                    $this->leftRotate($n["parent"]["parent"]);                    
                }            
            }
        }
        
        $this->root["color"] = "BLACK";
    }
    
    /*
                         n
                        / \
                       a   y
                          / \
                         b   c

                          y
                         / \
                        n   c
                       / \
                      a   b
    */
    public function leftRotate(&$n)
    {
        $y = &$n["right"];
        $n["right"] = &$y["left"];
        
        if ( !$this->Isnil($y["left"]) )
        {
            $y["left"]["parent"] = &$n;
        }
        
        $y["parent"] = &$n["parent"];
        
        if ( $this->Isnil($n["parent"]) )
        {
            $this->root = &$y;
        }
        else if ( $n["data"] == $n["parent"]["left"]["data"] )//Fatal error: Nesting level too deep - recursive dependency?
        {
            $n["parent"]["left"] = &$y;
        }
        else
        {
            $n["parent"]["right"] = &$y;
        }
        
        $y["left"] = &$n;
        $n["parent"] = &$y;
        
    }

    /*
                         n
                        / \
                       y   a
                      / \
                     b   c

                          y
                         / \
                        b   n
                           / \
                          c   a
    */
    public function rightRotate(&$n)
    {
        $y = &$n["left"];
        $n["left"] = &$y["right"];
        
        if ( !$this->Isnil($y["right"]) )
        {
            $y["right"]["parent"] = &$n;
        }
        
        $y["parent"] = &$n["parent"];
        
        if ( $this->Isnil($n["parent"]) )
        {
            $this->root = &$y;
        }
        else if ( $n["data"] == $n["parent"]["left"]["data"] )
        {
            $n["parent"]["left"] = &$y;
        }
        else
        {
            $n["parent"]["right"] = &$y;
        }
        
        $y["right"] = &$n;
        $n["parent"] = &$y;
        
    }
    
    // 按照數據結構和算法分析里面的操作
    public function delete($data,&$r)
    {
        if ( $r == null )
            return;//沒有找到節點,或者視圖從一個空樹中刪除節點
        if ( $data < $r["data"] )
            $this->delete( $data, $r["left"] );
        else if ( $data > $r["data"] )
            $this->delete( $data, $r["right"] );
        else if ( $r["left"] != null && $r["right"] != null )
        {
            //往下的都是$data == $r["data"] ,找到節點,而且其左右均不為空
            
            $min =  $this->findMin( $r["right"] );// y replace z , 
            $r["data"] = $min["data"];
            $this->delete( $r["data"] , $r["right"]);//delete y which in z's right subtree
        }
        else
        {
            //找到,但是該節點最多只有一個child
            $r = ( $r["left"] != null ) ? $r["left"] : $r["right"];
        }
    }
    
    // 檢測是否違反紅黑樹性質, 用于測試插入和刪除
    public function checkerror()
    {
        if($this->root["color"] == "RED")
        {
            echo "root must be black \n";
            return;
        }
        
        
    }
    
    public function transplant(&$u,&$v)
    {
        if ( $this->Isnil($u["parent"]) )
            $this->root = &$v;
        else if ( $u["data"] == $u["parent"]["left"]["data"] ) // whats wrong with the php
            $u["parent"]["left"] = &$v;
        else
            $u["parent"]["right"] = &$v;
            
        $v["parent"] = &$u["parent"];
    }
    
    public function delete2($data,&$r)
    {
        if ( $this->Isnil($r)  )
            return ;//沒有找到節點
        if ( $data < $r["data"])
            $this->delete2( $data, $r["left"] );
        else if ( $data > $r["data"] )
            $this->delete2( $data, $r["right"] );
        else
        {
            // we find the node , now we can call the algorithm in introduction to algorithm
            $y = &$r;
            $y_origin_color = $r["color"];
            
            if ( $this->Isnil($r["left"]) )
            {
                // simulator the transplant z , z.right
                // 我們沒有改變指針間的關系,而是直接改變了變量的內容,將z所在的變量用z.right覆蓋
                // 在C++的實現中r是指針的引用,指向某個Node,這個引用的對象是parent的right或left
                // 在那里是修改指針的內容為z.right,
                // 但是PHP里面引用就代表變量本身,我們parent.left只是一個別名,別名實際上等于變量名
                // 我們實際上沒有得到parent的right 或 left,而是得到了一個和他等價的,也就是指向同一個變量的變量名
                // 所以我們無法改變引用本身,只能改變其所指向的變量
                $x = &$r["right"];
                $this->transplant($r,$r["right"]);
                //相當于transplant
                
            }
            else if( $this->Isnil($r["right"])  )
            {
                $x = &$r["left"];
                $this->transplant($r,$r["left"]);
            }
            else
            {
                // 有兩個 child
                
                $y =  &$this->findMin( $r["right"] ); // 加& 得到節點的引用
                $y_origin_color = $y["color"];
                echo "y.data is ".$y["data"]." ".$r["data"]."\n";
                
                // y has no left child
                $x = &$y["right"];
                
                if ( $y["parent"]["data"] == $r["data"]) 
                {
                    // y 是r的直接child
                    $x["parent"] = &$y;// x could be sentinel , x will 取代y的位置
                } else
                {
                    // y 是right subtree中的某個節點
                    // 要用 y的right 取代y的位置
                    $this->transplant($y,$y["right"]);//因為PHP不是按照指針來區別節點的,因此如果y有兩個sentinel節點,transplant函數會失效
                    
                    $y["right"]  = &$r["right"];
                    $y["right"]["parent"] = &$y; // 這里的right不是y原來的parent,而是來自r的 right,對transplant的繼續
                    
                }
                
                $this->transplant($r,$y);
                $y["left"] = &$r["left"];//繼續y取代r的步驟
                $y["left"]["parent"] = &$y;// left could be sentinel
                $y["color"] = $r["color"];
                

                
            }
        }
        
        if ( $y_origin_color == "BLACK" )
            $this->deleteFixup($x);
    }
    
    /*
    這里要討論一下,是否會出現,x的parent的兩個孩子都是nil的情況
    不可能,因為x的doubly black, 如果x是sentinel,那么x.parent的另一個節點絕不可能是sentinel too
     
                                     p
                                    / \
                                   x   sentinel
    這樣的話,從到x的black節點比p到sentinel要多,
    因此
    if ( $x == $x["parent"]["left"] )
    總會得到正確的結果
    */
    public function deleteFixup(&$x)
    {
        while ( $x["data"] != $this->root["data"] && $x["color"] == "BLACK" )        // nest level too deep
        {
            // X is a doubly black
            if ( $x["data"] == $x["parent"]["left"]["data"] ) // nest level too deep
            {
                // 如果x是sentinel,而x是right child,而parent也有一個sentinel的left child,
                // 那么這個判斷會失效
                // 發現如果x是sentinel,那么無法判斷x是left 還是right
                
                $s = &$x["parent"]["right"]; // sibling
                if (  $s["color"] == "RED" )
                {
                    $s["color"] = "BLACK";
                    $x["parent"]["color"] = "RED";
                    $this->leftRotate($x["parent"]);
                    $s = $x["parent"]["right"];// sibling , now  the sibling is BLACK , not introduce any violation , transform to case 2
                }
                
                if ( $s["left"]["color"] == "BLACK" && $s["right"]["color"] == "BLACK" )
                {
                    $s["color"] = "RED";
                    $x = &$x["parent"];// float up the x , go back to the while iteration , the loop invariant : x is doubly or red blck node hold
                }
                else 
                {
                    if( $s["right"]["color"] == "BLACK" )
                    {
                        // SIBLING IS BLACK , 并且sibling的兩個child不同時是BLACK , 如果right是BLACK ,left 一定是RED
                        // 操作是transform到 case 4
                        
                        $s["left"]["color"] = "BLACK";
                        $s["color"] = "RED";// exchange s and s.left , then rightRotate
                        $this->rightRotate($s);
                        $s = &$x["parent"]["right"];
                        // now ,sibling is black ,and sibling has a RED right child , is case 4
                    }
                    
                    // into case 4
                    
                    $s["color"] = $x["parent"]["color"];
                    $x["parent"]["color"] = "BLACK";// SIBLING D PARENT 和 sibling 交換眼色
                    // 等價于
                    //$s["parent"]["color"] = "BLACK";,因為事先知道s的color,因此交換無須中間變量
                    $s["right"]["color"] = "BLACK";// 因為下面要rotate,經過right的路徑會減少一個BLACK,因此將right改成黑色
                    $this->leftRotate($x["parent"]);
                    $x = &$this->root;// 完成
                }
            }
            else
            {
                // 如果x是sentinel,而x是right child,而parent也有一個sentinel的left child,
                // 那么這個判斷會失效
                // 發現如果x是sentinel,那么無法判斷x是left 還是right
                
                $s = &$x["parent"]["left"]; // sibling
                if (  $s["color"] == "RED" )
                {
                    $s["color"] = "BLACK";
                    $x["parent"]["color"] = "RED";
                    $this->rightRotate($x["parent"]);
                    $s = $x["parent"]["left"];// sibling , now  the sibling is BLACK , not introduce any violation , transform to case 2
                }
                
                if ( $s["right"]["color"] == "BLACK" && $s["left"]["color"] == "BLACK" )
                {
                    $s["color"] = "RED";
                    $x = &$x["parent"];// float up the x , go back to the while iteration , the loop invariant : x is doubly or red blck node hold
                }
                else 
                {
                    if( $s["left"]["color"] == "BLACK" )
                    {
                        // SIBLING IS BLACK , 并且sibling的兩個child不同時是BLACK , 如果right是BLACK ,left 一定是RED
                        // 操作是transform到 case 4
                        
                        $s["right"]["color"] = "BLACK";
                        $s["color"] = "RED";// exchange s and s.left , then rightRotate
                        $this->leftRotate($s);
                        $s = &$x["parent"]["left"];
                        // now ,sibling is black ,and sibling has a RED right child , is case 4
                    }
                    
                    // into case 4
                    
                    $s["color"] = $x["parent"]["color"];
                    $x["parent"]["color"] = "BLACK";// SIBLING D PARENT 和 sibling 交換眼色
                    // 等價于
                    //$s["parent"]["color"] = "BLACK";,因為事先知道s的color,因此交換無須中間變量
                    $s["left"]["color"] = "BLACK";// 因為下面要rotate,經過right的路徑會減少一個BLACK,因此將right改成黑色
                    $this->rightRotate($x["parent"]);
                    $x = &$this->root;// 完成
                }
            }
        }
        
        $x["color"] = "BLACK";
    }
    
    public function & findMin( &$r )
    {
        if ( $this->Isnil($r) )
            return null;
        if ( $this->Isnil($r["left"]) )
            return $r;
        return $this->findMin($r["left"]);//此處不加&,返回的也是別名而不是拷貝
    }
    
    //按層,從左到右輸出
    public function printTree()
    {
        // 存儲一個數組,是上一層的全部樹根
        $roots = array();
        
        //初始只包含樹根
        $roots[] = $this->root;
        
        $this->printTreeRecursion($roots);
    }
    
    public function printTreeRecursion($roots)
    {
        $nextroots = array();//當前層的所有節點的left right 組成的數組
        
        if( count($roots) == 0 )//退出條件,某層為空
            return;
        
        for( $i = 0 ; $i < count($roots); $i++ )
        {
            if( $roots[$i] != null)
            {
                echo $roots[$i]["data"]." ";
                $nextroots[] = $roots[$i]["left"];
                $nextroots[] = $roots[$i]["right"];
            }            
        }
        echo "\n";//end of current layer
        
        
        $this->printTreeRecursion($nextroots);
    }
    
    public function printTreePreorder(&$r,$d)
    {
        for( $i = 0 ; $i < $d * 2 ; $i++ )
            echo " ";
        
        if( $this->Isnil($r))    
            echo "nill\n";
        else
            echo $r["data"]."(".$r["color"].") PARENT:".$r["parent"]["data"]."\n";
        
        if( $this->Isnil($r))
            return;
        $this->printTreePreorder($r["left"],$d+1);
        $this->printTreePreorder($r["right"],$d+1);
    }
    
    // 中序可按順序輸出,中間的某個元素是跟
    // 這個元素的左邊所有元素是其左樹,右邊全部是其右樹
    public function printTreeInorder(&$r,$d)
    {
        if ( $r != null )
            $this->printTreeInorder($r["left"],$d+1);

        for( $i = 0 ; $i < $d * 2 ; $i++ )
            echo " ";
        
        if( $r == null)    
            echo "nill\n";
        else
            echo $r["data"]."\n";
        
        if( $r != null)            
            $this->printTreeInorder($r["right"],$d+1);
    }

}

$rbt = new RBTree();
echo "hah\n";
//$rbt->insert(array("left" => null,"right" => null,"parent" => null,"color" => "RED","isnil" => false,"data" => 1));
echo "hah\n";
//$rbt->insert(array("left" => null,"right" => null,"parent" => null,"color" => "RED","isnil" => false,"data" => 2));
echo "hah\n";
//$rbt->insert(array("left" => null,"right" => null,"parent" => null,"color" => "RED","isnil" => false,"data" => 3));
echo "hah\n";
//$rbt->printTreePreorder($rbt->root,0);
$rbt->insert(array("left" => null,"right" => null,"parent" => null,"color" => "RED","isnil" => false,"data" => 4));//執行此處的時候出了問題
echo "hah\n";
$rbt->insert(array("left" => null,"right" => null,"parent" => null,"color" => "RED","isnil" => false,"data" => 5));

$rbt->insert(array("left" => null,"right" => null,"parent" => null,"color" => "RED","isnil" => false,"data" => 6));

$rbt->insert(array("left" => null,"right" => null,"parent" => null,"color" => "RED","isnil" => false,"data" => 7));

$rbt->insert(array("left" => null,"right" => null,"parent" => null,"color" => "RED","isnil" => false,"data" => 8));
$rbt->insert(array("left" => null,"right" => null,"parent" => null,"color" => "RED","isnil" => false,"data" => 9));
//$rbt->printTreePreorder($rbt->root,0);

$rbt->insert(array("left" => null,"right" => null,"parent" => null,"color" => "RED","isnil" => false,"data" => 23));

//$rbt->printTreePreorder($rbt->root,0);
/*
下面插入12之后,紅黑樹被破壞了
之前的樹

                          4B
                        /   \
                       2B    6B
                      /  \  /  \
                     1B  3B 5B  8R
                               /  \
                              7B   9B      
                                    \
                                    23R


正確的做法應該是12 會加到 23的left child, RED RED 沖突
uncle是BLACK,z本身是left child,我們應該做一個right rotate

                          4B
                        /   \
                       2B    6B
                      /  \  /  \
                     1B  3B 5B  7B
                                  \
                                  9B      
                                 /  \
                                8R  23R   
                                   /
                                  12R

正確的結果應該是

                          4B
                        /   \
                       2B    6B
                      /  \  /  \
                     1B  3B 5B  8R
                               /  \
                               7B  12B      
                                  /  \
                                 9R  23R   
                                  
*/
$rbt->insert(array("left" => null,"right" => null,"parent" => null,"color" => "RED","isnil" => false,"data" => 12));
//$rbt->printTreePreorder($rbt->root,0);
$rbt->insert(array("left" => null,"right" => null,"parent" => null,"color" => "RED","isnil" => false,"data" => 10));
$rbt->insert(array("left" => null,"right" => null,"parent" => null,"color" => "RED","isnil" => false,"data" => 24));
$rbt->insert(array("left" => null,"right" => null,"parent" => null,"color" => "RED","isnil" => false,"data" => 28));
$rbt->insert(array("left" => null,"right" => null,"parent" => null,"color" => "RED","isnil" => false,"data" => -12));
//$rbt->insert(array("left" => null,"right" => null,"parent" => null,"color" => "RED","isnil" => false,"data" => -5));
//$rbt->insert(array("left" => null,"right" => null,"parent" => null,"color" => "RED","isnil" => false,"data" => -20));
//$rbt->insert(array("left" => null,"right" => null,"parent" => null,"color" => "RED","isnil" => false,"data" => -3));
$rbt->insert(array("left" => null,"right" => null,"parent" => null,"color" => "RED","isnil" => false,"data" => 102));
$rbt->insert(array("left" => null,"right" => null,"parent" => null,"color" => "RED","isnil" => false,"data" => 90));
$rbt->insert(array("left" => null,"right" => null,"parent" => null,"color" => "RED","isnil" => false,"data" => 72));
$rbt->insert(array("left" => null,"right" => null,"parent" => null,"color" => "RED","isnil" => false,"data" => 720));
$rbt->insert(array("left" => null,"right" => null,"parent" => null,"color" => "RED","isnil" => false,"data" => 121));
$rbt->printTreePreorder($rbt->root,0);

$rbt->delete2(4,$rbt->root);

$rbt->delete2(5,$rbt->root);

$rbt->delete2(8,$rbt->root);
$rbt->delete2(24,$rbt->root);
$rbt->delete2(28,$rbt->root);
$rbt->delete2(9,$rbt->root);
$rbt->delete2(6,$rbt->root);
$rbt->delete2(12,$rbt->root);
echo "haha\n";
$rbt->printTreePreorder($rbt->root,0);

//finishing\

//  紅黑樹在實際使用的時候,似乎會傾向于像右邊傾斜
?>

生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈