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
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
Post a Comment