simple recursion 1

[Sedai]

the following algorithm is obviously faulty.

void a(int r, int s){
	int x = (s+r)/2;
	if(r==s)
		return;
	cerr << x <<&quot; &quot;;
	a(r, x,);
	a(x+1, s);
}

Examining even the simplest case (calling a(1,2); )shows the problem. I know it can be 'worked around' by
a(1,n+1) if u need n ints in displayed in preorder, but I don't like such work-arounds.
How should I change the stopping condition, or is it that I need another variable.... I bet it's simple but I don't see it

thank you for your help!

Avendeval

 

[Zyrenthian]

looking at a(1,2) i dont see the fault

r =1;
s=2;
x = 3/2; // 1

// no return

cerr<< 1;

a(1,1)// will return
a(2,2) // will return
done


Could you post a different case that causes the infinite loop???

Matt

 

[Sedai]

im sorry i didnt make it clear.
there's no infinite loop, it's just that the highest int is never displayed, that's the problem.
for example if i want the ints from 1-10 displayed in preorder and i call a(1,10); i'll get
5 3 2 1 4 8 7 6 9
u see, the 10 is missing
I can always compensate for this by a(1,11); but i hate this...
i was wondering if i could change the algorithm to work properly.
actually, looking at the output for a(1,11); it makes me wonder if the algorithm is correct at all (logically); or if it produces the best result....?

thanks for ur help!!

Avendeval

 

[Zyrenthian]

by pre order, i dont follow how you are doing this. Are you mimicing an AVL tree?

Matt

 

[Sedai]

yeah, i need this to give me the indices of an array so that I can input the values of the array at these indices in a binary search tree, and make it balanced (btw, my array is sorted). but this is irrelavent really.
can u help me modify the above algorithm to make it work right? or at least give me some hints?

thanks!!
Avendeval

 

[Guest_imported]

a(1,11) does not just add a 10 to the end of sequence of a(1,10). you will get 5 3 2 1 4 8 7 6 9 with a(1,10) and get 6 3 2 1 5 4 9 8 7 10 with a(1,11). They are totally different. I am not clear about what you want.

 

[Zyrenthian]

However... both are balanced avl trees

 

[Zyrenthian]

Analyzing the function further i see that it will never print out the maximum value passed to it (i.e. s) look at this scenario

a(1,10)

prints out 5 (11/2)

calls a(1,5)
prints out 3
calls a(1,3)
prints out 2
calls a(1,2)
prints out 1
returns and calls a(3,5)
prints out 4
returns
returns
calls a(5,10)

NOTICE that 5 was NOT printed when a(1,5) was called

here in lies your problem. The quick fix for it is as you said... to call the function with a(1,n+1). The way it is currently written will never print out the highest value. I apologize but i do not have time to look at the function further, however i would suggest looking at code for an AVL tree. It has 4 functions which will manage the tree. LeftRotate RightRotate DoubleLeftRotate and DoubleRightRotate. If i think of anything else regarding this function i will post it but I am leaving for home from work at the moment.

Matt

 

[Sedai]

yeah, sure, i will get different results, i realize this.
;-)

as Zyrenthianthat says i WILL get balanced AVL trees in either case, so at least the algorithm is ok, it's just the implementation...

the upper index (second argumnet) gets ommitted, and that's bugging me

I could easily add the value of the last index to the tree,
as in
a(1,10);
then i get:
5 3 2 1 4 8 7 6 9
assuming that insude the a function instead of cerr i have bst.insert(array);
after the call of the function i could just have something like
bst.insert(array[10]);
so it's as if i had:
5 3 2 1 4 8 7 6 9 [bold]10[/bold]

still, it seems like cheating to me. id like to make the algorithm work perfectly. any ideas? i hope u understand what i mean. if not, don't worry, i guess i'll just stick to this.... and thanks for you time, i appreciate it!
Avendeval

 

[raochetan]

Change the code as below. it works as u want. When u call the function a(1, 10) it prints from all the 10 integers

void a(int r, int s){
if(r>s)
return;
int x = (s+r+1)/2;
cerr << x <<&quot; &quot;;
a(r, x-1);
a(x+1, s);
}

 

[Lebowski]

What is a AVL tree?

A simple decoding of the abreiviation will do I'll research from there...

Thanks

 

[Sedai]

thank you raochetan.
i see your point
thanks again!



p.s. Lebowski: AVL trees, height-balanced binary search trees. Named after two russian guys Georgii Maksimovich Adel'son-Vel'skii and Evgenii Mikhailovich Landis. They came up with a technique (somewhere in the 1960s)to keep a binary search tree balanced as items are inserted into it. Avendeval

 

[Lebowski]

Thanks.. good luck...