# by default, only the result of the last expression in a cell is displayed after evaluation.
# the following forces display of *all* self-standing expressions in a cell.
from IPython.core.interactiveshell import InteractiveShell
InteractiveShell.ast_node_interactivity = "all"
# most methods will be written recursively, but to avoid "slicing" the data structure
# we will hide the recursive func def within the non recursive one
# recursive one will need to define the subproblem, no extra arguments are needed on the user call
class BSTree:
class Node:
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right
def __init__(self):
self.size = 0
self.root = None
def add(self, val):
"""Adds `val` to this tree while maintaining BSTree properties."""
assert(val not in self)
pass
def __contains__(self, val):
"""Returns `True` if val is in this tree and `False` otherwise."""
pass
def __delitem__(self, val):
"""Removes `val` from this tree while maintaining BSTree properties."""
assert(val in self)
pass
def __iter__(self):
"""Returns an iterator over all the values in the tree, in ascending order."""
pass
def __len__(self):
return self.size
def pprint(self, width=64):
"""Attempts to pretty-print this tree's contents."""
height = self.height()
nodes = [(self.root, 0)]
prev_level = 0
repr_str = ''
while nodes:
n,level = nodes.pop(0)
if prev_level != level:
prev_level = level
repr_str += '\n'
if not n:
if level < height-1:
nodes.extend([(None, level+1), (None, level+1)])
repr_str += '{val:^{width}}'.format(val='-', width=width//2**level)
elif n:
if n.left or level < height-1:
nodes.append((n.left, level+1))
if n.right or level < height-1:
nodes.append((n.right, level+1))
repr_str += '{val:^{width}}'.format(val=n.val, width=width//2**level)
print(repr_str)
def height(self):
"""Returns the height of the longest branch of the tree."""
def height_rec(t):
if not t:
return 0
else:
return max(1+height_rec(t.left), 1+height_rec(t.right))
# left nsubtree height right subtree height
return height_rec(self.root)
t = BSTree()
t.root = BSTree.Node(5,
left=BSTree.Node(2),
right=BSTree.Node(10))
t.size = 3
t.height()
2
t.pprint()
5
2 10
t.height()
2
class BSTree(BSTree):
def __contains__(self, val):
def contains_rec(node):
if not node:
return False
elif node.val==val:
return True
elif node.val<val:
return contains_rec(node.right)
else:
return contains_rec(node.left)
return contains_rec(self.root)
t = BSTree()
t.root = BSTree.Node(5,
left=BSTree.Node(2),
right=BSTree.Node(10))
t.size = 3
5 in t
3 in t
True
False
class BSTree(BSTree):
def add(self, val):
assert(val not in self)
def add_rec(node):
if node:
if node.val>val: # node value is bigger than the insert value, go left
node.left = add_rec(node.left)
return node
else:
node.right = add_rec(node.right)
return node
else: # a leaf node called add_rec, my parent has to point to the new node inserted
return BSTree.Node(val, None, None)
self.root = add_rec(self.root)
self.size+=1
import random
t = BSTree()
vals = list(range(5))
random.shuffle(vals)
for x in vals:
t.add(x)
# t.pprint()
t.pprint()
# 0 1 2 4 5 # 3 must have been instert first, 1 or 3 inserted 2nd, 0 and 4 came later
4
0 -
- 3 - -
- - 2 - - - - -
- - - - 1 - - - - - - - - - - -
import random
t = BSTree()
vals = list(range(1, 10, 2))
random.shuffle(vals)
for x in vals:
t.add(x)
assert(all(x in t for x in range(1, 10, 2)))
assert(all(x not in t for x in range(0, 12, 2)))
class BSTree(BSTree):
def __delitem__(self, val):
assert(val in self) # if val is not in the BST, raise an exeption
# deal with relatively simple cases first!
def delitem_rec(node):
# search for val in BST
if node.val<val:
node.right = delitem_rec(node.right)
return node
elif node.val>val:
node.left = delitem_rec(node.left)
return node
else: # found the node with val
# case 1 node has no children
if not node.left and not node.right:
return None
# case 2 node has one child
elif node.left and not node.right:
return node.left
elif not node.left and node.right:
return node.right
# case 3 node has two children
else:
pass
# find the predecessor (or successor) and get a pointer to that node
# immediately smaller than val immediately larger than val
# go left, then go right right right etc
# the predecessor (or successor) MUST have 0 or 1 child (it cannot have 2)
# replace the node.val with predecessor.val, DELETE the predecessor node
self.root = delitem_rec(self.root)
self.size-=1
t = BSTree()
for x in [10, 5, 15, 2, 17]:
t.add(x)
t.pprint()
10
5 15
2 - - 17
del t[2]
t.pprint()
10
5 15
- - - 17
del t[17]
t.pprint()
10
5 15
del t[15]
t.pprint()
10
5 -
del t[5]
t.pprint()
10
del t[10]
t.pprint()
-
t = BSTree()
for x in [10, 5, 15, 2, 17]:
t.add(x)
t.pprint()
10
5 15
2 - - 17
del t[5]
t.pprint()
10
2 15
- - - 17
t = BSTree()
for x in [10, 5, 15, 2, 17]:
t.add(x)
del t[15]
t.pprint()
10
5 17
2 - - -
t = BSTree()
for x in [10, 5, 2, 7, 9, 8, 1, 15, 12, 18]:
t.add(x)
t.pprint()
class BSTree(BSTree):
def __delitem__(self, val):
assert(val in self) # if val is not in the BST, raise an exeption
# deal with relatively simple cases first!
def delitem_rec(node):
# search for val in BST
if node.val<val:
node.right = delitem_rec(node.right)
return node
elif node.val>val:
node.left = delitem_rec(node.left)
return node
else: # found the node with val
# case 1 node has no children
if not node.left and not node.right:
return None
# case 2 node has one child
elif node.left and not node.right:
return node.left
elif not node.left and node.right:
return node.right
# case 3 node has two children
else:
# find the predecessor (or successor) and get a pointer to that node
# immediately smaller than val immediately larger than val
# go left, then go right right right etc
# the predecessor (or successor) MUST have 0 or 1 child (it cannot have 2)
# replace the node.val with predecessor.val, DELETE the predecessor node
predNode=node.left
parentOfPredNode = node
while predNode.right:
parentOfPredNode=predNode
predNode=predNode.right
# predNode is pointing to predecessor node.val=predNode.val
# delete the predNode I NEED POINTER TO PARENT OF prednode
# parentOfPredNode is pointer to its parent
node.val=predNode.val
# delete the node predNode
# case where left child of node has no right subtree
if parentOfPredNode == node:
node.left=predNode.left # splice out prednode
else:
parentOfPredNode.right = predNode.left
return node
self.root = delitem_rec(self.root)
self.size-=1
t = BSTree()
for x in [10, 5, 2, 7, 9, 8, 1, 15, 12, 18]:
t.add(x)
t.pprint()
10
5 15
2 7 12 18
1 - - 9 - - - -
- - - - - - 8 - - - - - - - - -
del t[15]
t.pprint()
10
5 12
2 7 - 18
1 - - 9 - - - -
- - - - - - 8 - - - - - - - - -
del t[10]
t.pprint()
9
5 12
2 7 - 18
1 - - 8 - - - -
t = BSTree()
for x in [10, 5, 2, 7, 9, 8, 1, 15, 12, 18]:
t.add(x)
t.pprint()
10
5 15
2 7 12 18
1 - - 9 - - - -
- - - - - - 8 - - - - - - - - -
del t[5]
t.pprint()
10
2 15
1 7 12 18
- - - 9 - - - -
- - - - - - 8 - - - - - - - - -
t = BSTree()
for x in [10, 5, 2, 7, 9, 8, 1, 15, 12, 18]:
t.add(x)
del t[10]
t.pprint()
9
5 15
2 7 12 18
1 - - 8 - - - -
t = BSTree()
for x in [10, 5, 2, 7, 9, 8, 1, 15, 12, 18]:
t.add(x)
t.pprint()
10
5 15
2 7 12 18
1 - - 9 - - - -
- - - - - - 8 - - - - - - - - -
t.add(6)
t.add(7.5)
t.add(9.5)
t.add(6.5)
t.pprint()
10
5 15
2 7 12 18
1 - 6 9 - - - -
- - - - - 6.5 8 9.5 - - - - - - - -
- - - - - - - - - - - - 7.5- - - - - - - - - - - - - - - - - - -
t.add(9.3)
t.pprint()
10
5 15
2 7 12 18
1 - 6 9 - - - -
- - - - - 6.5 8 9.5 - - - - - - - -
- - - - - - - - - - - - 7.5- 9.3- - - - - - - - - - - - - - - - -
del t[10]
t.pprint()
9.5
5 15
2 7 12 18
1 - 6 9 - - - -
- - - - - 6.5 8 9.3 - - - - - - - -
- - - - - - - - - - - - 7.5- - - - - - - - - - - - - - - - - - -
class BSTree(BSTree):
def __iter__(self): # write as a generator, use yield instead of return
def iter_rec(node):
# if node exists
# visit left subtree (subproblem yield)
# visit root yield node.val
# visit right subtree (subproblem yield)
if node:
for x in iter_rec(node.left):
yield x
yield node.val
for x in iter_rec(node.right):
yield x
for x in iter_rec(self.root):
yield x
import random
t = BSTree()
vals = list(range(20))
random.shuffle(vals)
for x in vals:
t.add(x)
for x in t: #calls __iter__
print(x)
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
class BSTree(BSTree):
def __iter__(self): # write as a generator, use yield instead of return
def iter_rec(node):
# if node exists
# visit left subtree (subproblem yield)
# visit root yield node.val
# visit right subtree (subproblem yield)
if node:
yield from iter_rec(node.left)
yield node.val
yield from iter_rec(node.right)
for x in iter_rec(self.root):
yield x
import random
t = BSTree()
vals = list(range(20))
random.shuffle(vals)
for x in vals:
t.add(x)
for x in t: #calls __iter__
print(x)
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19