I wrote a dictionary class of an avl search tree with values in leaves, but it is necessary to add immutability to it, that is, when deleting and adding anything (whether it is changing an element with an existing key or adding a new element), a new tree should be created based on an existing one. I can't figure out how to write the delete function. It should return a new tree based on the old one, but without the deleted element. I will be very grateful for any help(question of life and death)
class Node:
def __init__(self,key,value=None,left = None, right = None, inv = False):
self.key = key
self.value = value
if inv:
left,right = right,left
if left and right:
self.height = max(left.height,right.height)+1
if left:
self.height = left.height+1
if right:
self.height = right.height+1
else:
self.height = 1
self.left = left
self.right = right
class Dict:
def __init__(self):
self.root = None
self.len = 0
def __len__(self):
return self.len
def __getitem__(self,key):
if self.root:
return self.get(self.root,key)
raise KeyError()
def __contains__(self,key):
try:
self.__getitem__(key)
return True
except:
return False
def __setitem__(self,key,value):
if not self.root:
self.root = Node(key,value)
else:
self.root = self.put(self.root,key,value)
self.len+=1
def __delitem__(self,key):
if key not in self:
raise KeyError()
else:
self.root = self.delete(self.root,key)
self.len-=1
#def delete(self,tree,key):
#???
def height(self,tree): return tree.height if tree else 0
def children(self,tree, inv): return (tree.right,tree.left) if inv else (tree.left,tree.right)
def put(self,tree,key,value):
if not tree.left:
if key == tree.key:
self.len-=1
return Node(key,value,tree.left,tree.right)
elif key < tree.key:
return Node(tree.key,tree,Node(key,value),tree)
else:
return Node(tree.key, tree, tree, Node(key, value))
if tree.key == key:
self.put(tree.value,key,value)
return tree
inv = key < tree.key
left, right = self.children(tree, inv)
return self.avl(Node(tree.key, tree.value, left, self.put(right, key, value), inv), inv)
def get(self,tree,key):
if not tree.left:
if key != tree.key:
raise KeyError()
return tree.value
if key == tree.key:
return self.get(tree.value,key)
return self.get(self.children(tree, key < tree.key)[1], key)
def avl(self,tree,inv):
l,r = self.children(tree,inv)
if self.height(r) - self.height(l) < 2:
return tree
rl, rr = self.children(r, inv)
if self.height(rl) - self.height(rr) == 1:
r = self.reassoc(r, not inv)
return self.reassoc(Node(tree.key, tree.value, l, r, inv), inv)
def reassoc(self, tree, inv):
l, r = self.children(tree, inv)
rl, rr = self.children(r, inv)
return Node(r.key, r.value, Node(tree.key, tree.value, l, rl, inv), rr, inv)
def print_tree(tree, indent = ""):
if tree.right:
print_tree(tree.right, indent + " ")
if tree.left == tree.right:
print(f"{indent}{tree.key} -> {tree.value}")
else:
print(f"{indent}{tree.key}")
if tree.value is None:
raise ValueError
if tree.left:
print_tree(tree.left, indent + " ")
t = Dict()
for v, k in enumerate([5,7,2,1,3,6,2,7]):
t.__setitem__(k, v)
print_tree(t.root)
print()
