In [ ]:
def insert(x,nums):
if nums == []:
return [x]
elif x <= nums[0]:
return [x] + nums
else:
return [nums[0]] + insert(x,nums[1:])
def isort(nums):
if nums == []:
return []
else:
return insert(nums[0],isort(nums[1:]))
In [1]:
# implementing sets; so no duplicates
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def find_min(self):
if self.left is None:
return self.value
else:
return self.left.find_min()
# insert returns True or False depending on whether the value was inserted
def insert(self, x):
if x < self.value:
if self.left is None:
n = Node(x)
self.left = n
return True
else:
return self.left.insert(x)
elif x > self.value:
if self.right is None:
n = Node(x)
self.right = n
return True
else:
return self.right.insert(x)
else:
return False
def delete(self,x):
return self.delete_helper(x) is not None
def delete_helper(self,x):
if self.value == x: # found the value to delete
if self.left is None:
return self.right
elif self.right is None:
return self.left
else:
# find the smallest value in the right subtree
# and replace the current value with that value
# then delete that value from the right subtree
min_right = self.right.find_min()
self.value = min_right
self.right = self.right.delete_helper(min_right)
return self
elif x < self.value:
if self.left is None:
return None
else:
self.left = self.left.delete_helper(x)
return self
else:
if self.right is None:
return None
else:
self.right = self.right.delete_helper(x)
return self
def __str__(self):
if self.left is None and self.right is None:
return str(self.value)
elif self.left is None:
return str(self.value) + "," + str(self.right)
elif self.right is None:
return str(self.left) + "," + str(self.value)
else:
return str(self.left) + "," + str(self.value) + "," + str(self.right)
# 10,20,30,40,50,60,70,80,90,100
In [2]:
class BST:
def __init__(self):
self.root = None
def insert(self, x):
if self.root is None:
self.root = Node(x)
return True
else:
return self.root.insert(x)
def delete(self,x):
if self.root is None:
return False
else:
return self.root.delete(x)
def __str__(self):
return str(self.root)
In [4]:
t = BST()
t.insert(40)
t.insert(50)
t.insert(30)
t.insert(10)
t.insert(8)
print(t)
8,10,30,40,50
In [5]:
t.delete(30)
print(t)
8,10,40,50
In [1]:
str(None)
Out[1]:
'None'