tinker balanced right branch

So this is the code for what I tried to make...
I was trying to make the keys,  akey  coming into the tree be as balanced as possible.  After much head scratching, and a lot of walking away... I decided to set it aside and just do the tree without balancing it... and wow butter.  Especially after going through all this.
I think this worked, but there wasn't a great way to test it.  I had a print method to see what was going on, and it looked like what I wanted it to do, but I have so much to learn, and so much farther to go before I can properly tackle this.

 The whole code would be really confusing.... I had something completely different, and then altered just the right branch to try and figure it out .

tree = BinaryTree(20)
tree.set(21, 'spam')
tree.set(22, 'eggs')
tree.set(23, 'poltry')
tree.set(24, 'cheese')
tree.set(25, 'bubbles')
tree.set(30, 'pump')
tree.set(31, 'chicken')
tree.set(26, 'ham')
tree.set(28, 'coffee')
tree.set(27, 'lollipop')
tree.set(29, 'trollberrys')
tree.set(32, 'nob')
I should have made the print more so it printed farther, 27, 26 are in coffee, but they didn't print, my print didn't go that deep. I have to walk away from it or I'll never move on.










So a tinker,  trying to balance the incoming keys into the right branch of the binary tree:





## my tree initiates with a root_node,  that has a key, self.median.
## the self.median is set on creation of the tree.  So if you have a list that
## ranges from 1-100 you'd do:
##   tree = BinarySearchTree(50)
if akey > self.median:
            west = self.root_node.right
            if not west:
   #[<----- root --right branch (akey)-->][<--None----newnode(akey)--None->]
                newnode = BinaryTreeNode(akey, value, None, None)
                self.root_node.right = newnode
            elif west:
                #parent = west First Branch
                middle = int(self.median * 1.5)
                # if the new akey is closer to the median, replace the First branch

                if abs(middle - west.key) > abs(middle - akey):
                    print("swapping parent")
                    left_check = west.left
                    right_check = west.right
                    print(f"{akey}:{west.key} (({left_check} , {right_check}))")
                    if akey <= west.key:
                       
                        # replace original parent with new median range akey
                        if akey == west.key:
                            west.value = value
                        else:
                            # old parent is greater then new akey replacement
                            right_child = west
                            left_child = west.left
                            if left_child:
                                print("swapping parent node if-A")
                                newnode = BinaryTreeNode(akey, value, left_child, right_child )
                                self.root_node.right = newnode
                                west.left = None
                            else:
                                print(" swapping parent node if -B.")
                                # left_child is None:  Should I put left_child in anyways?
                                newnode = BinaryTreeNode(akey, value, None, right_child)
                                self.root_node.right = newnode
        #########O#############################################################################3       
                           
                    else:
                       
                        # akey is > then the west.key
                        if akey == west.key:
                            west.value = value
                        else:
                            #old parent is <  new akey parent
                            left_child = west
                            right_child = west.right
                            if right_child:
                                print(" swapping parent node else - A.")
                                newnode = BinaryTreeNode(akey, value, left_child, right_child)
                                west.right = None
                                self.root_node.right = newnode
                            else:
                                print(" swapping parent node else - B.")
                                newnode = BinaryTreeNode(akey, value, west, None)
                                self.root_node.right = newnode
                           
############O########################################################################33                       
                else:   
                               
                    while west:
                        # if the akey is less,  go along the childrens left path
                        # replace any greater nodes, or go till there is None

                        left_child = west.left
                        right_child = west.right   
                        if akey == west.key:
                            west.value = value
                            break
                           
                        if akey <= west.key:
                            print(f"{akey}:{west.key}")
                            if akey == west.key:
                                west.value = value
                                break
                            elif not left_child:       
                                print(f"no left child = {akey}")                   
                                newnode = BinaryTreeNode(akey, value, None, None)
                                west.left = newnode
                                break
                            else:
                                #current key > akey
                                # is the left_leaf smaller then akey?
                                # right_leaf will be bigger then akey

                                print(f" ESLE BLOCK {west.key}:{akey}")
                                if west.key == akey:
                                    west.value = value
                                    break
                                if left_child.key == akey:
                                    left_child.value = value
                                    break
                                elif left_child.key > akey:
                                    print(f" making a right key out of {left_child.key} new left = {akey}")
                                    # left_child is > akey... make left_child a right to new akey.
                                    # make akey new left to west

                                    left_leaf = west.left
                                    newnode = BinaryTreeNode(akey, value, None, left_leaf)
                                    west.left = newnode
                                    break                                   
                                else:
                                    west = west.left
                               
                               
                       
                        else:
                            print(f"{akey}:{west.key}")
                            # akey is >= west.key
                            left_child = west.left
                            right_child = west.right
                            if akey == west.key:
                                west.value = value
                                break
                            elif not right_child:
                                    print(f" no right_child, placing {akey}")                           
                                    newnode = BinaryTreeNode(akey, value, None, None)
                                    west.right = newnode
                                    break
                            else:
                                if right_child.key == akey:
                                    right_child.value = value
                                    break
                                elif right_child.key < akey:
                                    #akey > west.key  right leaf < akey
                                    # set akey as new right_child, make old child, a leaf on akey

                                    print(f"Making left_leaf a right_child of {akey}")
                                    right_leaf = west.right
                                    newnode = BinaryTreeNode(akey, value, right_leaf, None)
                                    west.right = newnode   
                                    break                       
                                else:
                                    west = west.right   
           
                   

Comments

Popular posts from this blog

JavaScript Ascii animation with while loops and console.log

playing with color in powershell python

playing with trigonometry sin in pygame