Computer Science Canada

Deleting Nodes w/ 2 Children from a BST
Author:  whoareyou [ Wed Mar 05, 2014 12:01 am ]
Post subject:  Deleting Nodes w/ 2 Children from a BST
I guess the problem is mostly due to the fact that I still don't understand recursion very well. What my prof is trying to do is to teach it to us by directly applying it to data structures that may use them, such as the Binary Search Tree. I've already been able to delete a node with no children and one children but a node with 2 children is very confusing. I am supposed to write the _delete_node operation. The idea is to replace the deleted node with the node containing the maximum value in its left subtree. By the way, all changes are performed on the nodes, rather than on the values in the nodes. An alternate approach would be to move values between nodes in order to preserve the BST structure (which I think would be easier).

So, once I get into the _delete_node operation with a node with two children, I can find the maximum value in the left subtree easily. With that idea, I came up with this:

code:

        else: #Last condition: two children
           
            old = node
            max_node = node._left
           
            while (max_node._right is not None):
                max_node = max_node._right
               
            node = _BSTNode (max_node._value)
            node._left = old._left
            node._right = old._right

            max_node = self.remove(max_node._value)


This can successfully delete the node at the top of the tree, but with any other node in the tree with two children, it won't work (it keeps the max_node in the original position, but replaces the deleted node correctly). Another thing is that in my profs call trace, it doesn't seem as if he is calling the remove function again to remove max_node. Any help regarding this approach would be fantastic.

Relevant Code:

code:

    def remove(self, key):
        """
        -------------------------------------------------------
        Removes a node with a value matching key from the bst.
        Returns the value matched.
        Use: value = bst.remove( key )
        -------------------------------------------------------
        Preconditions:
          key - data to search for (?)
        Postconditions:
          returns:
          value - value matching key if found,
          otherwise returns None. Update structure of bst as required.
        -------------------------------------------------------
        """
        self._root, value = self._remove_aux(self._root, key)
        return value

    def _remove_aux(self, node, key):
        """
        -------------------------------------------------------
        Attempts to find a value matching key in a BST node. Deletes the node
        if found and returns the sub-tree root.
        Private recursive operation called only by remove.
        Use: node, value = self._remove_aux(node, key)
        -------------------------------------------------------
        Preconditions:
          node - a bst node (_BSTNode)
          key - data to search for (?)
        Postconditions:
          returns:
          node - the node to search for key (_BSTNode)
          value - value of node containing key if it exists, None otherwise.
        -------------------------------------------------------
        """
        if node is None:
            # Base Case: the key is not in the tree.
            value = None
        elif key < node._value:
            # Search the left subtree.
            node._left, value = self._remove_aux(node._left, key)
        elif key > node._value:
            # Search the right subtree.
            node._right, value = self._remove_aux(node._right, key)
        else:
            # Value has been found.
            value = node._value
            # Replace this node with another node.
            node = self._delete_node(node)
            self._count -= 1

        if node is not None and value is not None:
            # If the value was found, update the ancestor heights.
            node._update_height()
        return node, value


code:

    def _delete_node(self, node):
        """
        -------------------------------------------------------
        Removes a node from the bst.
        Use: node = self._delete_node(node)
        -------------------------------------------------------
        Preconditions:
          node - the bst node to be deleted (_BSTNode)
        Postconditions:
          returns:
          node - the node that replaces the deleted node. This node is the node
          with the maximum value in the current node's left subtree (_BSTNode)
        -------------------------------------------------------
        """
       
        # Your code here.
       
        return node
Author:  Insectoid [ Wed Mar 05, 2014 7:55 am ]
Post subject:  RE:Deleting Nodes w/ 2 Children from a BST
The actual delete function should be very short. Any conditions that decide *if* you delete it should be in another function.

The delete function should look like this:

code:

function delete_node (node A){
    if (A != NULL) { //if node A exists
        delete_node (left); //delete its left child
        delete_node (right); //delete its right child
        free (A) //delete A
    }
}
Author:  Tony [ Wed Mar 05, 2014 1:55 pm ]
Post subject:  RE:Deleting Nodes w/ 2 Children from a BST
@Insectoid - that deletes the entire tree rooted at the node A. The interface says to delete just one node.

@whoareyou - good call, you should think more about recursion.
code:

while (max_node._right is not None):
                max_node = max_node._right

Instead of traversing the structure yourself, each node should be able to (recursively) figure out their own max values.
code:

max_node = node._right.max_node()


Finally,
code:

node = _BSTNode (max_node._value)
            node._left = old._left
            node._right = old._right

Instead of creating copies of the leftover nodes, I'm pretty sure that the intended behaviour is to keep the existing nodes, and relink the pointers into the new desired structure. That is, if you are deleting 1 node, you should have just 1 deletion and 0 new nodes being created.
Author:  whoareyou [ Wed Mar 05, 2014 4:37 pm ]
Post subject:  Re: Deleting Nodes w/ 2 Children from a BST
I tried drawing out on paper what the procedure was and I came up with some new code which seems to work. I found two different cases regarding the parent node of the maximum node. Does this look correct?

code:

        else:
           
            parent = node
            max_node = node._left
           
            while (max_node._right is not None):
                parent = max_node
                max_node = max_node._right

           
            if (parent is node):                   
                max_node._left = None
            else:
                parent._right = max_node._left
                max_node._left = parent
               
            parent._update_height()
            max_node._right = node._right
            node = max_node

:


You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.

Terms of Use | Privacy Policy