Informatica 3: Novità

Nella lezione del 3/12 abbiamo introdotto i B-Tree.

Implementazione dei B-Tree in Python

class InvalidBTreeException(Exception):
	pass
 
class NonFullSplitException(Exception):
	pass
 
class BTree(object):
	def __init__(self,parent,chld,elem,degree=2,isLeaf=True):
		'''Default: 2-3-4 Tree'''
		self.isLeaf=isLeaf
		self.children=chld
		self.keys=elem
		self.minkeys=degree-1
		self.maxkeys=2*degree-1
		self.parent=parent
		if parent and (len(self.keys)>self.maxkeys or len(self.keys)<self.minkeys) :
			raise InvalidBTreeException, "This is not a valid BTree node! N.keys="+`len(self.keys)`
 
	def isFull(self):
		return self.maxkeys==len(self.keys)
 
	def search(self,key):
		# Find smallest index such that key < self.keys[i]
		i=0
		while i<len(self.keys) and key > self.keys[i] : i+=1
		# Did we find the key?
		if i<=len(self.keys) and key==self.keys[i] :
			return self, i
		# Are we in a leaf? If so, search ends unsuccessfully..
		elif self.isLeaf :
			return None, None
		# Recursively try on self.children at same index i
		else :
			return self.children[i].search(key)
 
	def split(self):
		if not self.isFull() :
			raise NonFullSplitException, "Why split a non-full node?"
		S=self.minkeys # Median key+1
		k=self.keys[S]
		if self.parent==None : # We're in root!
			newroot = BTree(None, [self], [], S+1, False)
			self.parent=newroot
		new = BTree(self.parent, self.children[S+1:], self.keys[S+1:], S+1, self.isLeaf)
		for c in new.children :
			c.parent=new
		self.children=self.children[:S+1]
		self.keys=self.keys[:S]
		i=self.parent.children.index(self)
		self.parent.children.insert(i+1,new)
		self.parent.keys.insert(i+1,k)
		return self.parent
 
	def insert(self, key, insertNonFull=False):
		if (not insertNonFull) and self.isFull() :
			self.split().insert(key,True)
		elif self.isLeaf :
			self.keys.append(key)
			self.keys.sort()
		else :
			# Find smallest index such that key < self.keys[i]
			i=0
			while i<len(self.keys) and key > self.keys[i] : i+=1
			self.children[i].insert(key)
		return self.root()
 
	def printtree(self,prefix=''):
		print prefix, self.keys
		for i in self.children :
			i.printtree(prefix+'  ')
 
	def root(self):
		if self.parent==None :
			return self
		return self.parent.root()
 
	def check(self):
		for c in self.children :
			if c.parent!=self : 
				self.printtree()
				raise InvalidBTreeException, "Wrong parent-child relation! on "+`self.keys`+' '+`c.keys`
			else : c.check()
 
if __name__ == '__main__' :
	bt = BTree(None,[],[2,4])
	bt=bt.insert(3)
	bt=bt.insert(1)
	bt=bt.insert(5)
	bt=bt.insert(9)
	bt=bt.insert(7)
	bt=bt.insert(13)
	bt=bt.insert(6)
	bt.printtree()
	bt.check()
	bt=bt.insert(11)
	bt.printtree()
	bt.check()
	bt=bt.insert(10)

Qui trovate il codice relativo.

Nella lezione del 3/12, abbiamo visto i BST, mentre in quella di lunedi' vedremo l'Heap. A partire da queste strutture dati, potremo costruire l'algoritmo di ordinamento noto come Heapsort.

Qui trovate vari esempi di Heap e Heapsort in Python.

In today's lecture, we have seen the BST. We will see the Heap data structure next time, as well as the Heapsort algorithm.

Here you can find the Heap and Heapsort examples in Python.

#!/usr/bin/python
 
class BinNode(object):
	def __init__(self,parent,key,content=None):
		self.data  = content
		self.key   = key
		self.left  = None
		self.right = None
		self.parent= parent
 
	def __getitem__(self,side):
		if side in [ 0, 'left', 'l' ] :
			return self.left
		elif side in [ 1, 'right', 'r' ] :
			return self.right
		raise KeyError, side
 
	def __setitem__(self,side,item):
		if not isinstance(item,BinNode) :
			raise TypeError, item
		if side in [ 0, 'left', 'l' ] :
			self.left = item
		elif side in [ 1, 'right', 'r' ] :
			self.right = item
		else :
			raise KeyError, side
 
	def isLeaf(self):
		return not (self.left or self.right)
 
	def search(self,key):
		if self.key==key :
			return self
		if key<self.key :
			return self.left.search(key) if self.left else None
		else :
			return self.right.search(key) if self.right else None
 
	def insert(self,key,content=None):
		if key<self.key :
			if self.left :
				self.left.insert(key,content)
			else :
				self.left = BinNode(self,key,content)
		else :
			if self.right :
				self.right.insert(key,content)
			else :
				self.right = BinNode(self,key,content)
 
	def min(self):
		x=self
		while x.left : x=x.left
		return x
 
	def max(self):
		x=self
		while x.right : x=x.right
		return x
 
	def next(self):
		if self.right : return self.right.min()
		x,y=self,self.parent
		while y and x == y.right : x,y=y,y.parent
		return y
 
	def prev(self):
		if self.left : return self.left.max()
		x,y=self,self.parent
		while y and x == y.left : x,y=y,y.parent
		return y
 
	def delete(self,node):
		root = self
		y = node if not node.left or not node.right else node.next()
		x = y.left if y.left else y.right
		if x : x.parent = y.parent 
		if not y.parent :	root =x
		elif y.parent.left == y : y.parent.left = x
		else : y.parent.right = x
		if y != node :
			node.key = y.key
			node.data = y.data
		return root, y
 
	def __str__(self) :
		return '{ '+`self.key`+' : '+`self.data`+' }'
 
def preorder(node,action,direction=['l','r']):
	'''Preorder, defaults to left to right; 
	action must be a function specific for the elements'''
	action(node)
	if node[direction[0]] : 
		preorder(node[direction[0]],action,direction)
	if node[direction[1]] : 
		preorder(node[direction[1]],action,direction)
 
def postorder(node,action,direction=['l','r']):
	'''Preorder, defaults to left to right; 
	action must be a function specific for the elements'''
	if node[direction[0]] : 
		preorder(node[direction[0]],action,direction)
	if node[direction[1]] : 
		preorder(node[direction[1]],action,direction)
	action(node)
 
def inorder(node,action,direction=['l','r']):
	'''Preorder, defaults to left to right; 
	action must be a function specific for the elements'''
	if node.isLeaf() : 
		action(node)
	else :
		if node[direction[0]] : 
			inorder(node[direction[0]],action,direction)
		action(node)
		if node[direction[1]] : 
			inorder(node[direction[1]],action,direction)
 
 
if __name__ == '__main__' :
	def action(node):
		print node.key,
	from random import choice
	root = BinNode(None,choice(range(12)))
	for i in range(5) :
		root.insert(choice(range(12)))
	inorder(root,action)
	print ''
	print 'max', root.max().key
	print 'min', root.min().key
	x=root.min()
	for i in range(5) :
		print x.key,
		x=x.next()
	print x.key
	for i in range(5) :
		x = root.search(choice(range(12)))
		if x :
			root,deleted=root.delete(x)
			print 'deleted', deleted.key
	inorder(root,action)

Nella lezione del 14/11, abbiamo visto gli alberi binari, con due possibili implementazioni:

• Con strutture collegate da puntatori
• Come array, per alberi completi

Abbiamo inoltre introdotto le proprieta' di fullness e completeness, e i teoremi relativi che permettono di misurare l'occupazione in memoria di un albero binario.

Infine, abbiamo introdotto gli algoritmi di visita degli alberi binari.

Qui trovate il codice Python degli esempi visti a lezione.

Nella lezione del 7/11, abbiamo visto alcuni concetti tipici di Python, ma presenti anche in altri linguaggi di programmazione:

• Iteratori
• Generatori

A partire da questi ultimi, abbiamo costruito un modello di multithreading non-preemptive (i.e., cooperativo) basato sul concetto di coroutine.

Qui potete trovare gli esempi Python visti a lezione, e qui un tutorial sull'uso dei generatori e degli iteratori.

Nella lezione del 26/11, abbiamo visto i principali algoritmi di ordinamento:

• Bubblesort
• Insertion sort
• Selection sort
• Mergesort
• Quicksort
• Binsort
• Radix sort

Vedremo che alcuni altri algoritmi di ordinamento possono essere realizzati usando strutture d'appoggio basate su alberi, in particolare lo Heapsort.

Qui potete trovare le implementazioni in Python dei vari algoritmi (aggiornata rispetto allo scorso anno).

In the 26/11 lecture, we've seen the most common sorting algorithms:

• Bubblesort
• Insertion sort
• Selection sort
• Mergesort
• Quicksort
• Binsort
• Radix sort

We'll see that some additional sorting algorithms can be implemented with tree-based data structures – specifically Heapsort.

Here you can find the Python implementations of the algorithms seen at lecture (updated with respect to last year's code).