PHP 는 이 진 트 리 그래 픽 디 스 플레이 기능 에 대한 상세 한 설명 을 실현 합 니 다.[이 진 트 리,밸 런 스 트 리 및 레 드 블랙 트 리 포함]

이 글 의 사례 는 PHP 가 이 진 트 리 그래 픽 디 스 플레이 기능 을 구현 하 는 것 을 보 여 준다.여러분 께 참고 하도록 공유 하 겠 습 니 다.구체 적 으로 는 다음 과 같 습 니 다.
선언:
최근 에 선생님 께 서 숙제 를 내 주 셨 습 니 다.균형 이 잡 힌 이 진 트 리 와 빨 간 검 은 나 무 를 이해 하고 실현 하 라 고 하 셨 습 니 다.원래 선생님 께 서 C\#로 쓰 셨 다 고 하 셨 는데 제 가 배 운 C\#는 선생님 께 거의 다 돌려 드 렸 습 니 다.어떻게 하 죠?그럼 지금 가장 익숙 한 언어 인 PHP 로 써 주세요!
한 가지 문제 가 있 습 니 다.책 에 서 는 나 무 를 설명 할 때 기본적으로 이미지 의 나무 그림 을 보 여 줍 니 다.그러나 우리 스스로 어떤 나 무 를 실현 하려 고 시도 할 때 디 버 깅,출력 할 때 문자 로 만 출력 할 수 있 습 니 다.이것 은 디 버 깅 등에 매우 큰 불편 을 가 져 왔 다.그리고 각종 바 이 두 후에 나 는 PHP 를 이용 하여 이 진 트 리 의 도형 을 나타 내 는 자원 이 거의 0 이라는 것 을 발견 했다!좋아,그럼 나 혼자 하나 실현 할 게!
효과 표시:
만약 에 제 가 이 단계 에서 코드 를 만 들 었 다 면 여러분 들 이 비교적 답답 할 것 입 니 다.그러면 제 가 바로 결 과 를 올 리 겠 습 니 다.그 다음 에 코드 를 보충 하고 여러분 들 의 읽 기 흥 미 를 자극 하 겠 습 니 다.
1.이 진 트 리 검색:

2.밸 런 스 이 진 트 리:

3.검 붉 은 나무:

상위 코드:
우리 그림 에 클래스 를 만 듭 시다.약간 고 급 스 러 워 보 입 니 다.
image.php 파일:

<?php
/**
 * author:LSGOZJ
 * description:        
 */
class image
{
  //     
  //         
  private $level_high = 100;
  //            
  private $leaf_width = 50;
  //      
  private $rad = 20;
  //          
  private $leave = 20;
  // （        ）
  private $tree;
  //    
  private $level;
  //               （         ，            ）
  private $maxCount;
  //      
  //    
  private $width;
  //    
  private $height;
  //      （RGB）
  private $bg = array(
    220, 220, 220
  );
  //    （             ）
  private $nodeColor = array(
    255, 192, 203
  );
  //    
  private $image;
  /**
   *     ，      
   * @param $tree         
   * @return null
   */
  public function __construct($tree)
  {
    $this->tree = $tree;
    $this->level = $this->getLevel();
    $this->maxCount = $this->GetMaxCount($this->level);
    $this->width = ($this->rad * 2 * $this->maxCount) + $this->maxCount * $this->leaf_width;
    $this->height = $this->level * ($this->rad * 2) + $this->level_high * ($this->level - 1) + $this->leave;
    //1.    
    $this->image = imagecreatetruecolor($this->width, $this->height); //         ，       
    //     
    $bgcolor = imagecolorallocate($this->image, $this->bg[0], $this->bg[1], $this->bg[2]);
    imagefill($this->image, 0, 0, $bgcolor);
  }
  /**
   *                            
   * @param $level     
   * @return     
   */
  function GetMaxCount($level)
  {
    return pow(2, $level - 1);
  }
  /**
   *         
   * @param null
   * @return     
   */
  function getLevel()
  {
    return $this->tree->Depth();
  }
  /**
   *        
   * @param null
   * @return null
   */
  public function show()
  {
    $this->draw($this->tree->root, 1, 0, 0);
    header("Content-type:image/png");
    imagepng($this->image);
    imagedestroy($this->image);
  }
  /**
   * （  ）          
   * @param $root，   （    ） $i，         $p_x，    x   $p_y,    y  
   * @return null
   */
  private function draw($root, $i, $p_x, $p_y)
  {
    if ($i <= $this->level) {
      //     y  
      $root_y = $i * $this->rad + ($i - 1) * $this->level_high;
      //     x  
      if (!is_null($parent = $root->parent)) {
        if ($root == $parent->left) {
          $root_x = $p_x - $this->width / (pow(2, $i));
        } else {
          $root_x = $p_x + $this->width / (pow(2, $i));
        }
      } else {
        //   
        $root_x = (1 / 2) * $this->width;
        $root_y += $this->leave;
      }
      //   （         （  、  、  ）   ）
      $method = 'draw' . get_class($this->tree) . 'Node';
      $this->$method($root_x, $root_y, $root);
      //           （   ）
      $black = imagecolorallocate($this->image, 0, 0, 0);
      if (!is_null($parent = $root->parent)) {
        imageline($this->image, $p_x, $p_y, $root_x, $root_y, $black);
      }
      //     
      if (!is_null($root->left)) {
        $this->draw($root->left, $i + 1, $root_x, $root_y);
      }
      //     
      if (!is_null($root->right)) {
        $this->draw($root->right, $i + 1, $root_x, $root_y);
      }
    }
  }
  /**
   *         
   * @param $x，     x   $y，     y   $node，       
   * @return null
   */
  private function drawBstNode($x, $y, $node)
  {
    //       
    $black = imagecolorallocate($this->image, 0, 0, 0);
    $nodeColor = imagecolorallocate($this->image, $this->nodeColor[0], $this->nodeColor[1], $this->nodeColor[2]);
    //    
    imageellipse($this->image, $x, $y, $this->rad * 2, $this->rad * 2, $black);
    //       
    imagefill($this->image, $x, $y, $nodeColor);
    //       
    imagestring($this->image, 4, $x, $y, $node->key, $black);
  }
  /**
   *         
   * @param $x，     x   $y，     y   $node，       
   * @return null
   */
  private function drawAvlNode($x, $y, $node)
  {
    $black = imagecolorallocate($this->image, 0, 0, 0);
    $nodeColor = imagecolorallocate($this->image, $this->nodeColor[0], $this->nodeColor[1], $this->nodeColor[2]);
    imageellipse($this->image, $x, $y, $this->rad * 2, $this->rad * 2, $black);
    imagefill($this->image, $x, $y, $nodeColor);
    imagestring($this->image, 4, $x, $y, $node->key . '(' . $node->bf . ')', $black);
  }
  /**
   *       
   * @param $x，     x   $y，     y   $node，       
   * @return null
   */
  private function drawRbtNode($x, $y, $node)
  {
    $black = imagecolorallocate($this->image, 0, 0, 0);
    $gray = imagecolorallocate($this->image, 180, 180, 180);
    $pink = imagecolorallocate($this->image, 255, 192, 203);
    imageellipse($this->image, $x, $y, $this->rad * 2, $this->rad * 2, $black);
    if ($node->IsRed == TRUE) {
      imagefill($this->image, $x, $y, $pink);
    } else {
      imagefill($this->image, $x, $y, $gray);
    }
    imagestring($this->image, 4, $x, $y, $node->key, $black);
  }
}

자,이제 클 라 이언 트 에서 어떻게 호출 하 는 지 봅 시다.
client.php

class Client
{
  public static function Main()
  {
    try {
      //         
      function autoload($class)
      {
        include strtolower($class) . '.php';
      }
      spl_autoload_register('autoload');
      $arr = array(62, 88, 58, 47, 35, 73, 51, 99, 37, 93);
//      $tree = new Bst();  //     
      $tree = new Avl();  //     
//      $tree = new Rbt();  //   
      $tree->init($arr);   //     
//      $tree->Delete(62);
//      $tree->Insert(100);
//      $tree->MidOrder();  //      （          ，            ）
      $image = new image($tree);
      $image->show();  //    
    } catch (Exception $e) {
      echo $e->getMessage();
    }
  }
}
Client::Main();

여기에 사용 되 는 세 나무의 종 류 는 다음 과 같다.
두 갈래 검색 트 리 bst.php:

<?php
 /**
 * author:zhongjin
 * description:      
 */
//  
class Node
{
  public $key;
  public $parent;
  public $left;
  public $right;
  public function __construct($key)
  {
    $this->key = $key;
    $this->parent = NULL;
    $this->left = NULL;
    $this->right = NULL;
  }
}
//     
class Bst
{
  public $root;
  /**
   *       
   * @param $arr          
   * @return null
   */
  public function init($arr)
  {
    $this->root = new Node($arr[0]);
    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 . " ";
      $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;
  }
  /**
   *           
   * @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->right != 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
   */
  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;
      }
    }
    //return $root;
  }
  /**
   *      $key     
   * @param $key         
   * @return null
   */
  function Delete($key)
  {
    if (is_null($this->search($key))) {
      throw new Exception('  ' . $key . "   ，    ！");
    }
    $root = $this->root;
    $dnode = $this->search($key);
    if ($dnode->left == NULL || $dnode->right == NULL) { #                   ， c = dnode
      $c = $dnode;
    } else { #             ，c  dnode     ，                   
      $c = $this->successor($dnode);
    }
    //        ，   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;
    }
    #  c!=dnode，  c dnode     ，  c dnode key 
    if ($c != $dnode) {
      $dnode->key = $c->key;
    }
    #     
//    return $root;
  }
  /**
   * （  ）      
   * @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);
  }
}
?>

균형 트 리 avl.php:

<?php
 /**
 * author:zhongjin
 * description:      
 */
//  
class Node
{
  public $key;
  public $parent;
  public $left;
  public $right;
  public $bf; //    
  public function __construct($key)
  {
    $this->key = $key;
    $this->parent = NULL;
    $this->left = NULL;
    $this->right = NULL;
    $this->bf = 0;
  }
}
//     
class Avl
{
  public $root;
  const LH = +1; //  
  const EH = 0;  //  
  const RH = -1; //  
  /**
   *       
   * @param $arr          
   * @return null
   */
  public function init($arr)
  {
    $this->root = new Node($arr[0]);
    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->bf . " ";
      $this->mid_order($root->right);
    }
  }
  /**
   * （  ）    
   * @param null
   * @return null
   */
  public function MidOrder()
  {
    $this->mid_order($this->root);
  }
  /**
   *   $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->left) {
        $P->left = $R;
      } else {
        $P->right = $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;
    }
  }
  /**
   *   $root                  
   * @param $root（    ）   
   * @return null
   */
  public function LeftBalance($root)
  {
    $L = $root->left;
    $L_bf = $L->bf;
    switch ($L_bf) {
      //  root        ，         
      case self::LH:  //      root         ，       
        $root->bf = $L->bf = self::EH;
        $this->R_Rotate($root);
        break;
      case self::RH:  //      root         ，      
        $L_r = $L->right;  //root        
        $L_r_bf = $L_r->bf;
        //  root          
        switch ($L_r_bf) {
          case self::LH:
            $root->bf = self::RH;
            $L->bf = self::EH;
            break;
          case self::EH:
            $root->bf = $L->bf = self::EH;
            break;
          case self::RH:
            $root->bf = self::EH;
            $L->bf = self::LH;
            break;
        }
        $L_r->bf = self::EH;
        // root          
        $this->L_Rotate($L);
        // root      
        $this->R_Rotate($root);
    }
  }
  /**
   *   $root                  
   * @param $root（    ）   
   * @return null
   */
  public function RightBalance($root)
  {
    $R = $root->right;
    $R_bf = $R->bf;
    switch ($R_bf) {
      //  root        ，         
      case self::RH:  //      root         ，       
        $root->bf = $R->bf = self::EH;
        $this->L_Rotate($root);
        break;
      case self::LH:  //      root         ，      
        $R_l = $R->left;  //root        
        $R_l_bf = $R_l->bf;
        //  root          
        switch ($R_l_bf) {
          case self::RH:
            $root->bf = self::LH;
            $R->bf = self::EH;
            break;
          case self::EH:
            $root->bf = $R->bf = self::EH;
            break;
          case self::LH:
            $root->bf = self::EH;
            $R->bf = self::RH;
            break;
        }
        $R_l->bf = self::EH;
        // root          
        $this->R_Rotate($R);
        // root      
        $this->L_Rotate($root);
    }
  }
  /**
   *         $key     
   * @param $key      
   * @return $key     
   */
  public 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;
  }
  /**
   *           
   * @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       
   */
  private 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       
   */
  private 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;
  }
  /**
   * （  ）    ，          ，          
   * @param $root     $key        
   * @return null
   */
  private function insert_node(&$root, $key)
  {
    //        ，     
    if (is_null($root)) {
      $root = new Node($key);
      //      
      return TRUE;
    } else {
      //        $key     
      if ($key == $root->key) {
        //      
        return FALSE;
      } // root         
      elseif ($key < $root->key) {
        //       
        if (!($this->insert_node($root->left, $key))) {
          //    
          return FALSE;
        }
        //    ,      
        if (is_null($root->left->parent)) {
          $root->left->parent = $root;
        }
        switch ($root->bf) {
          //        ，           
          case self::EH:
            $root->bf = self::LH;
            //   
            return TRUE;
            break;
          //          ，        
          case self::LH:
            $this->LeftBalance($root);
            //   ，     
            return FALSE;
            break;
          //          ，        
          case self::RH:
            $root->bf = self::EH;
            //     
            return FALSE;
            break;
        }
      } // root         
      else {
        //       
        if (!$this->insert_node($root->right, $key)) {
          //    
          return FALSE;
        }
        //    ,      
        if (is_null($root->right->parent)) {
          $root->right->parent = $root;
        }
        switch ($root->bf) {
          //        ，           
          case self::EH:
            $root->bf = self::RH;
            //   
            return TRUE;
            break;
          //          ，        
          case self::LH:
            $root->bf = self::EH;
            return FALSE;
            break;
          //          ，       
          case self::RH:
            $this->RightBalance($root);
            //     
            return FALSE;
            break;
        }
      }
    }
  }
  /**
   * （  ） $key    
   * @param $key        
   * @return null
   */
  public function Insert($key)
  {
    $this->insert_node($this->root, $key);
  }
  /**
   *         （       ）
   * @param $key       
   * @return         
   */
  private function get_del_node($key)
  {
    $dnode = $this->search($key);
    if ($dnode == NULL) {
      throw new Exception("     ！");
      return;
    }
    if ($dnode->left == NULL || $dnode->right == NULL) { #                   ， c = dnode
      $c = $dnode;
    } else { #             ，c  dnode     ，                   
      $c = $this->successor($dnode);
    }
    $dnode->key = $c->key;
    return $c;
  }
  /**
   * （  ）      ，              
   * @param $node          
   * @return null
   */
  private function del_node($node)
  {
    if ($node == $this->root) {
      $this->root = NULL;
      return;
    }
    $current = $node;
    //   node      ，         ，       
    $P = $current->parent;
    //      ，                 
    $lower = TRUE;
    while ($lower == TRUE && !is_null($P)) {
      //         
      if ($current == $P->left) {
        if($current == $node){
          if (!is_null($current->left)) {
            $P->left = $current->left;
          } else {
            $P->left = $current->left;
          }
        }
        $P_bf = $P->bf;
        switch ($P_bf) {
          case self::LH:
            $P->bf = self::EH;
            $lower = TRUE;
            $current = $P;
            $P = $current->parent;
            break;
          case self::EH:
            $P->bf = self::RH;
            $lower = FALSE;
            break;
          case self::RH:
            $this->RightBalance($P);
            $lower = TRUE;
            $current = $P->parent;
            $P = $current->parent;
            break;
        }
      } //   
      else {
        if($current == $node){
          if (!is_null($current->left)) {
            $P->right = $current->left;
          } else {
            $P->right = $current->left;
          }
        }
        $P_bf = $P->bf;
        switch ($P_bf) {
          case self::LH:
            $this->LeftBalance($P);
            $lower = TRUE;
            $current = $P->parent;
            $P = $current->parent;
            break;
          case self::EH:
            $P->bf = self::LH;
            $lower = FALSE;
            break;
          case self::RH:
            $P->bf = self::LH;
            $lower = TRUE;
            $current = $P;
            $P = $current->parent;
            break;
        }
      }
    }
  }
  /**
   * （  ）      
   * @param $key      key 
   * @return null
   */
  public function Delete($key)
  {
    $del_node = $this->get_del_node($key);
    $this->del_node($del_node);
  }
  /**
   * （  ）      
   * @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);
  }
}
?>

붉 은 검 은 나무 rbt.php:

<?php
 /**
 * author:zhongjin
 * 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 관련 내용 에 관심 이 있 는 독자 들 은 본 사이트 의 주 제 를 볼 수 있다.
본 논문 에서 말 한 것 이 여러분 의 PHP 프로 그래 밍 에 도움 이 되 기 를 바 랍 니 다.