We discussed two data structures - Linked Lists and Binary Search Trees.
from IPython.core.interactiveshell import InteractiveShell
InteractiveShell.ast_node_interactivity = "all"
## This file contains functions for the representation of binary trees.
## used in class Binary_search_tree's __repr__
## Written by a former student in the course - thanks to Amitai Cohen
## No need to fully understand this code
def printree(t, bykey = True):
"""Print a textual representation of t
bykey=True: show keys instead of values"""
#for row in trepr(t, bykey):
# print(row)
return trepr(t, bykey)
def trepr(t, bykey = False):
"""Return a list of textual representations of the levels in t
bykey=True: show keys instead of values"""
if t==None:
return ["#"]
thistr = str(t.key) if bykey else str(t.val)
return conc(trepr(t.left,bykey), thistr, trepr(t.right,bykey))
def conc(left,root,right):
"""Return a concatenation of textual represantations of
a root node, its left node, and its right node
root is a string, and left and right are lists of strings"""
lwid = len(left[-1])
rwid = len(right[-1])
rootwid = len(root)
result = [(lwid+1)*" " + root + (rwid+1)*" "]
ls = leftspace(left[0])
rs = rightspace(right[0])
result.append(ls*" " + (lwid-ls)*"_" + "/" + rootwid*" " + "|" + rs*"_" + (rwid-rs)*" ")
for i in range(max(len(left),len(right))):
row = ""
if i<len(left):
row += left[i]
else:
row += lwid*" "
row += (rootwid+2)*" "
if i<len(right):
row += right[i]
else:
row += rwid*" "
result.append(row)
return result
def leftspace(row):
"""helper for conc"""
#row is the first row of a left node
#returns the index of where the second whitespace starts
i = len(row)-1
while row[i]==" ":
i-=1
return i+1
def rightspace(row):
"""helper for conc"""
#row is the first row of a right node
#returns the index of where the first whitespace ends
i = 0
while row[i]==" ":
i+=1
return i
A link to special method names in python: http://getpython3.com/diveintopython3/special-method-names.html
A linked list is a linear data structure (i.e. - nodes can be accessed one after the other). The list is composed of nodes, where each node contains a value and a "pointer" to the next node in the list.
Linked lists support operations such as insertion, deletion, search and many more.
class Node():
def __init__(self, val):
self.value = val
self.next = None
def __repr__(self):
#return "[" + str(self.value) + "," + str(id(self.next))+ "]"
#for today's recitation, we print the id of self instead of self.next
return "[" + str(self.value) + "," + str(id(self))+ "]"
class Linked_list():
def __init__(self, seq=None):
self.next = None
self.len = 0
if seq != None:
for x in seq[::-1]:
self.add_at_start(x)
def __repr__(self):
out = ""
p = self.next
while p != None:
out += str(p) + " " #str envokes __repr__ of class Node
p = p.next
return out
def __len__(self):
''' called when using Python's len() '''
return self.len
def add_at_start(self, val):
''' add node with value val at the list head '''
p = self
tmp = p.next
p.next = Node(val)
p.next.next = tmp
self.len += 1
def add_at_end(self, val):
''' add node with value val at the list tail '''
p = self
while (p.next != None):
p = p.next
p.next = Node(val)
self.len += 1
def insert(self, loc, val):
''' add node with value val after location 0<=loc<len of the list '''
assert 0 <= loc < len(self)
p = self
for i in range(0, loc):
p = p.next
tmp = p.next
p.next = Node(val)
p.next.next = tmp
self.len += 1
def __getitem__(self, loc):
''' called when using L[i] for reading
return node at location 0<=loc<len '''
assert 0 <= loc < len(self)
p = self.next
for i in range(0, loc):
p = p.next
return p
def __setitem__(self, loc, val):
''' called when using L[loc]=val for writing
assigns val to node at location 0<=loc<len '''
assert 0 <= loc < len(self)
p = self.next
for i in range(0, loc):
p = p.next
p.value = val
return None
def find(self, val):
''' find (first) node with value val in list '''
p = self.next
# loc = 0 # in case we want to return the location
while p != None:
if p.value == val:
return p
else:
p = p.next
#loc=loc+1 # in case we want to return the location
return None
def delete(self, loc):
''' delete element at location 0<=loc<len '''
assert 0 <= loc < len(self)
p = self
for i in range(0, loc):
p = p.next
# p is the element BEFORE loc
p.next = p.next.next
self.len -= 1
def insert_ordered(self, val):
''' assume self is an ordered list,
insert Node with val in order '''
p = self
q = self.next
while q != None and q.value < val:
p = q
q = q.next
newNode = Node(val)
p.next = newNode
newNode.next = q
self.len += 1
def find_ordered(self, val):
''' assume self is an ordered list,
find Node with value val '''
p = self.next
while p != None and p.value < val:
p = p.next
if p != None and p.value == val:
return p
else:
return None
Converting a string to a list
L= Linked_list("abc")
L
[a,91843024] [b,91843088] [c,91842992]
memory view
Adding elements one by one. Try using Python tutor.
l = Linked_list()
l.add_at_start("a")
l.add_at_start("b")
l
[b,91843568] [a,91843664]
Method | List | Linked list |
init | $O(1)$ | $O(1)$ |
init with $k$ items | $O(k)$ | $O(k)$ |
for the rest of the methods we assume that the structure contains $n$ items | ||
add at start | $O(n)$ | $O(1)$ |
add at end | $O(1)$ | $O(n)$ |
$lst[k]$ (get the $k$th item) | $O(1)$ | $O(k)$ |
delete $lst[k]$ | $O(n-k)$ | $O(k)$ |
Reversing a linked list in $O(1)$ additional memory. See the code and demo here
class Node():
def __init__(self, val):
self.value = val
self.next = None
def __repr__(self):
#return "[" + str(self.value) + "," + str(id(self.next))+ "]"
#for today's recitation, we print the id of self instead of self.next
return "[" + str(self.value) + "," + str(id(self))+ "]"
class Linked_list():
def __init__(self, seq=None):
self.next = None
self.len = 0
if seq != None:
for x in seq[::-1]:
self.add_at_start(x)
def __repr__(self):
out = ""
p = self.next
while p != None:
out += str(p) + " " #str envokes __repr__ of class Node
p = p.next
return out
def __len__(self):
''' called when using Python's len() '''
return self.len
def add_at_start(self, val):
''' add node with value val at the list head '''
p = self
tmp = p.next
p.next = Node(val)
p.next.next = tmp
self.len += 1
def add_at_end(self, val):
''' add node with value val at the list tail '''
p = self
while (p.next != None):
p = p.next
p.next = Node(val)
self.len += 1
def insert(self, loc, val):
''' add node with value val after location 0<=loc<len of the list '''
assert 0 <= loc < len(self)
p = self
for i in range(0, loc):
p = p.next
tmp = p.next
p.next = Node(val)
p.next.next = tmp
self.len += 1
def __getitem__(self, loc):
''' called when using L[i] for reading
return node at location 0<=loc<len '''
assert 0 <= loc < len(self)
p = self.next
for i in range(0, loc):
p = p.next
return p
def __setitem__(self, loc, val):
''' called when using L[loc]=val for writing
assigns val to node at location 0<=loc<len '''
assert 0 <= loc < len(self)
p = self.next
for i in range(0, loc):
p = p.next
p.value = val
return None
def find(self, val):
''' find (first) node with value val in list '''
p = self.next
# loc = 0 # in case we want to return the location
while p != None:
if p.value == val:
return p
else:
p = p.next
#loc=loc+1 # in case we want to return the location
return None
def delete(self, loc):
''' delete element at location 0<=loc<len '''
assert 0 <= loc < len(self)
p = self
for i in range(0, loc):
p = p.next
# p is the element BEFORE loc
p.next = p.next.next
self.len -= 1
def insert_ordered(self, val):
''' assume self is an ordered list,
insert Node with val in order '''
p = self
q = self.next
while q != None and q.value < val:
p = q
q = q.next
newNode = Node(val)
p.next = newNode
newNode.next = q
self.len += 1
def find_ordered(self, val):
''' assume self is an ordered list,
find Node with value val '''
p = self.next
while p != None and p.value < val:
p = p.next
if p != None and p.value == val:
return p
else:
return None
def reverse(self):
prev = None
curr = self.next
while curr != None:
tmp = curr.next
curr.next = prev
prev = curr
curr = tmp
self.next = prev
ll = Linked_list("abc")
ll
ll.reverse()
ll
[a,91941296] [b,91941232] [c,91941200]
[c,91941200] [b,91941232] [a,91941296]
Recall the (recursive) definition of a binary tree:
A binary search tree is a binary tree whose nodes have values, with the additional property that if $v$ is a node then all nodes in the left subtree of $v$ have keys smaller than $v.key$ and all those in the right subtree of $v$ have keys larger than $v.key$.
Binary search trees support operations such as insertion, deletion, search and many more.
class Tree_node():
def __init__(self, key, val):
self.key = key
self.val = val
self.left = None
self.right = None
def __repr__(self):
return "(" + str(self.key) + ":" + str(self.val) + ")"
class Binary_search_tree():
def __init__(self):
self.root = None
def __repr__(self): #no need to understand the implementation of this one
out = ""
for row in printree(self.root): #need printree.py file
out = out + row + "\n"
return out
def lookup(self, key):
''' return node with key, uses recursion '''
def lookup_rec(node, key):
if node == None:
return None
elif key == node.key:
return node
elif key < node.key:
return lookup_rec(node.left, key)
else:
return lookup_rec(node.right, key)
return lookup_rec(self.root, key)
def insert(self, key, val):
''' insert node with key,val into tree, uses recursion '''
def insert_rec(node, key, val):
if key == node.key:
node.val = val # update the val for this key
elif key < node.key:
if node.left == None:
node.left = Tree_node(key, val)
else:
insert_rec(node.left, key, val)
else: #key > node.key:
if node.right == None:
node.right = Tree_node(key, val)
else:
insert_rec(node.right, key, val)
return
if self.root == None: #empty tree
self.root = Tree_node(key, val)
else:
insert_rec(self.root, key, val)
def minimum(self):
''' return node with minimal key '''
if self.root == None:
return None
node = self.root
left = node.left
while left != None:
node = left
left = node.left
return node
def depth(self):
''' return depth of tree, uses recursion'''
def depth_rec(node):
if node == None:
return -1
else:
return 1 + max(depth_rec(node.left), depth_rec(node.right))
return depth_rec(self.root)
def size(self):
''' return number of nodes in tree, uses recursion '''
def size_rec(node):
if node == None:
return 0
else:
return 1 + size_rec(node.left) + size_rec(node.right)
return size_rec(self.root)
def inorder(self):
'''prints the keys of the tree in a sorted order'''
def inorder_rec(node):
if node == None:
return
inorder_rec(node.left)
print(node.key)
inorder_rec(node.right)
inorder_rec(self.root)
t = Binary_search_tree()
t.insert(4,'a')
t.insert(2,'a')
t.insert(6,'a')
t.insert(1,'a')
t.insert(3,'a')
t.insert(5,'a')
t.insert(7,'a')
t
t.inorder()
4 ______/ |______ 2 6 __/ |__ __/ |__ 1 3 5 7 / | / | / | / | # # # # # # # #
1 2 3 4 5 6 7
Claim: An inorder traversal of a binary search tree prints the keys in ascending order.
Proof, by complete induction on the size of tree:
More information on complete induction: https://en.wikipedia.org/wiki/Mathematical_induction#Complete_(strong)_induction
Question: Assume $N = 2^n - 1$ for some $n$, find a method of inserting the numbers $[1,...,N]$ to a BST such that it is completely balanced (i.e. - it is a complete tree).
Solution: As we usually do with trees, we give a recursive solution. Our input will be a node and a first and last index to enter into the tree rooted in the node. We start with the root, $first = 1, last = 2^n - 1$
class Tree_node():
def __init__(self, key, val):
self.key = key
self.val = val
self.left = None
self.right = None
def __repr__(self):
return "(" + str(self.key) + ":" + str(self.val) + ")"
class Binary_search_tree():
def __init__(self):
self.root = None
def __repr__(self): #no need to understand the implementation of this one
out = ""
for row in printree(self.root): #need printree.py file
out = out + row + "\n"
return out
def lookup(self, key):
''' return node with key, uses recursion '''
def lookup_rec(node, key):
if node == None:
return None
elif key == node.key:
return node
elif key < node.key:
return lookup_rec(node.left, key)
else:
return lookup_rec(node.right, key)
return lookup_rec(self.root, key)
def insert(self, key, val):
''' insert node with key,val into tree, uses recursion '''
def insert_rec(node, key, val):
if key == node.key:
node.val = val # update the val for this key
elif key < node.key:
if node.left == None:
node.left = Tree_node(key, val)
else:
insert_rec(node.left, key, val)
else: #key > node.key:
if node.right == None:
node.right = Tree_node(key, val)
else:
insert_rec(node.right, key, val)
return
if self.root == None: #empty tree
self.root = Tree_node(key, val)
else:
insert_rec(self.root, key, val)
def minimum(self):
''' return node with minimal key '''
if self.root == None:
return None
node = self.root
left = node.left
while left != None:
node = left
left = node.left
return node
def depth(self):
''' return depth of tree, uses recursion'''
def depth_rec(node):
if node == None:
return -1
else:
return 1 + max(depth_rec(node.left), depth_rec(node.right))
return depth_rec(self.root)
def size(self):
''' return number of nodes in tree, uses recursion '''
def size_rec(node):
if node == None:
return 0
else:
return 1 + size_rec(node.left) + size_rec(node.right)
return size_rec(self.root)
def inorder(self):
'''prints the keys of the tree in a sorted order'''
def inorder_rec(node):
if node == None:
return
inorder_rec(node.left)
print(node.key)
inorder_rec(node.right)
inorder_rec(self.root)
def insert_balanced(self, n):
'''inserts the numbers 1, ... , 2**n - 1 into a full BST'''
def insert_balanced_rec(node, first, last):
if first == last:
node.key = first
node.val = first
else:
mid = (first + last - 1) // 2
node.key = mid + 1
node.val = mid + 1
node.left = Tree_node(0,0)
insert_balanced_rec(node.left, first, mid)
node.right = Tree_node(0,0)
insert_balanced_rec(node.right, mid + 2, last)
self.root = Tree_node(0,0)
insert_balanced_rec(self.root, 1, 2**n - 1)
t = Binary_search_tree()
t.insert(4,'a')
t.insert(2,'a')
t.insert(6,'a')
t.insert(1,'a')
t.insert(3,'a')
t.insert(5,'a')
t.insert(7,'a')
#t.inorder()
t = Binary_search_tree()
t.insert_balanced(4)
printree(t.root)
[' 8 ', ' ______________/ |________________ ', ' 4 12 ', ' ______/ |______ _______/ |_______ ', ' 2 6 10 14 ', ' __/ |__ __/ |__ __/ |__ __/ |__ ', ' 1 3 5 7 9 11 13 15 ', ' / | / | / | / | / | / | / | / | ', '# # # # # # # # # # # # # # # #']
Exam question (2018, Spring Semester)
Let $L,K$ be two linked lists of length $n,m$ respectively. We say that the lists merge if there exists a node that is on both lists.
I.e. - there exists a node $q$ in $L$ and $p$ in $K$ such that $q ~is~ p == True$. In such a case we call $p$ a joint node.
Write a function $are\_merged$ that gets two linked lists as an input and returns True iff the lists merge.
The main idea - two linked lists merge if and only if their last node (their tail) is the same node.
def are_merged(L, K):
node_l = L.next
node_k = K.next
while node_l.next != None:
node_l = node_l.next
while node_k.next != None:
node_k = node_k.next
return node_k is node_l
#Here is an equivalent solution with a shorter code:
#last_node_l = L[len(L)-1]
#last_node_k = K[len(K)-1]
#return last_node_l is last_node_k
L = Linked_list("abcd")
L
K = Linked_list()
K.next = L.next.next.next
# Manually define the length of K
K.len = 2
K.add_at_start("e")
K
M = Linked_list()
M.add_at_start("d")
M
print(are_merged(L,K))
print(are_merged(L,M))
[a,2582652271360] [b,2582652268728] [c,2582652271808] [d,2582652268840]
[e,2582652270800] [c,2582652271808] [d,2582652268840]
[d,2582652629344]
True False
Space: Saving a pointer to two nodes can be done in $O(1)$ memory Time: Each node in the lists is read exactly once and all operations run in time $O(1)$ so runtime is $O(n+m)$
Next, write a function $find\_shared$ that gets two merged linked lists as an input and returns the first joint node of the lists.
Analyze its running time and space complexity.
def find_shared_1(L, K):
id_set = set()
p = L.next
while p != None:
id_set.add(id(p))
p = p.next
q = K.next
while q != None:
if id(q) in id_set:
return q
q = q.next
return None # should not reach here since L, K have joint items
def find_shared_2(L, K):
n = len(L)
m = len(K)
p = L.next
q = K.next
for i in range(max(0, n-m)):
print('advp')
p = p.next
for i in range(max(0, m-n)):
print('advq')
q = q.next
while p != None:
if p is q:
return p
p = p.next
q = q.next
return None # Should never get here
def find_shared_3(L, K):
p = L.next
q = K.next
while p != None and q != None:
if p is q:
return p
p = p.next
q = q.next
if p == None:
p = K.next
if q == None:
q = L.next
return None # must end before, since L, K have joint items
L = Linked_list("abcd")
L
K = Linked_list()
K.next = L.next.next.next
# Save the first joint node
x = K.next
K.len = 2
K.add_at_start("e")
K
M = Linked_list()
M.add_at_start("d")
M
print(are_merged(L,K))
print(are_merged(L,M))
print(find_shared_1(L,K), find_shared_1(L,K) == x)
print(find_shared_2(L,K), find_shared_2(L,K) == x)
print(find_shared_3(L,K), find_shared_3(L,K) == x)
[a,91940784] [b,91940624] [c,91940592] [d,91940272]
[e,91940432] [c,91940592] [d,91940272]
[d,1901584]
True False advp advp [c,91940592] True [c,91940592] True [c,91940592] True
For the analysis assume wlog that $n \geq m$: