Binary Search Tree e Heap

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)