johnsiilver Posted October 5, 2006 Share Posted October 5, 2006 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); }} Quote Link to comment Share on other sites More sharing options...
Hi I Am Timbo Posted October 5, 2006 Share Posted October 5, 2006 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. Quote Link to comment Share on other sites More sharing options...
Recommended Posts
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.