My python Binary Tree

Here she is,  I tested the crap out of it,  An edge case error in delete took me a few hours to find. I'll highlight where I fixed it with yellow.
That's part of why delete has so many (#print)'s in it. I left them in so if someone has a similar issue...   "Your size is not dropping, although your items are being deleted." 

I'm still learning,  if you see something drop me a comment!  I'd love to make it better.

--- Start code block --


from random import randint  # for manual testing

 class BinaryTreeNode(object):
    def __init__(self, key, value, left, right):
        self.key = key
        self.value = value
        self.left = left
        self.right = right
   
    def __repr__(self):
        nleft = self.left and self.left.value or None
        nright = self.right and self.right.value or None
        return f"{nleft} <--- ( {self.key} : {self.value} ) ---> {nright}"
       
class BinaryTree(object):
    def __init__(self, median):
        self.median = median
        self.root_node = BinaryTreeNode(self.median, 'binary_root_node', None, None)
        self._size = 0
       
    def set(self, akey, value):
           
        if akey < self.median:
            east = self.root_node.left
           
           
            if not east:
                #  [None<---- newnode _---> None][<--left-- root --right-->]
                newnode = BinaryTreeNode(akey, value, None, None)
                self.root_node.left = newnode
                self._size += 1
            else:
               
                while east:
                    if akey == east.key:
                        east.value = value
                        break
                    elif east.key < akey:
                        if east.right == None:
                            newnode = BinaryTreeNode(akey, value, None, None)
                            east.right = newnode
                            self._size += 1
                            break
                        else:
                            east = east.right
                    else:
                       
                        if east.left == None:
                            newnode = BinaryTreeNode(akey, value, None, None)
                            east.left = newnode
                            self._size += 1
                            break
                        else:
                            east = east.left
               
        if akey > self.median:
            west = self.root_node.right
           
            if not west:
                # [<---- root --right-->][None<---- newnode _---> None]
                newnode = BinaryTreeNode(akey, value, None, None)
                self.root_node.right = newnode
                self._size += 1
            else:
               
                while west:
                    ########################
                    if akey == west.key:
                        west.value = value
                        break
                    elif west.key < akey:
                        if west.right == None:
                            newnode = BinaryTreeNode(akey, value, None, None)
                            west.right = newnode
                            self._size += 1
                            break
                        else:
                            west = west.right
                    else:
                       
                        if west.left == None:
                            newnode = BinaryTreeNode(akey, value, None, None)
                            west.left = newnode
                            self._size += 1
                            break
                        else:
                            west = west.left

     def get(self, akey):
        node = self.root_node
        if akey < self.median:
            node = node.left
            while node:
               
                if akey == node.key:
                    return node.value
                else:
                    if akey < node.key:
                        node = node.left
                    else:
                        node = node.right
        else:
            node = node.right
            while node:
                if akey == node.key:
                    return node.value
                else:
                    if akey < node.key:
                        node = node.left
                    else:
                        node = node.right
                       
                       
    def delete(self, akey):
        if akey < self.median:
            east = self.root_node.left
           
            if not east:
                # do nothing
                return None
            else:
                root = True
                temp = None
                #print(f" AKEY =  {akey}")
                while east:
                    left_child = east.left
                    right_child = east.right
                    #print(f"{east.key}")
                    if east.key == akey:
            # find the first center child/leaf that is none (left or right, I chose left)
            # make that the holder for the oposing child,    and the one you didn't use #becomes parent node
            # center branches are @east.left go right ---> (x) <--@east.right go left
                        if not left_child and not right_child:
                            print(right_child)
                            if not root:
                                #print(" temp    east")
                                #print(temp.left)
                                temp_left = temp.left
                                temp_right = temp.right
                                #print(temp.right)
                                #print(east)
                                #print(f"DELETE LEAF NODE {east}")
                                done = False
                                while not done:
                                    if temp_right:
                                        if temp_right.key == akey:
                                            temp.right = None
                                            print("temp.right = None")   
                                            print(temp)                               
                                            self._size -= 1
                                            done = True
                                            break
                                    elif temp_left:
                                        if temp_left.key == akey:
                                            temp.left = None
                                            print("temp.left = None")
                                            print(temp)
                                            self._size -= 1
                                            done = True
                                            break
                                    else: 
                                         #the temp has to have a right or left.  that is where 
                                         # the akey was found.
                                        print("this should not happen")
                                break
                            else:
                                self.root_node.left = None
                                self._size -= 1
                                break
                        else:
                            # it has a child link
                            left_child = east.left
                            right_child = east.right
                            if left_child and right_child:
                                new_left_child = east.left
                                #print(east)
                                #print(right_child)
                                # because parent node dictates the greatest value of
                                # the left's, right branch; x in branch will not be 
                                # greater then  the parent...
                                # we can be sure that however far down the branch we 
                                # go, the right_child which is greater then the parent_node, 
                                #can go after the preceeding nodes in the chain.
                                # It will be greater then them. Searching for numbers larger 
                                # then right.key will still lead to the right_child, 
                                # but it may be a longer path to it and it's child nodes
                                while new_left_child:
                                    if new_left_child.right == None:
                                        new_left_child.right = right_child
                                        east.key = left_child.key
                                        east.value = left_child.value
                                        east.left = left_child.left
                                        east.right = left_child.right
                                        self._size -= 1
                                        #print(new_left_child.right)
                                        break
                                    else:
                                        new_left_child = new_left_child.right
                                break
                            elif left_child and not right_child:
                                east.key = left_child.key
                                east.value = left_child.value
                                east.left = left_child.left
                                east.right = left_child.right
                                self._size -= 1
                                break
                            elif right_child and not left_child:
                                east.key = right_child.key
                                east.value = right_child.value
                                east.left = right_child.left
                                east.right = right_child.right
                                self._size -= 1
                                break
                            else:
                                print("error in while loop for :while east: delete(akey)")               
                                break
                    elif akey > east.key:
                        temp = east
                        root = False
                        east = east.right
                       
                    else:
                        temp = east
                        root = False
                        east = east.left
        else:
           # akey is > self.median
           # median should always be set to a float, such as 20.5 so that it can not
           # be duplicated assuming all entered key's are whole numbers.
           # and all keys go to proper side for example, if self.median 20.5,  
           # 20 will go left. or if 20 gets deleted, root is not involved.
                west = self.root_node.right
                root = True
                temp = None
                if not west:
                    return None
                else:
                    while west:
                        left_child = west.left
                        right_child = west.right
                        if akey == west.key:
                            # we've found the node to remove
                            if not left_child and not right_child:
                                if not root:
                                    temp_left = temp.left
                                    temp_right = temp.right
                                    done = False
                                    while not done:
                                        if temp_right:
                                            if temp_right.key == akey:
                                                temp.right = None                                   
                                                self._size -= 1
                                                #print("temp.right = None")
                                                #print(temp.right)
                                                done = True
                                                break
                                        if temp_left:
                                            print("running check left temp")
                                            if temp_left.key == akey:
                                                temp.left = None
                                                #print("temp.left = None")
                                                #print(temp.left)
                                                self._size -= 1
                                                done = True
                                                break
                                        else:
             ## the temp value if it is not root,  should be what was previous
             ## to the current east.  Therefore it cannot have no left or right.
                                            print("This should not happen.")
                                    break
                                else:
                                    self.root_node.right = None
                                    self._size -= 1
                                    break
                            elif left_child and not right_child:
                                west.key = left_child.key
                                west.value = left_child.value
                                west.left = left_child.left
                                west.right = left_child.right
                                self._size -= 1
                                break
                            elif right_child and not left_child:
                                west.key = right_child.key
                                west.value = right_child.value
                                west.left = right_child.left
                                west.right = right_child.right
                                self._size -= 1
                                break
                            elif right_child and left_child:
                                new_left_child = west.left
                                #print(right_child)
                                while new_left_child:
                                    if new_left_child.right == None:
                                        new_left_child.right = right_child
                                        west.key = left_child.key
                                        west.value = left_child.value
                                        west.left = left_child.left
                                        west.right = left_child.right
                                        #print(new_left_child)
                                        self._size -= 1
                                        break
                                    else:
                                        new_left_child = new_left_child.right
                                break
                            else:
                                print("error in while loop for :while west: delete(akey)")
                        elif akey > west.key:
                            temp = west
                            west = west.right
                            root = False
                        else:
                            temp = west
                            west = west.left
                            root = False
                           
               
    def dump(self):
       
        west = self.root_node.right
        east = self.root_node.left
        if east:
            print(f"East branch: {east}")
            self.recursDump(east)
            print("********** END EAST************")
           
        if west:
            print(f"West branch: {west}")
            self.recursDump(west)
            print("********** END WEST************")
           
       
           
    def recursDump(self, branch):
       
        if branch == None:
            print(" ")
        else:
            left_child = branch.left
            right_child = branch.right
            if left_child:
                print(left_child)
            if right_child:
                print(right_child)
            self.recursDump(right_child)
            self.recursDump(left_child)
            return branch
           
    def count(self):
        trunk = self.root_node
        keyslist = []
        result = self.recurs_helper(trunk, keyslist)
        #print(result)
        count = len(result)
        return count
       
    def make_key_list(self):
        # same as count different return
        trunk = self.root_node
        keyslist = []
        result = self.recurs_helper(trunk, keyslist)
        #print(result)
        return result
       
    def recurs_helper(self, branch, alist):
        if branch == None:
            pass
        else:
            left_sprout = branch.left
            right_sprout = branch.right
            if left_sprout:
                self.list_add(left_sprout, alist)
            if right_sprout:
                self.list_add(right_sprout, alist)
            self.recurs_helper(left_sprout, alist)
            self.recurs_helper(right_sprout, alist)
            return alist

                
           
    def list_add(self, something, alist):       
        if something:
            alist.append(something.key)
           


-- End code block ---



Comments

Post a Comment

Popular posts from this blog

JavaScript Ascii animation with while loops and console.log

I was working on figuring out while loops for an exercise in LearnJavaScriptTheHardWay  by Zed Shaw,  and I decided to do this: The red text console.logs were for debugging, and will take over the animation if the comments are removed. The bold red number is the point at which the loop stops.  My CPU didn't have too much trouble with that large number, but I'd recommend dialing it down if your CPU is slow. Also if your CPU is really fast, you'll have to change the pause to something much lower to see the animation better.  That too is in a loop, so the more that pause happens, the more loops your CPU is running.   Link: https://stackoverflow.com/questions/9006988/node-js-on-windows-how-to-clear-console To clear screen as described in link above, uncomment the bold purple comment I tried to comment the code to help learners see what I did,  any comments or suggestions, feel free to drop em in!        ...
Read more

playing with trigonometry sin in pygame

Image
Ok I am so far from understanding, so don't take this as any kind of math lesson. Also, every time I thought I knew what I was doing.... pygame would show me differently. Still a work in progress, but for now, something to play with. Update: SinWaveTime class added to produce that particular weaving effect Tinkering with the different sin wave variables: I wrote this piece separate from my 3D experiment to see how to manipulate the sin wave. While trying to use time as the factor to move my pygame draw circle on the x-axis, i got this crazy little doo-dad : I don't think it's drawing two circles at once, but if I figure out what the heck it's doing I'll let you know.  Or hey if you know, drop a comment.  I don't know if my comments are just not working, or no one wants to. So, here's some pygame code to play with the sin wave.  Alter the different variables to see it in action. picture of SinWave.move_with_time() see changes, SinWaveTime c...
Read more

JavaScript and a Matrix

Image
Screenshot of the code a 10 by 10 matrix Update 5/11/2021 I have successfully used the matrix to create a Snake game in Angular. See the live (Desktop only) game here: Firebase Deploy of Angular S N A K E Update 3/23/2021: I have changed the live version of the game to dynamically create the map for the minesweeper and this allowed for many open windows as to how I can upgrade and add onto the game. The easy version of the game allows people to learn and see how to form a strategy to defeat the original version of the game. There are sounds and options for game type and game size. Click on the options to turn the sound off if loud noises startle you as losing the games results in an explosion noise. Below is the link to the game, hosted on GitHub, and a GitHub link if you'd like to fork the code. Live Game: http...
Read more