not a binary tree python
Ok, a little background. The lesson for class specifically said NOT to look up what a binary tree was, and to try and make one from his english description. I honestly didn't know what they were supposed to look like, just that they had a way of sorting stuff out as it went into the structure.... We needed a root BinaryTreeNode, then the BinaryTree, where we'd put the data... and it would have a set(), get(), delete(), and list()
the Node would have a key, value, left, right. and when the nodes go into the binary tree they would go straight into the structure where they belong, the root node would help decide where the new set data would go somehow.....Oh and it had something to do with that crazy Doubly Linked Dictionary we made...
Realized I didn't account for putting stuff in the list that matched the key of the root node.... adding that in. Going to pull out my string maker for some testing.
Maybe I wasn't so far off from what it's supposed to do after all.
I went and looked at:
wikipedia.. and wow... https://en.wikipedia.org/wiki/Binary_search_tree
I think it would have taken me weeks to follow that and try to guess what they are doing. I'm going to have to redo my code, cause... this ain't that...
So from the books description, this is the little monster I made:
NOT a binary tree:
from random import randint
class BSTreeNode(object):
def __init__(self, key, value, left, right):
self.key = key
self.value = value
self.left = left
self.right = right
def __repr__(self): # (<--left--[key: value]--right-->)
leftval = self.left and self.left.value or None
rightval = self.right and self.right.value or None
return f"left={leftval} [{self.key}:{self.value}] right={rightval}"
class BSTree(object):
def __init__(self, median):
self.median = median
self.root = BSTreeNode(self.median, 'root_node', None, None)
self.alist = []
self.alist.append(self.root)
def list_tree(self):
for i in self.alist:
print(i)
def get(self, akey):
if akey <= self.median:
i = self.alist.index(self.root)
print(i)
sideleft = len(self.alist) - i + 1
while i >=0:
node = self.alist[i]
if node.key == akey:
return self.alist[i]
i -= 1
elif akey >= self.median:
i = self.alist.index(self.root)
length = len(self.alist)
while i <= length:
node = self.alist[i]
if node.key == akey:
return self.alist[i]
i += 1
def set(self, akey, value):
if akey < self.median:
i = self.alist.index(self.root)
while i >= 0:
node = self.alist[i]
if node.left == None:
newnode = BSTreeNode(akey, value, None, self.alist[i])
node.left = newnode
self.alist.insert(i, newnode)
break
elif node.left != None:
i -= 1
node = self.alist[i]
if node.key <= akey:
print(akey)
if i - 1 < 0:
#beginning of list is bigger then node
newnode = BSTreeNode(akey, value, self.alist[i], self.alist[i+1])
node.right = newnode
nxt = self.alist[i+1]
nxt.left = newnode
self.alist.insert(i+1, newnode)
break
elif i - 1 > 0:
#not beginning, is bigger then node
newnode = BSTreeNode(akey, value, self.alist[i], self.alist[i+1])
node.right = newnode
nxt = self.alist[i+1]
nxt.left = newnode
self.alist.insert(i+1, newnode)
break
else:
i -= 1
elif akey > self.median:
i = self.alist.index(self.root)
print(f" elif alist index i = {i}")
length = len(self.alist) - 1
node = self.alist[i]
while i <= length:
print("greater while exec.")
if node.right == None:
newnode = BSTreeNode(akey, value, self.alist[i], None)
node.right = newnode
self.alist.append(newnode)
break
elif node.right != None:
i += 1
node = self.alist[i]
#print(node)
#print(akey)
if node.key >= akey:
if i + 1 >= length:
# if last right is bigger
newnode = BSTreeNode(akey, value, self.alist[i-1], self.alist[i])
prev = self.alist[i-1]
prev.right = newnode
node.left = newnode
self.alist.insert(i, newnode)
break
elif i + 1 <= length:
print(akey)
# if first-last right is bigger:
newnode = BSTreeNode(akey, value, self.alist[i-1], self.alist[i])
node.left = newnode
prev = self.alist[i-1]
prev.right = newnode
self.alist.insert(i, newnode)
break
else:
i += 1
else:
# akey is = to self.median:
# place the equivelant key on the left or right, depending on
# which side is smaller
i = self.alist.index(self.root)
length = len(self.alist)
rightside = len(self.alist) - i
leftside = 0 + i
if length == 1:
node = self.alist[i]
newnode = BSTreeNode(akey, value, None, self.alist[i])
node.left = newnode
self.alist.insert(i, newnode)
elif length > 1:
rightside = len(self.alist) - i
leftside = 0 + i
if leftside < rightside:
node = self.alist[i]
if node.left != None:
newnode = BSTreeNode(akey, value, self.alist[i-1], self.alist[i])
node.left = newnode
prev = self.alist[i-1]
prev.right = newnode
self.alist.insert(i, newnode)
else:
newnode = BSTreeNode(akey, value, None, self.alist[i])
node.left = newnode
self.alist.append(newnode)
elif rightside < leftside:
node = self.alist[i]
if node.right != None:
newnode = BSTreeNode(akey, value, self.alist[i-1], self.alist[i])
prev = self.alist[i-1]
prev.right = newnode
node.left = newnode
self.alist.insert(i, newnode)
else:
newnode = BSTreeNode(akey, value, self.alist[i], None)
node.right = newnode
self.alist.append(newnode)
else:
# both sides are equal: add to right:
i = self.alist.index(self.root)
node = self.alist[i]
if node.right != None:
i += 1
newnode = BSTreeNode(akey, value, self.alist[i-1], self.alist[i])
prev = self.alist[i-1]
nxt = self.alist[i]
prev.right = newnode
nxt.left = newnode
node.left = newnode
print(nxt)
self.alist.insert(i, newnode)
else:
newnode = BSTreeNode(akey, value, self.alist[i], None)
node.right = newnode
self.alist.append(newnode)
def delete(self, node):
i = self.alist.index(self.root)
# take a node out.
root = self.alist[i]
length = len(self.alist)
print(node.key)
if node.value == 'root_node':
print('DANGER! cannot remove root node!')
return None
if node.key <= root.key:
while i >= 0:
i -= 1
current = self.alist[i]
if current.left == None and current == node:
nxt = self.alist[i+1]
nxt.left = None
self.alist.remove(current)
break
elif current.left != None and current == node:
nxt = self.alist[i+1]
prev = self.alist[i-1]
nxt.left = prev
prev.right = nxt
self.alist.remove(current)
break
elif node.key >= root.key:
while i<= length - 1:
print(node.key)
i += 1
current = self.alist[i]
if current.right == None and current == node:
prev = self.alist[i-1]
prev.right = None
self.alist.remove(current)
break
elif current.right != None and current == node:
nxt = self.alist[i+1]
prev = self.alist[i-1]
nxt.left = prev
prev.right = nxt
self.alist.remove(current)
break
def remove(self, arbit):
print(arbit)
length = len(self.alist)
for i in range(0, length):
node = self.alist[i]
print(f"{node.value}:{arbit} < {i} > length = {length}")
if node.value == arbit:
self.delete(node)
# break is necessary!
# a deleted node will change the size of the list.
break
# manual test stuff. also tested with for loops and random integers
# I knew I was probably on the wrong track so didn't get too in depth
# no way it came this easy, this book has been a struggle, and this wasn't.
spam = BSTree(128)
spam.set(128, 'ii')
spam.set(99, 'j')
spam.set(300, 'p')
spam.set(128, 'umm')
spam.set(200, 'o')
spam.set(400, 'l')
spam.set(600, 'y')
spam.set(128, 'juj')
spam.set(430, 'oo')
spam.set(230, 'uu')
spam.set(100, 'tt')
spam.set(44, 'y7')
spam.set(111, 'pop')
spam.set(128, 'lil')
spam.set(128, 'trt')
spam.set(-45, 'olo')
spam.list_tree()
print("****************")
#spam.remove('y7')
#spam.remove('pop')
#spam.remove('l')
#spam.remove('y')
#spam.list_tree()
the Node would have a key, value, left, right. and when the nodes go into the binary tree they would go straight into the structure where they belong, the root node would help decide where the new set data would go somehow.....Oh and it had something to do with that crazy Doubly Linked Dictionary we made...
Realized I didn't account for putting stuff in the list that matched the key of the root node.... adding that in. Going to pull out my string maker for some testing.
Maybe I wasn't so far off from what it's supposed to do after all.
I went and looked at:
wikipedia.. and wow... https://en.wikipedia.org/wiki/Binary_search_tree
I think it would have taken me weeks to follow that and try to guess what they are doing. I'm going to have to redo my code, cause... this ain't that...
So from the books description, this is the little monster I made:
NOT a binary tree:
from random import randint
class BSTreeNode(object):
def __init__(self, key, value, left, right):
self.key = key
self.value = value
self.left = left
self.right = right
def __repr__(self): # (<--left--[key: value]--right-->)
leftval = self.left and self.left.value or None
rightval = self.right and self.right.value or None
return f"left={leftval} [{self.key}:{self.value}] right={rightval}"
class BSTree(object):
def __init__(self, median):
self.median = median
self.root = BSTreeNode(self.median, 'root_node', None, None)
self.alist = []
self.alist.append(self.root)
def list_tree(self):
for i in self.alist:
print(i)
def get(self, akey):
if akey <= self.median:
i = self.alist.index(self.root)
print(i)
sideleft = len(self.alist) - i + 1
while i >=0:
node = self.alist[i]
if node.key == akey:
return self.alist[i]
i -= 1
elif akey >= self.median:
i = self.alist.index(self.root)
length = len(self.alist)
while i <= length:
node = self.alist[i]
if node.key == akey:
return self.alist[i]
i += 1
def set(self, akey, value):
if akey < self.median:
i = self.alist.index(self.root)
while i >= 0:
node = self.alist[i]
if node.left == None:
newnode = BSTreeNode(akey, value, None, self.alist[i])
node.left = newnode
self.alist.insert(i, newnode)
break
elif node.left != None:
i -= 1
node = self.alist[i]
if node.key <= akey:
print(akey)
if i - 1 < 0:
#beginning of list is bigger then node
newnode = BSTreeNode(akey, value, self.alist[i], self.alist[i+1])
node.right = newnode
nxt = self.alist[i+1]
nxt.left = newnode
self.alist.insert(i+1, newnode)
break
elif i - 1 > 0:
#not beginning, is bigger then node
newnode = BSTreeNode(akey, value, self.alist[i], self.alist[i+1])
node.right = newnode
nxt = self.alist[i+1]
nxt.left = newnode
self.alist.insert(i+1, newnode)
break
else:
i -= 1
elif akey > self.median:
i = self.alist.index(self.root)
print(f" elif alist index i = {i}")
length = len(self.alist) - 1
node = self.alist[i]
while i <= length:
print("greater while exec.")
if node.right == None:
newnode = BSTreeNode(akey, value, self.alist[i], None)
node.right = newnode
self.alist.append(newnode)
break
elif node.right != None:
i += 1
node = self.alist[i]
#print(node)
#print(akey)
if node.key >= akey:
if i + 1 >= length:
# if last right is bigger
newnode = BSTreeNode(akey, value, self.alist[i-1], self.alist[i])
prev = self.alist[i-1]
prev.right = newnode
node.left = newnode
self.alist.insert(i, newnode)
break
elif i + 1 <= length:
print(akey)
# if first-last right is bigger:
newnode = BSTreeNode(akey, value, self.alist[i-1], self.alist[i])
node.left = newnode
prev = self.alist[i-1]
prev.right = newnode
self.alist.insert(i, newnode)
break
else:
i += 1
else:
# akey is = to self.median:
# place the equivelant key on the left or right, depending on
# which side is smaller
i = self.alist.index(self.root)
length = len(self.alist)
rightside = len(self.alist) - i
leftside = 0 + i
if length == 1:
node = self.alist[i]
newnode = BSTreeNode(akey, value, None, self.alist[i])
node.left = newnode
self.alist.insert(i, newnode)
elif length > 1:
rightside = len(self.alist) - i
leftside = 0 + i
if leftside < rightside:
node = self.alist[i]
if node.left != None:
newnode = BSTreeNode(akey, value, self.alist[i-1], self.alist[i])
node.left = newnode
prev = self.alist[i-1]
prev.right = newnode
self.alist.insert(i, newnode)
else:
newnode = BSTreeNode(akey, value, None, self.alist[i])
node.left = newnode
self.alist.append(newnode)
elif rightside < leftside:
node = self.alist[i]
if node.right != None:
newnode = BSTreeNode(akey, value, self.alist[i-1], self.alist[i])
prev = self.alist[i-1]
prev.right = newnode
node.left = newnode
self.alist.insert(i, newnode)
else:
newnode = BSTreeNode(akey, value, self.alist[i], None)
node.right = newnode
self.alist.append(newnode)
else:
# both sides are equal: add to right:
i = self.alist.index(self.root)
node = self.alist[i]
if node.right != None:
i += 1
newnode = BSTreeNode(akey, value, self.alist[i-1], self.alist[i])
prev = self.alist[i-1]
nxt = self.alist[i]
prev.right = newnode
nxt.left = newnode
node.left = newnode
print(nxt)
self.alist.insert(i, newnode)
else:
newnode = BSTreeNode(akey, value, self.alist[i], None)
node.right = newnode
self.alist.append(newnode)
def delete(self, node):
i = self.alist.index(self.root)
# take a node out.
root = self.alist[i]
length = len(self.alist)
print(node.key)
if node.value == 'root_node':
print('DANGER! cannot remove root node!')
return None
if node.key <= root.key:
while i >= 0:
i -= 1
current = self.alist[i]
if current.left == None and current == node:
nxt = self.alist[i+1]
nxt.left = None
self.alist.remove(current)
break
elif current.left != None and current == node:
nxt = self.alist[i+1]
prev = self.alist[i-1]
nxt.left = prev
prev.right = nxt
self.alist.remove(current)
break
elif node.key >= root.key:
while i<= length - 1:
print(node.key)
i += 1
current = self.alist[i]
if current.right == None and current == node:
prev = self.alist[i-1]
prev.right = None
self.alist.remove(current)
break
elif current.right != None and current == node:
nxt = self.alist[i+1]
prev = self.alist[i-1]
nxt.left = prev
prev.right = nxt
self.alist.remove(current)
break
def remove(self, arbit):
print(arbit)
length = len(self.alist)
for i in range(0, length):
node = self.alist[i]
print(f"{node.value}:{arbit} < {i} > length = {length}")
if node.value == arbit:
self.delete(node)
# break is necessary!
# a deleted node will change the size of the list.
break
# manual test stuff. also tested with for loops and random integers
# I knew I was probably on the wrong track so didn't get too in depth
# no way it came this easy, this book has been a struggle, and this wasn't.
spam = BSTree(128)
spam.set(128, 'ii')
spam.set(99, 'j')
spam.set(300, 'p')
spam.set(128, 'umm')
spam.set(200, 'o')
spam.set(400, 'l')
spam.set(600, 'y')
spam.set(128, 'juj')
spam.set(430, 'oo')
spam.set(230, 'uu')
spam.set(100, 'tt')
spam.set(44, 'y7')
spam.set(111, 'pop')
spam.set(128, 'lil')
spam.set(128, 'trt')
spam.set(-45, 'olo')
spam.list_tree()
print("****************")
#spam.remove('y7')
#spam.remove('pop')
#spam.remove('l')
#spam.remove('y')
#spam.list_tree()
Comments
Post a Comment