#!/usr/bin/gawk -f            
# /* vim: set filetype=awk : */ -*- awk -*- 
#
# ----| rbt |--------------------------------------
#
#   _ _ _ _ _                                    ((
#  |=|=|=|=|=|.----------------------------.    _))_
#  |-|-|-|-|-||  a 'requirez' code bundle  | ___\__/)_
#  |_|_|_|_|_|'----------------------------'|_||_~~_|_|
#
# Built by "komarneni" on Fri Jun 30 12:47:17 EDT 2006.
#
# This program is free software; you can redistribute it and/or
# modify it under the terms of the GNU General Public License
# as published by the Free Software Foundation; version 2.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with this program; if not, write to the Free Software
# Foundation, Inc.,51 Franklin Street, Fifth Floor, Boston, 
# MA 02110-1301, USA.
#
# #---- [saya.awk ] ------------------------------------------
#<h3>saya.awk</h3>
#Print a string in key-sort order.

function saya(s,a,q1,q2,eol,    com,i,j,n,tmp,str,sep) {
	com="sort";
	q1= q1 ? "\"" : "";
	q2= q2 ? "\"" : "";
	for(i in a) {
		sep="";
		str= s"[";
		n=split(i,tmp,SUBSEP);
		for(j=1;j<=n;j++) {
			str=str sep q1 tmp[j] q1;
			sep=",";
		}
		print str "] = " q2 a[i] q2 eol  | com;
	};
	close(com);
}





BEGIN{
	RS=","
		Root= -2;
	Id=-1;
	Left ="LEFT";
	Right ="RIGHT";
	Mass="MASS";
}




{ 

	while(getline var <"input.txt")
	{
		child(var);
	}
	close(var);                                              
}

END {
	saya("T",T)
		printt(T);
moveup(T[Root],13,T,T1);
#assign2(T[Root],T,T1);
saya("T1",T1)
printt(T1)
}

function new(value){
	T[Root]=value;
}

# make the tree oeprations accept a tree argument

function printt(t) {  printt1(t[Root],"","",t) }
function printt1(x,b4,indent,t) {
	if (!x) return 1;
	print indent b4 x " = " x " [" t[x,Mass] "]" | "cat -n";
	printt1(t[x,Left] ," < ", indent "|  ",t);
	printt1(t[x,Right]," > ", indent "|  ",t); 
}

function array(a){split("",a,"")}

function child(value){
	T[Root]? child1(T[Root],value,T):new(value);
}

function child1(k0, k,t){

	if(k<k0)
	{
		if(t[k0,Left])
		{
			child1(t[k0,Left],k,t)
		}
		else{
			t[k0,Left]=k;
		}
	}
	else if(k>k0){
		if(t[k0,Right]){
			child1(t[k0,Right],k,t);
		}
		else{
			t[k0,Right]=k
		}
	}
	t[k,Mass]++
}

function moveup(x0,x1,t,t1)
{

	#print "in move up"
	if(t[x0,Left]==x1)
	{
		print "tinku"
assign2(t[x0,Left],t,t1)
			t[x0,Left]=" "
exit			
process(t,t1)
	}
	if(t[x0,Right]==x1)
	{
		print "vamsi"
assign2(t[x0,Right],t,t1)
			t[x0,Right]=""
			process(t,t1)
	}
	if(x0>x1)
	{
	print "right"
	moveup(t[x0,Left],x1,t,t1)
exit
	}
	if(x0<x1)
	{
		print "rleft"
moveup(t[x0,Right],x1,t,t1)
	}

}


function assign2(k0,t,t1)
{


	child2(T1[Root],k0,t,t1)
}


function child2(k1,k0,t,t1)
{

	if(!t1[Root])
	{
		t1[Root]=k0;
	}
	else {
		if(t[k0,Left])
		{

			t1[k0,Left]=t[k0,Left];
			child2(t1[k0,Left],t[k0,Left],t,t1)
		}
		if(t[k0,Right])
		{
			t1[k0,Right]=t[k0,Right];

			child2(t1[k0,Right],t[k0,Right],t,t1)
		}


	}
}


function process(t,t1)
{

assign2(t[Root],t,t1)
}