Revised Binary Tree, with the pytest file
Finally went through and fixed my spaghetti monster.
update(12/21/2020) moved code into 'code blocks'.
I will probably be moving this one next to My WordPress site: Nellie's Noodles
I might go back and add recursions, but for the purpose of showing readers how I made the code, while loops are much easier to follow, in my opinion.
The diagram of how I decided to do delete from a parent node with two children.
Python Binary Tree:
--Start Code Block--
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):
""" find proper placement in the tree for the given key:value pair
*replace value if key exists
*add node when in the proper place
"""
if akey < self.median:
# key is less then root, go left
east = self.root_node.left
if not east:
# east == None
# [None<---- _---="" newnode=""> None][<--left-- --right--="" root="">]
newnode = BinaryTreeNode(akey, value, None, None)
self.root_node.left = newnode
self._size += 1
else:
#east branch (possible parent) exists
while east:
# if akey exists, replace value
if akey == east.key:
east.value = value
break
elif east.key < akey:
# if akey is greater, go right
if east.right == None:
# dead end, place node
newnode = BinaryTreeNode(akey, value, None, None)
east.right = newnode
self._size += 1
break
else:
#Not a dead end continue
east = east.right
else:
# akey is less then branch key
if east.left == None:
#dead end place node
newnode = BinaryTreeNode(akey, value, None, None)
east.left = newnode
self._size += 1
break
else:
#not a dead end continue
east = east.left
if akey > self.median:
west = self.root_node.right
if not west:
# [<---- --right--="" root="">][None<---- _---="" newnode=""> None]
# West branch is empty, place node
newnode = BinaryTreeNode(akey, value, None, None)
self.root_node.right = newnode
self._size += 1
else:
# west branch is not empty, search for placement
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 _find_bottom(self, node, newleaf):
"""
with node being the right child of node to be deleted,
and node has a right child,
find the left most leaf that is empty (None)
"""
# change this to recurrsion when able
while node != None:
if node.left == None:
node.left = newleaf
break
else:
node = node.left
def _delete_node(self, node):
"""
return the replacement node, and wether or not the node is
the primary branch of the root_node
root_node primaries are changed in this function
"""
#print('activating _delete_node(node)')
root_left = self.root_node.left
root_right = self.root_node.right
primary_branch = False
# check if it is leaf
if node.right == None and node.left == None:
# LEAF
# replacement = None
if node == root_left:
self.root_node.left = None
primary_branch = True
elif node == root_right:
self.root_node.right = None
primary_branch = True
# return None for all other replacements that are not primary branches
return None, primary_branch
elif node.right == None and node.left != None:
# empty right slot, left becomes replacement
replacement = node.left
if node == root_left:
self.root_node.left = replacement
primary_branch = True
elif node == root_right:
self.root_node.right = replacement
primary_branch = True
return replacement, primary_branch
elif node.right != None and node.left == None:
# empty left slot
replacement = node.right
if node == root_left:
self.root_node.left = replacement
primary_branch = True
elif node == root_right:
self.root_node.right = replacement
primary_branch = True
return replacement, primary_branch
else:
# there are two children.
# first move the node.left to the right branches bottom most left leaf
# return replacement node which is node.right with the new leaf added
left_key = node.left.key
left_value = node.left.value
if node.left.left != None:
left_left = node.left.left
else:
left_left = None
if node.left.right != None:
left_right = node.left.right
else:
left_right = None
newnode = BinaryTreeNode(left_key, left_value, left_left, left_right)
right_branch = node.right
self._find_bottom(right_branch, newnode)
replacement = node.right
if node == root_left:
self.root_node.left = replacement
primary_branch = True
elif node == root_right:
self.root_node.right = replacement
primary_branch = True
return replacement, primary_branch
def delete(self, akey):
"""Remove any key;Value from tree, and replace it with proper
branch/parent or leaf where necessary """
if akey < self.median:
east = self.root_node.left
if not east:
# do nothing
# if east branch does not exist, key does not exist
#print('key not found: ', akey)
return None
else:
#run loop to find node
node = east
current = node
#print('else clause of delete activated less then median')
while node != None:
#print('while loop -- EAST')
if node.key == akey:
newnode, primary = self._delete_node(node)
if newnode == None and primary == False:
if current.left == node:
current.left = None
if current.right == node:
current.right = None
self._size -= 1
break
elif newnode != None and primary == False:
node.key = newnode.key
node.value = newnode.value
node.left = newnode.left
node.right = newnode.right
#print("deleting")
self._size -= 1
break
elif primary == True:
# this was a primary node branch
# _delete_node has replaced, removed necessary elements
self._size -= 1
break
else:
#print("else clause, while loop east of delete.")
#print('match found, nothing deleted')
break
elif node.key > akey:
#print("going left, node key is less then akey")
current = node
node = node.left
elif node.key < akey:
#print('going right, node key = ', node.key)
current = node
node = node.right
else:
print("node not found!")
if akey > self.median:
west = self.root_node.right
if not west:
# do nothing
# if west branch does not exist, key does not exist
return None
else:
#run loop to find node
node = west
current = node
#print('else clause of delete activated more then median')
while node != None:
#print('while loop -- WEST')
if node.key == akey:
newnode, primary = self._delete_node(node)
if newnode == None and primary == False:
if current.left == node:
current.left = None
if current.right == node:
current.right = None
self._size -= 1
break
elif newnode != None and primary == False:
node.key = newnode.key
node.value = newnode.value
node.left = newnode.left
node.right = newnode.right
#print("deleting")
self._size -= 1
break
elif primary == True:
# this was a primary node branch
# _delete_node has replaced, removed necessary elements
self._size -= 1
break
else:
#print('else clause in while loop West of delete.')
#print('match found, nothing deleted')
break
elif node.key > akey:
#print("going left, node key is greater then akey")
current = node
node = node.left
elif node.key < akey:
#print('going right, node key is less then akey')
current = node
node = node.right
else:
#print("node not found!")
break
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)
Pytest file
--Start Code Block--
from random import randint
from BST2 import BinaryTreeNode, BinaryTree
# I have to keep the build of lists under 3,000 total (laptop)
# my laptop starts to freak out about memory at 10,000
# it slows at 3000.
# recursion depth happens on count at 2000 items
def test_set():
oaktree = BinaryTree(50.5)
for i in range(0, 50):
oaktree.set(i, 'crunchy leaves')
assert oaktree._size == 50
for i in range(50, 100):
oaktree.set(i, 'acorns')
assert oaktree._size == 100
for i in range(0, 50):
oaktree.set(i, 'gypsy moths')
assert oaktree._size == 100
def test_count():
mapletree = BinaryTree(75.5)
for i in range(0, 100):
x = randint(1, 100)
mapletree.set(x, 'climbable')
assert mapletree._size == mapletree.count()
for i in range(0, 50):
x = randint(100, 150)
mapletree.set(x, 'shade')
assert mapletree._size == mapletree.count()
pinetree = BinaryTree(80.5)
for i in range(0, 160):
pinetree.set(i, 'christmas')
assert pinetree.count() == 160
pinetree.set(161, 'needles')
assert pinetree.count() == 161
def test_delete():
oaktree = BinaryTree(50.5)
for i in range(0, 50):
oaktree.set(i, 'crunchy leaves')
pinetree = BinaryTree(80.5)
for i in range(0, 160):
pinetree.set(i, 'christmas')
oaktree.delete(1)
assert oaktree.count() == 49
assert oaktree._size == 49
oaktree.delete(25)
assert oaktree.count() == 48
assert oaktree._size == 48
for i in range(0, 160):
pinetree.delete(i)
assert pinetree.count() == 0
assert pinetree._size == 0
for i in range(2, 25):
oaktree.delete(i)
assert oaktree.count() == 25
assert oaktree._size == 25
redwood = BinaryTree(11.5)
redlist = []
for i in range(0, 40):
x = randint(0, 40)
if x not in redlist:
redlist.append(x)
redwood.set(x, 'not 40')
assert redwood.count != 40
length_redlist = len(redlist)
assert redwood._size == length_redlist
for i in range(0, length_redlist):
redwood.delete(redlist[i])
assert redwood._size == 0
## was a FAIL...
## fixed. was removing the temp.left and temp.right
## only should remove the temp link that matched the (akey)
## that we want to delete.
assert redwood.count() == redwood._size
rightsided = BinaryTree(5.5)
righty = []
for i in range(0, 50):
rightsided.set(i, "slide to the right.")
righty.append(i)
assert len(righty) == rightsided._size
for i in range(0, 50):
rightsided.delete(i)
assert rightsided._size == 0
leftsided = BinaryTree(100.5)
lefty = []
for i in range(0, 50):
leftsided.set(i, "slide to the left")
lefty.append(i)
assert len(lefty) == leftsided._size
#### random leftsided rightsided
for i in range(0, 50):
x = randint(6, 50)
rightsided.set(x, "one hop this time")
righty2 = rightsided.make_key_list()
assert len(righty2) == rightsided._size
jump_jump = rightsided._size
for i in range(0, jump_jump):
x = righty2[i]
rightsided.delete(x)
assert rightsided._size == rightsided.count() == 0
for i in range(0, 50):
x = randint(0, 90)
leftsided.set(x, "cha-cha now ya'all.")
lefty2 = leftsided.make_key_list()
assert len(lefty2) == leftsided._size
cha_cha = leftsided._size
for i in range(0, cha_cha):
x = lefty2[i]
leftsided.delete(x)
assert leftsided._size == leftsided.count() == 0
### TEST A LARGE TREE ###
rainforest = BinaryTree(500.5)
for i in range(0, 1000):
x = randint(0, 1000)
rainforest.set(x, "oxygen")
rainy = rainforest.make_key_list()
assert len(rainy) == rainforest._size
cha_cha = rainforest._size
for i in range(0, cha_cha):
x = rainy[i]
rainforest.delete(x)
assert rainforest._size == rainforest.count() == 0
def test_make_list():
willow = BinaryTree(50.5)
messy_tree = []
### willow, lopsidded
for i in range(0, 50):
willow.set(i, "weeping")
messy_tree.append(i)
will_list = willow.make_key_list()
willow_size = willow.count()
assert len(will_list) == willow_size
for i in range(0, 50):
assert will_list[i] in messy_tree
## make_list_ appends from root.left, root.right down the branches
## the lists will have a different order, root.right will be second in the
## make_list, as it will most likely not be the second appended to manual list
for i in range(0, 50):
assert messy_tree[i] in will_list
## silver_spruce more even
silver_spruce = BinaryTree(40.5)
decor = []
for i in range(0, 82):
silver_spruce.set(i, 'firewood')
decor.append(i)
pine = silver_spruce.make_key_list()
spruce_count = silver_spruce.count()
assert len(pine) == spruce_count
for i in range(0, 82):
assert decor[i] in pine
for i in range(0, 82):
assert pine[i] in decor
### random made even tree
apple = BinaryTree(30.5)
pie = []
for i in range(0, 40):
x = randint(0, 62)
apple.set(x, "buggy")
pie.append(x)
juice = apple.make_key_list()
apple_size = apple.count()
assert apple_size == len(juice)
for i in range(0, apple_size):
assert juice[i] in pie
assert pie[i] in juice
def test_get():
oaktree = BinaryTree(-511.5)
oaklist = []
oaktree.set(-211, "spam1")
oaklist.append(-211)
oaktree.set(-739, "spam2")
oaklist.append(-739)
oaktree.set(-279, "spam3")
oaklist.append(-279)
oaktree.set(-417, "spam4")
oaklist.append(-417)
oaktree.set(-419, "spam5")
oaklist.append(-419)
oaktree.set(-969, "spam6")
oaklist.append(-969)
oaktree.set(-14, "spam7")
oaklist.append(-14)
oaktree.set(-715, "spam8")
oaklist.append(-715)
oaktree.set(-351, "spam9")
oaklist.append(-351)
oaktree.set(-349, "spam10")
oaklist.append(-349)
oaktree.set(-893, "spam11")
oaklist.append(-893)
oaktree.set(-672, "spam12")
oaklist.append(-672)
oaktree.set(-455, "spam13")
oaklist.append(-455)
oaktree.set(-21, "spam14")
oaklist.append(-21)
oaktree.set(-463, "spam15")
oaklist.append(-463)
######################
oaktree.set(-321, "spam16")
oaklist.append(-321)
oaktree.set(-6, "spam17")
oaklist.append(-6)
oaktree.set(-741, "spam18")
oaklist.append(-741)
oaktree.set(-494, "spam19")
oaklist.append(-494)
oaktree.set(-595, "spam20")
oaklist.append(-595)
oaktree.set(-452, "spam21")
oaklist.append(-452)
oaktree.set(-36, "spam22")
oaklist.append(-36)
oaktree.set(-358, "spam23")
oaklist.append(-358)
oaktree.set(-796, "spam24")
oaklist.append(-796)
oaktree.set(-625, "spam25")
oaklist.append(-625)
oaktree.set(-61, "spam26")
oaklist.append(-61)
oaktree.set(-329, "spam27")
oaklist.append(-329)
############################
oaktree.set(-35, "spam28")
oaklist.append(-35)
oaktree.set(-106, "spam29")
oaklist.append(-106)
oaktree.set(-393, "spam30")
oaklist.append(-393)
oaktree.set(-57, "spam31")
oaklist.append(-57)
oaktree.set(-314, "spam32")
oaklist.append(-314)
oaktree.set(-51, "spam33")
oaklist.append(-51)
oaktree.set(-62, "spam34")
oaklist.append(-62)
oaktree.set(-689, "spam35")
oaklist.append(-689)
oaktree.set(-366, "spam36")
oaklist.append(-366)
oaktree.set(-344, "spam37")
oaklist.append(-344)
oaktree.set(-463, "spam38")
oaklist.append(-463)
oaktree.set(-663, "spam39")
oaklist.append(-663)
oaktree.set(-318, "spam40")
oaklist.append(-318)
assert oaktree.get(-318) == "spam40"
assert oaktree.get(100) == None
assert oaktree.get(-393) == "spam30"
assert oaktree.get(-969) == "spam6"
assert oaktree.get(-6) =="spam17"
assert oaktree.get(-211) == "spam1"
oaktree.delete(-211)
oaktree.delete(-739)
assert oaktree.get(-279) == "spam3"
assert oaktree.get(-969) == "spam6"
assert oaktree.get(-211) == None
assert oaktree.get(-739) == None
#alteration
for akey in oaklist:
assert oaktree.get(akey) != None
oaktree.delete(-211)
oaktree.delete(-739)
assert oaktree.get(-211) == None
assert oaktree.get(-739) == None
Comments
Post a Comment