#
#   Binaarihakupuu, operaatioiden toimintaperiaate luentomonisteessa
#
# toteutus on luentomonisteen tavoin taysin epa-olio-orientoitunut
# eli kaytetaan funktioita, jotka saavat myos puun parametrina
# oliohenkinen toteutus ei allaolevista paljon muuttuisi

# maaritellaan Puusolmun konstruktorissa, etta attribuutit saavat oletusarvonaan
# None. Nain tulee myos selvaksi mita attribuutteja Puusolmulla on. 
# Pythonissahan tama ei oikeastaan ole tarpeen

class Puusolmu:
	def __init__(self):
		self.left = None;
		self.right = None;
		self.parent = None;
		self.key = None;

# Tehdaan samoin Puun suhteen
class Puu:
	def __init__(self):
		self.root = None;	
		
################################
		
def search(t,k):
	x = t.root;
	while x!=None and x.key!=k:
		if k<x.key:
			x = x.left;
		else:
			x = x.right;	
	return x;

# alipuun x pienin
def min(x):
	while x.left!=None:
		x = x.left;
	return x;

# alipuun x suurin
def max(x):
	while x.right!=None:
		x = x.right;
	return x;

def succ(t,x):
	if ( x.right!=None ):
		return min(x.right);
	y = x.parent
	while y != None and y.right == x: 
		x = y;		
		y = x.parent;	
	return y;
	
def insert(t, k):
	uusi = Puusolmu();
	uusi.key = k;
	uusi.left = None;
	uusi.right = None;
	uusi.parent = None;

	if ( t.root == None ):
		t.root = uusi;		
		return;

	x = t.root; 
	p = None;
	
	while x!=None:  	
		p = x;
		if ( uusi.key<x.key ):	
			x = x.left;				
		else:						
			x = x.right;			
	uusi.parent = p; 	
	if ( uusi.key < p.key ):
		p.left = uusi;
	else:
		p.right = uusi;
	
def delete(t, pois):
	# ensin tapaus 1: poistettavalla ei ole lapsia
	if pois.left == None and pois.right == None:
		vanh = pois.parent;
		if vanh == None:		
			t.root = None;
			return;
		if pois == vanh.left:
			vanh.left = None;
		else:
			vanh.right = None;
		return pois;
	# tapaus 2: poistettavalla on tasan yksi lapsi
	if pois.left == None or pois.right == None:	
		if pois.left != None:
			lapsi = pois.left;
		else:
			lapsi = pois.right;
		vanh = pois.parent;
		lapsi.parent = vanh;
		if vanh == None:
			t.root = lapsi;
			return;
		if pois == vanh.left:
			vanh.left = lapsi;
		else:
			vanh.right = lapsi;
		return pois;
	# tapaus 3: poistettavalla on kaksi lasta
	seur = min(pois.right)
	pois.key = seur.key
	lapsi = seur.right
	vanh = seur.parent
	if seur == vanh.left:
		vanh.left = lapsi
	else:
		vanh.right = lapsi
	if lapsi != None:
		lapsi.parent = vanh	

def inorder(x):
	if x != None:
		inorder(x.left);
		print( x.key );
		inorder(x.right);

#########################################
#
# luodaan puu ja kaytetaan sita
		
puu = Puu();
puu.root = None;

for i in [9,8,7,6,5,1,3,-7]:
	insert(puu, i);

for i in [4,8,9,88,5]:
	hit = search(puu, i);
	if ( hit!=None):
		print i, " on puussa";
	else:
		print i, " ei ole puussa";

print "pienin ",min(puu.root).key;
print "suurin ",max(puu.root).key;

print "solmut jarjestyksessa:";
x = min(puu.root);
while ( x!= None ):
	print x.key;
	x = succ(puu,x);
print "\n";

pois = search(puu,1);

if pois != None:
	print "poistetaan", pois.key;
	delete(puu, pois);
else:
	print "ei loydy";

inorder(puu.root);