Problems with using references in binary tree deletion

[johnsiilver]

I was wondering if anyone could point at what I'm doing wrong in regards to references in a binary tree php library I'm writing.  All of my functions seem to be working with the exception of the delete function.  I can't seem to unset nodes(a dictionary acting like a C struct) or make some nodes update there parent reference.  I think it is because I'm not understanding references correctly.  Any help would be appreciated.

class binaryTree
{

  var $root = null;
  var $node = null;

  /**
  * This function starts a search for a given key
  *
  * @param mixed $key Key to search for
  * @return mixed Data stored in structure referenced by key
  */
  function startSearch($key)
  {
    //Start the search
    $data = $this->searchTree($key, &$this->root);

    return($data);
  }

  /**
  * Inserts a key/data pair into a binary tree
  *
  * @param mixed $key Key the data will be sorted by
  * @param mixed $data Data to be stored and referenced by $key
  */
  function insert($key, $data)
  {
    $node = $this->createNode($key, $data);
    $this->insertNode($node, &$this->root);
  }
 
  /**
  * Public interface for deleting a node by passing a key
  *
  * @param mixed $key
  * @return boolean false if not found, true if deleted
  */
  function delete($key)
  {
    $node =& $this->searchTree($key,&$this->root);
   
    if ($node == false)
      return(false);
   
    $this->deleteNode(&$node);
   
    return(true);
  }

  /**
  * Initializes a node for use in the binary tree
  *
  * @param mixed $key The key which will be used for sorting
  * @param mixed $data The data to be stored
  * @return array Returns an array representing a node
  */
  private function createNode($key, $data)
  {
    $node['key'] = $key;
    $node['data'] = $data;
    $node['parent'] = null;
    $node['left'] = null;
    $node['right'] = null;

    return ($node);
  }

  private function insertNode($insertNode,$treeNode)
  {

    //If this node space is null, go back up and assign the new node
    if ($treeNode == null)
    {
    $treeNode = $insertNode;
    return(true);
    }

    //We need to go down a branch now
    if ($insertNode['key'] < $treeNode['key'])
    {
      //If the branch is null, then assign the new node there
      if ($treeNode['left'] == null)
      {
        //Assigns the node to the left tree
        $treeNode['left'] = &$insertNode;

        //Puts a pointer to the parent
        $insertNode['parent'] = $treeNode;

        return(true);
      }
      //Otherwise, let's go to the next branch
      $this->insertNode($insertNode, &$treeNode['left']);
    }
    else
    {
      //If the branch is null, then assign the new node there
      if ($treeNode['right'] == null)
      {
        //Assigns the node to the right tree
        $treeNode['right'] = &$insertNode;

        //Puts a pointer to the parent
        $insertNode['parent'] = $treeNode;

        return(true);
      }
      $this->insertNode($insertNode, &$treeNode['right']);
    }

  }

  private function deleteNode($node)
  {
    $parent = &$node['parent'];

    //If the node had no children
    if ($node['left'] == null && $node['right'] == null)
    {
      //Figure out which parent pointer the node lives off of
      //and set it to null
      if ($parent != null)//Don't do this part if we are the root node
      {
        if ($node['key'] < $parent['key'])
          $parent['left'] = null;
        else
          $parent['right'] = null;

        //Now delete the node
        unset($node);
      }
      //Ok the node is the root with no children
      else
      {
        unset($node);
        $this->root = null;
      }
    }

    //If the node had only a left child
    elseif ($node['left'] != null && $node['right'] == null)
    {
      //If the node is the root node
      if ($parent == null)
      {
        //Make the left node the root node
        $this->root = &$node['left'];
       
        //Get rid of the root node's parent
        $node['parent'] == null;
       
        //It's now the root, so it has no parent
        $node['left']['parent'] = null;
       
        //Now delete the node
        unset($node);
      }
      //If this is not the root node
      else
      {
        //Make the left child have a parent of the $node's parent
        $node['left']['parent'] = &$node['parent'];
       
        if ($node['parent']['left']['key'] == $node['key'])
        {
          //Move the child into the parent's left node
          $node['parent']['left'] = &$node['left'];
        }
        else
        {
          $node['parent']['right'] = &$node['left'];
        }
        //Now delete the node
        unset($node);
      }
    }//End elseif ($node['left'] != null && $node['right'] == null)

    //If the node had only a right child
    elseif ($node['right'] != null && $node['left'] == null)
    {
      //If the node is the root node
      if ($parent == null)
      {
        //Make the right node the root node
        $this->root = &$node['right'];
       
        //It's now the root, so it has no parent
        $node['right']['parent'] = null;
       
        //Now delete the node
        unset($node);
      }
      //If this is not the root node
      else
      {
        //Make the right child have a parent of the $node's parent
        $node['right']['parent'] = &$node['parent'];
       
       
        if ($node['parent']['left']['key'] == $node['key'])
        {
          //Move the child into the parent's left node
          $node['parent']['left'] = &$node['right'];
        }
        else
        {
          $node['parent']['right'] = &$node['right'];
        }
       
        //Now delete the node
        unset($node);
      }
     
    }//End if ($node['right'] != null && $node['left'] == null)
   
    //Ok, the worst scenario.  If the node has both chilren
    else
    {
      //Used to locate the smallest key in the right subtree
      $pointer = &$node['right'];
     
      //Find the smallest key
      while ($pointer['left'] != null)
      {
        $pointer = &$pointer['left'];
      }
     
      //Now let's copy the key and data into the $node
      $node['key'] = $pointer['key'];
      $node['data'] = $pointer['data'];
     
     

      //Now let's do a delete on the pointer as if we were doing a
      //right only delete
     
      //Make the right child have a parent of the $pointer's parent
      if ($pointer['right'] != null)
        $pointer['right']['parent'] = &$pointer['parent'];



      //Move the child into the parent's left node
      if ($pointer['right'] != null)
        $pointer['parent']['left'] = &$pointer['right'];

     
      //Now we need to remove the parents left child
      //if the pointer doesn't have a right child
      if ($pointer['right'] == null)
        $pointer['parent']['left'] = null;


      //Now delete the node
      unset($pointer);
     
     
    }
  }//End private function deleteNode(&$node)

  /**
  * Searches the binary tree.  Returns the data stored if the key is found,
  * returns false otherwise.
  *
  * @param mixed $key The Key to sort by
  * @param array $node The structure of the binary tree nodes
  * @return mixed Returns the data stored
  */
  private function &searchTree($key, $node)
  {

    //We didn't find the data
    if ($node == null)
      return(false);

    //We found the data
    if ($node['key'] == $key)
      return($node);

  //We need to go down a branch now
  if ($key < $node['key'])
    $data = $this->searchTree($key, &$node['left']);
  else
    $data = $this->searchTree($key, &$node['right']);

  //Now, let's return the $data
  return($data);

  }



}

[Hi I Am Timbo]

You said you are having trouble deleting a node.  What is it set to?  This information may help us figure out why it is not deleting.  Is it not changing at all?

Can you try deleting a node and then do a var_dump() of that node and see what the value is?

I'm just curious why you are doing this?  I understand why one would want to use a binary tree, but in a web application where all instance variables are recreated every time you change pages, this will tax the server far too much on a large scale.  Implementing other search algorithms or using a database's default search would likely be faster.