PHP Balanced tree - Remove element/node

Delete element from balanced tree:

//replaces $old_ptr with $new_ptr in the parent node's left or right node
function replace_pointer_link( $old_ptr, $new_ptr )
{
 global $tree;

 for( $i=0; $i < count($tree); $i++)
 {
  if( $i === $new_ptr )
   continue;//prevents replacing $old_ptr with $new_ptr in $tree[$new_ptr] 
 
  // if $tree[$i]['left'] is empty and we are checking for link to node 0($old_ptr=0),
  // ('' == 0)==true, but ('' === 0)==false
  // we don't need to put link to node 0 on empty nodes
  if( $tree[$i]['left'] === $old_ptr ){
   $tree[$i]['left'] = $new_ptr;
   return;
   }
   elseif( $tree[$i]['right'] === $old_ptr)
  {
   $tree[$i]['right'] = $new_ptr;
   return;
  }
 }

}
function delete( $value, $ptr, $higher)
{
 global $tree, $q, $start;
 static $higher;
 
 if( !$tree[$ptr]['value'] )
 {
  echo "KEY IS NOT IN TREE";
  $higher = false;
 }
 elseif( $value < $tree[$ptr]['value'] )
 {
  delete( $value, $tree[$ptr]['left'], $higher );
  if( $higher )
   balance1( $ptr, $higher);
 }
 elseif ( $value > $tree[$ptr]['value'] )
 {
 delete( $value, $tree[$ptr]['right'], $higher );
  if( $higher )
   balance2( $ptr, $higher);
 }
 else
 {
  $q = $ptr;
  if( $tree[$q]['right'] === null )
  {
   replace_pointer_link( $ptr, $tree[$q]['left'] );
   unset($tree[$q]);
   $higher = true; 
  }
  elseif( $tree[$q]['left'] === null )
  {
   replace_pointer_link( $ptr, $tree[$q]['right']);
   unset($tree[$q]);
   $higher = true;
  }
  else
  {
   del( $tree[$q]['left'], $higher );
   if( $higher )
    balance1( $ptr, $higher);
  
  }
 }
 
}
function balance1( $ptr, &$higher)
{
 global $tree, $start;
 switch( $tree[$ptr]['bal'] ){
  case -1: 
   $tree[$ptr]['bal'] = 0;// after del tree is balanced
  break;
  case 0://after deletion tree is higher in the right side
   $tree[$ptr]['bal'] = 1;
   $higher = false;
  break;
  case 1: // tree must be rebalanced
   $ptr1 = $tree[$ptr]['right'];
   $bal1 = $tree[$ptr1]['bal'];
   
   if( $bal1 >= 0 )// single flip RR
   {
    $tree[$ptr]['right'] = $tree[$ptr1]['left'];
    $tree[$ptr1]['left'] = $ptr;
    
    if( $bal1 == 0 )
    {
     $tree[$ptr]['bal'] = 1;
     $tree[$ptr1]['bal'] = -1;
     $higher = false;
    }else{
     $tree[$ptr]['bal'] = 0;
     $tree[$ptr1]['bal'] = 0;
    }
    
    // start pointer is replaced we need to change $start
    if( $ptr == $start )
     $start = $ptr1;
    replace_pointer_link($ptr, $ptr1);
   }
   else // double flip RL
   {
    $ptr2 = $tree[$ptr1]['left'];
    $bal2 = $tree[$ptr2]['bal'];
    
    $tree[$ptr1]['left'] = $tree[$ptr2]['right'];
    $tree[$ptr2]['right'] = $ptr1;
    
    $tree[$ptr]['right'] = $tree[$ptr2]['left'];
    $tree[$ptr2]['left'] = $ptr;
    
    if( $bal2 == 1 )
    {
     $tree[$ptr]['bal'] = -1;
    }else{
     $tree[$ptr]['bal'] = 0;
    }
    if( $bal2 == -1 )
    {
     $tree[$ptr1]['bal'] = 1;
    }else{
     $tree[$ptr1]['bal'] = 0;
    }

    if( $ptr == $start )
     $start = $ptr2;
    replace_pointer_link( $ptr, $ptr2);
    $tree[$ptr2]['bal'] = 0;
   }
   
  break;
 }
}

function balance2( $ptr, &$higher )
{
 global $tree, $start;
 switch( $tree[$ptr]['bal'] )
 {
  case 1:
   $tree[$ptr]['bal'] = 0;
  break;
  case 0:
   $tree[$ptr]['bal'] =-1;
   $higher = false;
  break;
  case -1:
   $ptr1 = $tree[$ptr]['left'];
   $bal1 = $tree[$ptr1]['bal'];
   
   if( $bal1 <= 0 )// single flip LL
   {
    $tree[$ptr]['left'] = $tree[$ptr1]['right'];
    $tree[$ptr1]['right'] = $ptr;
    
    if( $bal1 == 0 )
    {
     $tree[$ptr]['bal'] = -1;
     $tree[$ptr1]['bal'] = 1;
     $higher = false;
    }
    else
    {
     $tree[$ptr]['bal'] = 0;
     $tree[$ptr1]['bal'] = 0;
    }
    if( $ptr == $start )
     $start = $ptr1;
    replace_pointer_link( $ptr, $ptr1);
   }
   else// double flip LR 
   {
    $ptr2 = $tree[$ptr1]['right'];
    $bal2 = $tree[$ptr2]['bal'];
    
    $tree[$ptr1]['right'] = $tree[$ptr2]['left'];
    $tree[$ptr2]['left'] = $ptr1;
    
    $tree[$ptr]['left'] = $tree[$ptr2]['right'];
    $tree[$ptr2]['right'] = $ptr;
    
    if( $bal2 == -1 )
     $tree[$ptr]['bal'] = 1;
    else
     $tree[$ptr]['bal'] = 0;
    if( $bal2 == 1 )
     $tree[$ptr1]['bal'] = -1;
    else
     $tree[$ptr1]['bal'] = 0;
    
    if( $ptr == $start )
     $start = $ptr2;
    replace_pointer_link($ptr, $ptr2);
    $tree[$ptr2]['bal'] = 0;
   }
  
 }
}
function del( $ptr, &$higher )
{
 global $tree, $q;
 if( $tree[$ptr]['right'] )
 {
  del( $tree[$ptr]['right'], $higher);
  if( $higher )
   balance2( $ptr, $higher);
 }
 else
 {
  $tree[$q]['value'] = $tree[$ptr]['value'];
  $tree[$q]['count'] = $tree[$ptr]['count'];
  
  replace_pointer_link($ptr, $tree[$ptr]['left']);
  if( $ptr == $start )
   $start = $tree[$ptr]['left'];

  unset($tree[$ptr]);
  $higher = true;
 }
}
$my_tree = array();
// you could create as many trees as you want
// but when you want to work with them use $tree = &$my_tree;
$tree = &$my_tree;
$start = 0;

// array for testing deletion in balanced tree 
$values = array(5, 3, 8, 2, 4, 7, 10, 1, 6, 9, 11);

foreach( $values as $val )
{
 $start = search_btree( $val, $start, false);
}
echo "<html><body>";
echo "start=$start;";
echo "<pre>";
print_r( $my_tree );

delete( 4, $start, false);
delete( 8, $start, false);
delete( 6, $start, false);
delete( 5, $start, false);
delete( 2, $start, false);
delete( 1, $start, false);
delete( 7, $start, false);


echo "start=$start<br>";
print_r($tree);

echo "</pre>";
echo "<br><br>";
echo "</body></html>";

Source