README.md

Δυαδικό δέντρο αναζήτησης

(binsearch-tree.py)

• Κόμβοι και Δέντρο
• Εισαγωγή κλειδιού, τιμής
• Εκτύπωση δέντρου
• Αναζήτηση κλειδιού

binsearch-tree.py

class Node:

	def __init__(self,key,value,left=None,right=None):
		self.key = key
		self.value = value
		self.left = left
		self.right = right
	
class Tree:

	def __init__(self):
		self.root = None
		

	def insert(self,key,value):

		""" inserts `key`,`value` into binary search tree """

		self.root = self._insert(self.root,key,value)

		
	def _insert(self,node,key,value):

		"""  inserts `key`, `value` into binary search tree
		starting at `node`. Returns the same tree after insertion.
		"""
		
		if node is None: return Node(key,value)
			
		if node.key==key:
			node.value = value
							
		elif key<node.key:
			node.left = self._insert(node.left,key,value)
		else:
			node.right = self._insert(node.right,key,value)
			
		return node	

	
	def dump(self):

		""" pretty-print binary search tree """ 

		self._dump(self.root,0,'root')
		

	def _dump(self,node,level,prefix):

		""" prints a binary search tree starting at `node`
		and `level`. `prefix` is a string to be output before
		node's key/value
		"""

		indent = '\t'*level
		if node is None:
			print '%s[%s] <empty>' % (indent,prefix)
		else:
			print '%s[%s] key=%s, value=%s' % (indent,prefix,node.key,node.value)
			self._dump(node.left,level+1,'left ')
			self._dump(node.right,level+1,'right')


	def find(self,key):

		""" returns value for a `key` in binary search tree
		or None if `key` is not found.
		"""
		
		return self._find(self.root,key)

		
	def _find(self,node,key):

		""" returns value for a `key` in binary search tree
		or None if `key` is not found. Starts search at `node`.
		"""

		if node is None: return None

		if node.key==key:
			return node.value
							
		elif key<node.key:
			return self._find(node.left,key)
		else:
			return self._find(node.right,key)
			
		return node	
		

# create empty tree
t = Tree()

# key,value insertion
il = [(8,'a'),(3,'b'),(6,'c'),(3,'d'),(23,'v'),(11,'x'),(2,'z')]
for key,val in il:
	print 'Inserting key %s with value %s' % (key,val)
	t.insert(key,val)

print '---------------------------------------'
print 'Tree is:'
t.dump()
print '---------------------------------------'

# key search
fl = [6,23,22,4,8]
for key in fl:
	print 'Searching for key %s ...' % key,
	val = t.find(key)
	if val is None: print 'not found'
	else: print 'value is %s' % val