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); } }