Do you want BuboFlash to help you learning these things? Or do you want to add or correct something? Click here to log in or create user.


  • Presentation
  • Question
  • Answer

Question
In algorithms, for BinarySearchTree, the delete method (def delete(self, data): ) has these 5 steps: 1) use helper function to get pointers to node to delete and its parent 2) get children count of node to delete 3) If node to delete has no children, see if its right or left child of parent and act accordingly (cover root case where node is root so set root to None!) 4) If node to delete has one child, get pointer to that child (next_node), and if parent exists (i.e. not root case!), make parent point correctly (via left/right pointer) to that child, then cover root case (i.e. make root the next_node) 5) If node to delete has 2 children, create [...] , and iterate left on the leftmost_node till you find left most, then swap the current node.data with the leftmost_node.data, and delete the leftmost_node via its parent by pointing its left child to leftmost_node right child (which could be None, if no child), making sure to cover the basecase where the parent_of_leftmost_node is the root node (which causes right_child pointer of parent to point to leftmost_node right_child): 
class Node:        
    def __init__(self, data):            
        self.data = data
        self.left_child = None
        self.right_child = None


class Tree:        
    def __init__(self):            
        self.root_node = None

    def get_node_with_parent(self, data):        
        parent = None        
        current = self.root_node        
        if current == None:            
            return (parent, None)
        while current:            
            if data == current.data:                
                return (parent, current)           
            elif data <= current.data:                
                parent = current                
                current = current.left_child            
            else:                
                parent = current                
                current = current.right_child        
        return (parent, current)


    def remove(self, data): 
        # 1. User helper function to get pointers to node to delete and its parent       
        parent, node = self.get_node_with_parent(data)

        if node == None:            
            return False        

        # 2. Get children count of node to delete       
        children_count = 0        
        if node.left_child and node.right_child:            
            children_count = 2        
        elif (node.left_child is None) and (node.right_child is None):            
            children_count = 0        
        else:            
            children_count = 1

        # 3. If node to delete has no children, see if its right or left child of parent and act accordingly (cover case of root/   

        #   no parent!)
        if children_count == 0:
            if parent:                
                if parent.right_child is node:                    
                    parent.right_child = None
                else:
                    parent.left_child = None
            else:
                self.root_node = None
        # 4. If node to delete has one child, get pointer to that child (next_node), and if parent exists (i.e. not root case!), 
        #    make parent point correctly (via left/right pointer) to that child, then cover root case (i.e. make root the           

        #    next_node)
        elif children_count == 1:
            next_node = None
            if node.left_child:
                next_node = node.left_child
            else:
                next_node = node.right_child
            if parent:
                if parent.left_child is node:
                    parent.left_child = next_node
                else:
                    parent.right_child = next_node
            else:
                self.root_node = next_node
        # 5. If node to delete has 2 children         
        else:
            ????????????????????????????????????????????????????????????????????????????
            ????????????????????????????????????????????????????????????????????????????
            while leftmost_node.left_child:
                parent_of_leftmost_node = leftmost_node
                leftmost_node = leftmost_node.left_child
            node.data = leftmost_node.data

            if parent_of_leftmost_node.left_child == leftmost_node:
                parent_of_leftmost_node.left_child = leftmost_node.right_child
            else:  ############ parent_of_leftmost_node is root!!                                  
                parent_of_leftmost_node.right_child = leftmost_node.right_child
Answer
two new pointers, parent_of_leftmost_node (inititialized to node), and leftmost_node (initialized to node.right_child): 
        else:
            parent_of_leftmost_node = node
            leftmost_node = node.right_child
            while leftmost_node.left_child:
                parent_of_leftmost_node = leftmost_node
                leftmost_node = leftmost_node.left_child
            node.data = leftmost_node.data

            if parent_of_leftmost_node.left_child == leftmost_node:
                parent_of_leftmost_node.left_child = leftmost_node.right_child
            else:  ############ parent_of_leftmost_node is root!!                                  
                parent_of_leftmost_node.right_child = leftmost_node.right_child

Question
In algorithms, for BinarySearchTree, the delete method (def delete(self, data): ) has these 5 steps: 1) use helper function to get pointers to node to delete and its parent 2) get children count of node to delete 3) If node to delete has no children, see if its right or left child of parent and act accordingly (cover root case where node is root so set root to None!) 4) If node to delete has one child, get pointer to that child (next_node), and if parent exists (i.e. not root case!), make parent point correctly (via left/right pointer) to that child, then cover root case (i.e. make root the next_node) 5) If node to delete has 2 children, create [...] , and iterate left on the leftmost_node till you find left most, then swap the current node.data with the leftmost_node.data, and delete the leftmost_node via its parent by pointing its left child to leftmost_node right child (which could be None, if no child), making sure to cover the basecase where the parent_of_leftmost_node is the root node (which causes right_child pointer of parent to point to leftmost_node right_child): 
class Node:        
    def __init__(self, data):            
        self.data = data
        self.left_child = None
        self.right_child = None


class Tree:        
    def __init__(self):            
        self.root_node = None

    def get_node_with_parent(self, data):        
        parent = None        
        current = self.root_node        
        if current == None:            
            return (parent, None)
        while current:            
            if data == current.data:                
                return (parent, current)           
            elif data <= current.data:                
                parent = current                
                current = current.left_child            
            else:                
                parent = current                
                current = current.right_child        
        return (parent, current)


    def remove(self, data): 
        # 1. User helper function to get pointers to node to delete and its parent       
        parent, node = self.get_node_with_parent(data)

        if node == None:            
            return False        

        # 2. Get children count of node to delete       
        children_count = 0        
        if node.left_child and node.right_child:            
            children_count = 2        
        elif (node.left_child is None) and (node.right_child is None):            
            children_count = 0        
        else:            
            children_count = 1

        # 3. If node to delete has no children, see if its right or left child of parent and act accordingly (cover case of root/   

        #   no parent!)
        if children_count == 0:
            if parent:                
                if parent.right_child is node:                    
                    parent.right_child = None
                else:
                    parent.left_child = None
            else:
                self.root_node = None
        # 4. If node to delete has one child, get pointer to that child (next_node), and if parent exists (i.e. not root case!), 
        #    make parent point correctly (via left/right pointer) to that child, then cover root case (i.e. make root the           

        #    next_node)
        elif children_count == 1:
            next_node = None
            if node.left_child:
                next_node = node.left_child
            else:
                next_node = node.right_child
            if parent:
                if parent.left_child is node:
                    parent.left_child = next_node
                else:
                    parent.right_child = next_node
            else:
                self.root_node = next_node
        # 5. If node to delete has 2 children         
        else:
            ????????????????????????????????????????????????????????????????????????????
            ????????????????????????????????????????????????????????????????????????????
            while leftmost_node.left_child:
                parent_of_leftmost_node = leftmost_node
                leftmost_node = leftmost_node.left_child
            node.data = leftmost_node.data

            if parent_of_leftmost_node.left_child == leftmost_node:
                parent_of_leftmost_node.left_child = leftmost_node.right_child
            else:  ############ parent_of_leftmost_node is root!!                                  
                parent_of_leftmost_node.right_child = leftmost_node.right_child
Answer
?

Question
In algorithms, for BinarySearchTree, the delete method (def delete(self, data): ) has these 5 steps: 1) use helper function to get pointers to node to delete and its parent 2) get children count of node to delete 3) If node to delete has no children, see if its right or left child of parent and act accordingly (cover root case where node is root so set root to None!) 4) If node to delete has one child, get pointer to that child (next_node), and if parent exists (i.e. not root case!), make parent point correctly (via left/right pointer) to that child, then cover root case (i.e. make root the next_node) 5) If node to delete has 2 children, create [...] , and iterate left on the leftmost_node till you find left most, then swap the current node.data with the leftmost_node.data, and delete the leftmost_node via its parent by pointing its left child to leftmost_node right child (which could be None, if no child), making sure to cover the basecase where the parent_of_leftmost_node is the root node (which causes right_child pointer of parent to point to leftmost_node right_child): 
class Node:        
    def __init__(self, data):            
        self.data = data
        self.left_child = None
        self.right_child = None


class Tree:        
    def __init__(self):            
        self.root_node = None

    def get_node_with_parent(self, data):        
        parent = None        
        current = self.root_node        
        if current == None:            
            return (parent, None)
        while current:            
            if data == current.data:                
                return (parent, current)           
            elif data <= current.data:                
                parent = current                
                current = current.left_child            
            else:                
                parent = current                
                current = current.right_child        
        return (parent, current)


    def remove(self, data): 
        # 1. User helper function to get pointers to node to delete and its parent       
        parent, node = self.get_node_with_parent(data)

        if node == None:            
            return False        

        # 2. Get children count of node to delete       
        children_count = 0        
        if node.left_child and node.right_child:            
            children_count = 2        
        elif (node.left_child is None) and (node.right_child is None):            
            children_count = 0        
        else:            
            children_count = 1

        # 3. If node to delete has no children, see if its right or left child of parent and act accordingly (cover case of root/   

        #   no parent!)
        if children_count == 0:
            if parent:                
                if parent.right_child is node:                    
                    parent.right_child = None
                else:
                    parent.left_child = None
            else:
                self.root_node = None
        # 4. If node to delete has one child, get pointer to that child (next_node), and if parent exists (i.e. not root case!), 
        #    make parent point correctly (via left/right pointer) to that child, then cover root case (i.e. make root the           

        #    next_node)
        elif children_count == 1:
            next_node = None
            if node.left_child:
                next_node = node.left_child
            else:
                next_node = node.right_child
            if parent:
                if parent.left_child is node:
                    parent.left_child = next_node
                else:
                    parent.right_child = next_node
            else:
                self.root_node = next_node
        # 5. If node to delete has 2 children         
        else:
            ????????????????????????????????????????????????????????????????????????????
            ????????????????????????????????????????????????????????????????????????????
            while leftmost_node.left_child:
                parent_of_leftmost_node = leftmost_node
                leftmost_node = leftmost_node.left_child
            node.data = leftmost_node.data

            if parent_of_leftmost_node.left_child == leftmost_node:
                parent_of_leftmost_node.left_child = leftmost_node.right_child
            else:  ############ parent_of_leftmost_node is root!!                                  
                parent_of_leftmost_node.right_child = leftmost_node.right_child
Answer
two new pointers, parent_of_leftmost_node (inititialized to node), and leftmost_node (initialized to node.right_child): 
        else:
            parent_of_leftmost_node = node
            leftmost_node = node.right_child
            while leftmost_node.left_child:
                parent_of_leftmost_node = leftmost_node
                leftmost_node = leftmost_node.left_child
            node.data = leftmost_node.data

            if parent_of_leftmost_node.left_child == leftmost_node:
                parent_of_leftmost_node.left_child = leftmost_node.right_child
            else:  ############ parent_of_leftmost_node is root!!                                  
                parent_of_leftmost_node.right_child = leftmost_node.right_child
If you want to change selection, open document below and click on "Move attachment"

pdf

owner: kkhosravi - (no access) - PYTHON_DATA_STRUCTURES_AND_ALGORITHMS.pdf, p159

Summary

statusnot learnedmeasured difficulty37% [default]last interval [days]               
repetition number in this series0memorised on               scheduled repetition               
scheduled repetition interval               last repetition or drill

Details

No repetitions

Discussion

Do you want to join discussion? Click here to log in or create user.