import numpy as np
import sys
LEFT = 0
RIGHT= 1
class Node:
def __init__(self, value, left_child=None, right_child=None):
self.value = value
self.children = [left_child, right_child]
def insertion(self, value):
direction = RIGHT if self.value < value else LEFT
if self.children[direction] == None:
self.children[direction] = Node(value)
else:
self.children[direction].insertion(value)
def insertion_random(self, value, direction=np.random.randint(0,2)):
if self.children[direction] == None:
self.children[direction] = Node(value)
else:
self.children[direction].insertion_random(value,np.random.randint(0,2))
def delete(self,value):
if self == None:
return
if self.value > value:
# This 'if' is a dirty trick to have access to node deletion one-step ahead of meeting the node
# Another option is to pass the father of the current node as argument, so to delete the child from the father
# [CAREFUL] "del self" only deletes a local pointer, not the node itself
if (self.children[LEFT] != None and self.children[LEFT].value == value and self.children[LEFT].children[LEFT]==None and self.children[LEFT].children[RIGHT]==None):
self.children[LEFT] = None
return
self.children[LEFT].delete(value)
if self.value < value:
# same as above
if (self.children[RIGHT] != None and self.children[RIGHT].value == value and self.children[RIGHT].children[LEFT]==None and self.children[RIGHT].children[RIGHT]==None):
self.children[RIGHT] = None
return
self.children[RIGHT].delete(value)
if self.value == value:
if self.children[LEFT] == None:
self.value = self.children[RIGHT].value
self.children = self.children[RIGHT].children
return
if self.children[RIGHT] == None:
self.value = self.children[LEFT].value
self.children = self.children[LEFT].children
return
# Finds the bottom-rightest value (i.e., the maximum) in the LEFT subtree
current_node=self.children[LEFT]
depth=0
while current_node.children[RIGHT]!=None:
previous_node = current_node
current_node = current_node.children[RIGHT]
depth+=1
# Switch the node of the found maximum (bottom-rightmost of LEFT subtree) with the node to "delete"
# and delete this bottom-rightmost node by removing it from its father (previous_node)
self.value = current_node.value
if depth == 0:
self.children[LEFT] = None
else:
previous_node.children[RIGHT] = None
return
def print_tree(self, level=0):
print(" |---" * level,self.value)
for child in self.children:
if child == None:
print(" |---" * (level+1),"*")
else:
child.print_tree(level+1)
treeSize = 10
values = np.random.randint(0,100,treeSize)
print("List of values: ",values)
tree_random = Node(values[0])
for v in values[1:]:
tree_random.insertion_random(v)
print("\nRandom tree:\n")
tree_random.print_tree()
print("\n\n")
tree_bst = Node(values[0])
for v in values[1:]:
tree_bst.insertion(v)
print("BST tree:\n")
tree_bst.print_tree()
The idea is the verification algorithm is to go down the tree and check that "left child root value" < "root value" < "right child root value".
To keep track at the same time of the minimum and maximum value in the tree, these must be propagated down the tree when checking its validity.
def verif(self):
if self == None:
return True,sys.maxsize,-sys.maxsize
if self.children[LEFT] == None and self.children[RIGHT] == None:
return True,self.value,self.value
if self.children[LEFT] == None:
vr = verif(self.children[RIGHT])
return vr[0] and (self.value<=vr[1]),min(self.value,vr[1]),max(self.value,vr[2])
if self.children[RIGHT] == None:
vl = verif(self.children[LEFT])
return vl[0] and (self.value>=vl[2]),min(self.value,vl[1]),max(self.value,vl[2])
vl = verif(self.children[LEFT])
vr = verif(self.children[RIGHT])
return vl[0] and vr[0] and (vl[2]<=self.value<=vr[1]),min(self.value,min(vl[1],vr[1])),max(self.value,max(vl[2],vr[2]))
verif=trace(verif)
print("Verif for tree_random: ",verif(tree_random))
print("\n\n")
print("Verif for tree_bst: ",verif(tree_bst))
There are two options: when the value to discard is found:
The cost can vary from $O(1)$ (actually $1$ operation) in the lucky case where the tree has an isolated child leaf and this value is to be removed. In the worst case, the full depth of the tree needs to be explored and this costs at most $O(n)$ if the tree is unluckily build always on the same side. Generally though, the average cost would be the depth of the tree which generically would be of order $O(\log n)$.
def delete(self,value):
if self == None:
return
if self.value > value:
# This 'if' is a dirty trick to have access to node deletion one-step ahead of meeting the node
# Another option is to pass the father of the current node as argument, so to delete the child from the father
# [CAREFUL] "del self" only deletes a local pointer, not the node itself
if (self.children[LEFT] != None and self.children[LEFT].value == value and self.children[LEFT].children[LEFT]==None and self.children[LEFT].children[RIGHT]==None):
self.children[LEFT] = None
return
self.children[LEFT].delete(value)
if self.value < value:
# same as above
if (self.children[RIGHT] != None and self.children[RIGHT].value == value and self.children[RIGHT].children[LEFT]==None and self.children[RIGHT].children[RIGHT]==None):
self.children[RIGHT] = None
return
self.children[RIGHT].delete(value)
if self.value == value:
if self.children[LEFT] == None:
self.value = self.children[RIGHT].value
self.children = self.children[RIGHT].children
return
if self.children[RIGHT] == None:
self.value = self.children[LEFT].value
self.children = self.children[LEFT].children
return
# Finds the bottom-rightest value (i.e., the maximum) in the LEFT subtree
current_node=self.children[LEFT]
depth=0
while current_node.children[RIGHT]!=None:
previous_node = current_node
current_node = current_node.children[RIGHT]
depth+=1
# Switch the node of the found maximum (bottom-rightmost of LEFT subtree) with the node to "delete"
# and delete this bottom-rightmost node by removing it from its father (previous_node)
self.value = current_node.value
if depth == 0:
self.children[LEFT] = current_node.children[LEFT]
else:
previous_node.children[RIGHT] = None
return
treeSize = 10
values = np.random.randint(0,100,treeSize)
print(values)
tree_bst = Node(values[0])
for v in values[1:]:
tree_bst.insertion(v)
print("Base tree:\n")
tree_bst.print_tree()
index = np.random.randint(treeSize)
tree_bst.delete(values[index])
print("\nTree after deletion of values[",index,"]=",values[index],"\n")
tree_bst.print_tree()
from functools import wraps
def trace(func):
func_name = func.__name__
separator = '| '
trace.recursion_depth = 0
@wraps(func)
def traced_func(*args, **kwargs):
# repeat separator N times (where N is recursion depth)
# `map(str, args)` prepares the iterable with str representation of positional arguments
# `", ".join(map(str, args))` will generate comma-separated list of positional arguments
# `"x"*5` will print `"xxxxx"` - so we can use multiplication operator to repeat separator
print(f'{separator * trace.recursion_depth}|-- {func_name}({", ".join(map(str, args))})')
# we're diving in
trace.recursion_depth += 1
result = func(*args, **kwargs)
# going out of that level of recursion
trace.recursion_depth -= 1
# result is printed on the next level
print(f'{separator * (trace.recursion_depth + 1)}|-- return {result}')
return result
return traced_func