# 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
self.root = None
def add(self, val):
"""Adds `val` to this tree while maintaining BSTree properties."""
assert(val not in self) # enforces no duplicate values
pass
def __contains__(self, val):
"""Returns `True` if val is in this tree and `False` otherwise."""
# recursively, return True or Fals
def rec_contains(currentNode, val):
# base case currentNode is None, return false SMALLEST SUBPROBLEM
# base cases - found the val, return true
# recursive cases are go left or go right LARGEST SUBPROBLEM
if not currentNode: # if currentNode==None
return False
elif currentNode.val==val: #I know that currentNode is not None
return True
elif currentNode.val>val: #go left
return rec_contains(currentNode.left, val)
else:
return rec_contains(currentNode.right, val)
return rec_contains(self.root, val)
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): # distance to furthest leaf
# runtime in terms of the number of nodes in the BST
# O(size(BST)) O(n)
"""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
2 in t
5 in t
10 in t
11 in t
8 in t
4 in t
-1 in t
True
True
True
False
False
False
False
class BSTree(BSTree):
def __contains__(self, val):
pass
t = BSTree()
t.root = BSTree.Node(5,
left=BSTree.Node(2),
right=BSTree.Node(10))
t.size = 3
5 in t
class BSTree(BSTree): #inheritance
def add(self, val):
assert(val not in self)
# recursively
def rec_add(currentNode, val): # returns the child node I was at
if not currentNode: # its a None
# create a new node, return a pointer to that new node to whoever called me
return BSTree.Node(val)
# i know I have a currentNode
elif currentNode.val>val: #go left
currentNode.left=rec_add(currentNode.left,val)
return currentNode
else: #go right
currentNode.right=rec_add(currentNode.right,val)
return currentNode
self.root=rec_add(self.root, val)
self.size+=1
import random
t = BSTree()
vals = list(range(5))
random.shuffle(vals)
for x in vals:
t.add(x)
t.pprint()
3
1 4
0 2 - -
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)
def rec_del(currentNode):
# we do not need to check currentNode==None because I know the val is in the BST
if currentNode.val>val: #haven't found it, going left
currentNode.left=rec_del(currentNode.left)
return currentNode
elif currentNode.val<val: #haven't found it, going right
currentNode.right=rec_del(currentNode.right)
return currentNode
else: #if currentNode.val==val:
#easy cases first
# case #1 the node with "val" in it has no children
if not currentNode.left and not currentNode.right:
return None
# case #2 the node with "val" in it has one children
else:
pass
# case #3 the node with "val" in it has two children
self.root=rec_del(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()
-
class BSTree(BSTree):
def __delitem__(self, val):
assert(val in self)
def rec_del(currentNode):
# we do not need to check currentNode==None because I know the val is in the BST
if currentNode.val>val: #haven't found it, going left
currentNode.left=rec_del(currentNode.left)
return currentNode
elif currentNode.val<val: #haven't found it, going right
currentNode.right=rec_del(currentNode.right)
return currentNode
else: #if currentNode.val==val:
#easy cases first
# case #1 the node with "val" in it has no children
if not currentNode.left and not currentNode.right:
return None
# case #2 the node with "val" in it has one children
elif not currentNode.left and currentNode.right:
return currentNode.right # grandchild that exists
elif currentNode.left and not currentNode.right:
return currentNode.left # grandchild that exists
# case #3 the node with "val" in it has two children
self.root=rec_del(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[5]
t.pprint()
10
2 15
- - - 17
del t[15]
t.pprint()
10
2 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):
assert(val in self)
# fully working delete
def rec_del(currentNode):
# we do not need to check currentNode==None because I know the val is in the BST
if currentNode.val>val: #haven't found it, going left
currentNode.left=rec_del(currentNode.left)
return currentNode
elif currentNode.val<val: #haven't found it, going right
currentNode.right=rec_del(currentNode.right)
return currentNode
else: #if currentNode.val==val:
#easy cases first
# case #1 the node with "val" in it has no children
if not currentNode.left and not currentNode.right:
return None
# case #2 the node with "val" in it has one children
elif not currentNode.left and currentNode.right:
return currentNode.right # grandchild that exists
elif currentNode.left and not currentNode.right:
return currentNode.left # grandchild that exists
else:
# case #3 the node with "val" in it has two children
#find the node with the predecessor value (the largest item smaller than "val")
# iteratively, go to left subtree, everything in left subtree is smaller than "val"
# then find max in that left subtree, go right right right ....
parent_pred_node=currentNode
pred_node=currentNode.left
if not pred_node.right: # predecessor is immediately to left of current Node
currentNode.val=pred_node.val
if not pred_node.left:
parent_pred_node.left=None
else:
parent_pred_node.left=pred_node.left
else:
while pred_node.right:
parent_pred_node=pred_node
pred_node=pred_node.right
# pred_node points to the node with the val being the predecessor of "val"
currentNode.val=pred_node.val
#now delete the pred_node, that pred_node cannot have a right
# it's left might be None or might be another node
if not pred_node.left:
parent_pred_node.right=None
else:
parent_pred_node.right=pred_node.left
#parent_pred_node=pred_node.left
return currentNode # in case 3 I do not delete currentNode, I need to return it
# so parent can continue to point to it
self.root=rec_del(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)
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 - - - -
class BSTree(BSTree):
def __iter__(self):
def iter_rec(node): # in python we use yield not return/output
if node:
# call iter_rec(node.left)
yield from iter_rec(node.left)
yield node.val
# call iter_rec(node.right)
yield from iter_rec(node.right)
# call iter_rec(self.root)
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: # calling __iter
print(x)
0
- 7
- - 1 11
- - - - - 5 10 19
- - - - - - - - - - 3 6 8 - 18 -
- - - - - - - - - - - - - - - - - - - - 2 4 - - - 9 - - 17- - -
--------------------------------------------------------15-------
----------------------------------------------------------------------------------------------------------------1316--------------
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------1214------------------------------
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
t = BSTree() # keys are 0 to 100
t.add(50)
t.add(70)
t.add(85)
t.add(40)
t.add(25)
t.add(45)
t.pprint()
50
40 70
25 45 - 85
t = BSTree() # keys are 0 to 100
t.add(50)
t.add(40)
t.add(25)
t.add(45)
t.add(70)
t.add(85)
t.pprint()
50
40 70
25 45 - 85
t = BSTree() # keys are 0 to 100
t.add(59)
t.add(30)
t.add(40)
t.add(35)
t.add(32)
t.add(31)
t.pprint()
59
30 -
- 40 - -
- - 35 - - - - -
- - - - 32 - - - - - - - - - - -
- - - - - - - - 31- - - - - - - - - - - - - - - - - - - - - - -
t = BSTree() # keys are 0 to 100
t.add(1)
t.add(2)
t.add(3)
t.add(4)
t.add(5)
t.add(6)
t.pprint()
1
- 2
- - - 3
- - - - - - - 4
- - - - - - - - - - - - - - - 5
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 6
t = BSTree() # keys are 0 to 100
t.add(6)
t.add(5)
t.add(4)
t.add(3)
t.add(2)
t.add(1)
t.pprint()
6
5 -
4 - - -
3 - - - - - - -
2 - - - - - - - - - - - - - - -
1 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -