# 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"
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 # how many nodes in the BST
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):
# b=BSTree()
# if 5 in b
"""Returns `True` if val is in this tree and `False` otherwise."""
def contains_rec(node):
# node is None, node.val==val node.val>val node.val<val
if not node: # if node==None
return False
#node exists
elif node.val==val:
return True
elif node.val>val:
return contains_rec(node.left)
else:
return contains_rec(node.right)
return contains_rec(self.root)
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): #O(n) number of nodes in BST
"""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))
return height_rec(self.root)
t = BSTree()
t.root = BSTree.Node(5,
left=BSTree.Node(2),
right=BSTree.Node(10))
t.size = 3
t.pprint()
5
2 10
t.height()
2
t = BSTree()
t.root = BSTree.Node(5,
left=BSTree.Node(2),
right=BSTree.Node(10))
t.size = 3
5 in t
12 in t
2 in t
10 in t
1 in t
3 in t
8 in t
13 in t
True
False
True
True
False
False
False
False
class BSTree(BSTree):
def add(self, val):
assert(val not in self) # no duplicates allowed
def add_rec(node): # returns a pointer to the child node
# it traverses to
# if node exists, determine if recurse left or right
# if node does not exist, create new node, insert val
# return pointer to the new node
if not node:
return BSTree.Node(val) #new node left and right are None
# return a pointer to the new node
# node exists
elif node.val>val: # go left
node.left=add_rec(node.left)
return node
else:
node.right=add_rec(node.right)
return node
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()
1
0 2
- - - 3
- - - - - - - 4
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 add_alternative(self, val):
assert(val not in self) # no duplicates allowed
def add_alternative_rec(node):
# recursive calls do not return anything
# require every time I call this "node" exists
if node.val>val: # go left
if node.left:
add_alternative_rec(node.left)
else:
node.left=BSTree.Node(val, None, None)
else: #go right
if node.right:
add_alternative_rec(node.right)
else:
node.right=BSTree.Node(val, None, None)
if self.root:
add_alternative_rec(self.root)
else:
self.root=BSTree.Node(val, None, None)
self.size+=1
import random
t = BSTree()
vals = list(range(5))
random.shuffle(vals)
for x in vals:
t.add_alternative(x)
t.pprint()
2
1 3
0 - - 4
class BSTree(BSTree):
def __delitem__(self, val): # del t[4]
assert(val in self)
# deal with relatively simple cases first!
def delitem_rec(node):
if node.val>val: # go left
node.left=delitem_rec(node.left)
return node
elif node.val<val: # go right
node.right=delitem_rec(node.right)
return node
else: # we found the node to delete
# case #1 no children
if not node.left and not node.right:
return None
# case #2 1 child to the left
elif node.left and not node.right:
return node.left
# case #2 1 child to the right
elif not node.left and node.right:
return node.right
else: #case 3
pass
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[5]
t.pprint()
10
- 15
- - - 17
del t[17]
t.pprint()
10
- 15
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
del t[15]
t.pprint()
10
2 17
del t[2]
del t[10]
t.pprint()
17
t = BSTree()
for x in [10, 5, 15, 2, 17]:
t.add(x)
del t[15]
t.pprint()
class BSTree(BSTree):
def __delitem__(self, val): # del t[4]
assert(val in self)
# deal with relatively simple cases first!
def delitem_rec(node):
if node.val>val: # go left
node.left=delitem_rec(node.left)
return node
elif node.val<val: # go right
node.right=delitem_rec(node.right)
return node
else: # we found the node to delete
# case #1 no children
if not node.left and not node.right:
return None
# case #2 1 child to the left
elif node.left and not node.right:
return node.left
# case #2 1 child to the right
elif not node.left and node.right:
return node.right
else: #case 3
# node is pointer to the node with value to delete
# find it's predecssor node, it must be below it
# the predecessor might not be a leaf
# find predessor by go left, then go right right ...
# as we are traversing, watch for None
# swap predecessor value with node value
# delete predecessor
x = node.left # can x be None? NO, case 3 says node has 2 children
# if x has no right, x is already the predecessor
if not x.right:
node.val=x.val
node.left=x.left
else: # x has a right, walk down it
# maintaining 2 pointers
y = x.right
while x.right.right:
x=y
y=y.right
# when done, y points to predecssor, x points to its parent
node.val=y.val
# delete node y (it can only have a left child)
x.right=y.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 - - - - - - - - -
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)
t.pprint()
10
5 15
2 7 12 18
1 - - 9 - - - -
- - - - - - 8 - - - - - - - - -
del t[10]
t.pprint()
9
5 15
2 7 12 18
1 - - 8 - - - -
# if t:
# traverse(t.left, fn)
# fn(t.val) CHANGE THIS TO YIELD
# traverse(t.right,fn)
class BSTree(BSTree):
def __iter__(self):
def iter_rec(node):
if node:
yield from iter_rec(node.left)
yield node.val
yield from iter_rec(node.right)
yield from iter_rec(self.root)
import random
t = BSTree()
vals = list(range(20))
random.shuffle(vals)
for x in vals:
t.add(x)
t.pprint()
for x in t:
print(x)
8
3 15
1 4 13 19
0 2 - 6 12 14 18 -
- - - - - - 5 7 10 - - - 16 - - -
- - - - - - - - - - - - - - - - 9 11- - - - - - - 17- - - - - -
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19