====== Binary Search Tree e Heap ======

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

{{teaching:info3:heap.tgz|Qui}} trovate vari esempi di Heap e Heapsort in Python.

=== Binary Search Tree e Heap ===

In today's lecture, we have seen the [[wp>Binary_search_tree|BST]].
We will see the [[wp>Binary_heap|Heap]] data structure next time, as well as the [[wp>Heapsort]] algorithm.

{{teaching:info3:heap.tgz|Here}} you can find the Heap and Heapsort examples in Python.


== Binary Search Tree Implementation ==

<code 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)
</code>