關於紅黑樹的原理網上的資源就挺多的,而且情況有點小復雜,所以在這裡我就不再陳述瞭,直接上代碼吧:
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實現二叉樹的圖形顯示》