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.



Question
In algorithms, for BinarySearchTree class' insert method (def insert(self, data): ), you 1) create the Node object from the data 2) check to see if root is empty (if so make the new Node root), 3) if root is not empty, create current pointer to root, and parent pointer (to None initially) 4) go into "while True:" loop and in loop make parent the current, 5) in loop, check value of current (compared to new Node data) to see if current is to shift to right or left subtree and [...] (so short circuit loop):
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 insert(self, data):
        # 1. create the Node object with the data
        node = Node(data)
        # 2. if root is None, make this new node the root
        if self.root_node == None:            
            self.root_node = node        
        else:
            # 3. if root exists, then create a current pointer initialized to root, and a parent pointer (None initially)
            current = self.root_node        
            parent = None 
            # 4. go into "while True:" loop and in loop make parent the current  
            while True:            
                parent = current
                # 5. in loop compare the new node data to current node data and either go left side
                #    or right side of tree (and....
                if node.data <= current.data:
                    current = current.left_child
                    ?????????????????????????????????????????????????????????????????????
                        ?????????????????????????????????????????????????????????????????
                        ?????????????????????????????????????????????????????????????????
                else:
                    current = current.right_child
                    ?????????????????????????????????????????????????????????????????????
                        ?????????????????????????????????????????????????????????????????
                        ?????????????????????????????????????????????????????????????????
Answer
if current is None, you found right place to insert, so insert using parent pointer:
                # 5. in loop compare the new node data to current node data and either go left side
                #    or right side of tree and ...
                if node.data <= current.data:
                    current = current.left_child
                    #...and if you hit current of None, use the parent pointer to insert new node and
                    # short circuit loop, other wise the loop will continue down the tree
                    if current is None:
                        parent.left_child = node
                        return
                else:
                    current = current.right_child
                    #...and if you hit current of None, use the parent pointer to insert new node and
                    # short circuit loop, other wise the loop will continue down the tree
                    if current is None:
                        parent.right_child = node
                        return

Question
In algorithms, for BinarySearchTree class' insert method (def insert(self, data): ), you 1) create the Node object from the data 2) check to see if root is empty (if so make the new Node root), 3) if root is not empty, create current pointer to root, and parent pointer (to None initially) 4) go into "while True:" loop and in loop make parent the current, 5) in loop, check value of current (compared to new Node data) to see if current is to shift to right or left subtree and [...] (so short circuit loop):
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 insert(self, data):
        # 1. create the Node object with the data
        node = Node(data)
        # 2. if root is None, make this new node the root
        if self.root_node == None:            
            self.root_node = node        
        else:
            # 3. if root exists, then create a current pointer initialized to root, and a parent pointer (None initially)
            current = self.root_node        
            parent = None 
            # 4. go into "while True:" loop and in loop make parent the current  
            while True:            
                parent = current
                # 5. in loop compare the new node data to current node data and either go left side
                #    or right side of tree (and....
                if node.data <= current.data:
                    current = current.left_child
                    ?????????????????????????????????????????????????????????????????????
                        ?????????????????????????????????????????????????????????????????
                        ?????????????????????????????????????????????????????????????????
                else:
                    current = current.right_child
                    ?????????????????????????????????????????????????????????????????????
                        ?????????????????????????????????????????????????????????????????
                        ?????????????????????????????????????????????????????????????????
Answer
?

Question
In algorithms, for BinarySearchTree class' insert method (def insert(self, data): ), you 1) create the Node object from the data 2) check to see if root is empty (if so make the new Node root), 3) if root is not empty, create current pointer to root, and parent pointer (to None initially) 4) go into "while True:" loop and in loop make parent the current, 5) in loop, check value of current (compared to new Node data) to see if current is to shift to right or left subtree and [...] (so short circuit loop):
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 insert(self, data):
        # 1. create the Node object with the data
        node = Node(data)
        # 2. if root is None, make this new node the root
        if self.root_node == None:            
            self.root_node = node        
        else:
            # 3. if root exists, then create a current pointer initialized to root, and a parent pointer (None initially)
            current = self.root_node        
            parent = None 
            # 4. go into "while True:" loop and in loop make parent the current  
            while True:            
                parent = current
                # 5. in loop compare the new node data to current node data and either go left side
                #    or right side of tree (and....
                if node.data <= current.data:
                    current = current.left_child
                    ?????????????????????????????????????????????????????????????????????
                        ?????????????????????????????????????????????????????????????????
                        ?????????????????????????????????????????????????????????????????
                else:
                    current = current.right_child
                    ?????????????????????????????????????????????????????????????????????
                        ?????????????????????????????????????????????????????????????????
                        ?????????????????????????????????????????????????????????????????
Answer
if current is None, you found right place to insert, so insert using parent pointer:
                # 5. in loop compare the new node data to current node data and either go left side
                #    or right side of tree and ...
                if node.data <= current.data:
                    current = current.left_child
                    #...and if you hit current of None, use the parent pointer to insert new node and
                    # short circuit loop, other wise the loop will continue down the tree
                    if current is None:
                        parent.left_child = node
                        return
                else:
                    current = current.right_child
                    #...and if you hit current of None, use the parent pointer to insert new node and
                    # short circuit loop, other wise the loop will continue down the tree
                    if current is None:
                        parent.right_child = node
                        return
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, p155

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.