====== B-Tree ======

Nella lezione del 3/12 abbiamo introdotto i [[wp>B_Tree|B-Tree]].

**Implementazione dei B-Tree in Python**
<code 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)
</code>


{{teaching:info3:btree.tgz|Qui}} trovate il codice relativo.