[algogeeks] Re: BST represented in array
Karthik, Sorry for this but I still can't understand your program. Can you describe it for me or give an example of how it works. Will it work even in the case of non-complete BST, I mean for every BST? --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: BST represented in array
Now in the case of non complete BSTs it may run into trouble...I never handled them. It will work for complete BSTs though as it is. Refer to a previous thread in algogeeks where i had posted the thread inplace sorting and look at the solution by atamurad for the explanation. --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: BST represented in array
An unique BST does exist for such an array if you assume the root to be 1, then automatically you will be able to fix the left and right children of the root and so on. --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: BST represented in array
hi, U get sorted numbers if u traverse the BST in inorder..so if u traverse the array following inorder u get sorted list and also u visit each index onceso its O(n)... with regards, koushik chitta On 3/24/07, vim [EMAIL PROTECTED] wrote: hi guys plz explain how to sort elements of BST represented using array in o(n) time -- *** 30 years from now it doesn't matter which shoe you wore,which branded jean you wore..what all matters is WHAT YOU HAVE LEARNED AND HOW YOU HAVE USED IT. http://students.iiit.ac.in/~koushik_c --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: BST represented in array
#includestdio.h
#includestdlib.h
#includemath.h
#includestring.h
#define MAXN 2000
int a[MAXN];
int cnt = 0;
int log2n;
int n;
void populatetestcase(int i)
{
if(i*2=n) populatetestcase(i*2);
a=++cnt;
if(i*2+1=n) populatetestcase(i*2+1);
}
int calc_x(int i)
{
return (int)log2l((double)i);
}
int calc_m1(int i)
{
return 1 (log2n-calc_x(i)+1);
}
int calc_m2(int i)
{
return i - (1calc_x(i));
}
int main()
{
int i,j,temp,p;
n=(17)-1;
log2n = calc_x(n);
populatetestcase(1);
for(i=1; i=n; i++) {
p= calc_m1(i)*calc_m2(i) + calc_m1(i)/2;
if((pi a[p]a)|| (pi a[p]a))
continue;
j=i;
while(p!=i)
{
temp = a[j];
a[j] = a[p];
a[p] = temp;
p = calc_m1(p)*calc_m2(p) + calc_m1(p)/2;
}
}
for(i=1; i=n; i++)
{
printf(%d ,a);
}
system(PAUSE);
return 0;
}
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] Re: BST represented in array
yes...but you can sort without constant space using the posted algorithm --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: BST represented in array
I think your algo uses O(n) space too On Mar 25, 6:50 am, Karthik Singaram L [EMAIL PROTECTED] wrote: yes...but you can sort without constant space using the posted algorithm --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: BST represented in array
for(i=1; i=n; i++) {
p= calc_m1(i)*calc_m2(i) + calc_m1(i)/2;
if((pi a[p]a)|| (pi a[p]a))
continue;
j=i;
while(p!=i)
{
temp = a[j];
a[j] = a[p];
a[p] = temp;
p = calc_m1(p)*calc_m2(p) + calc_m1(p)/2;
}
}
Isnt this constant space (assuming that the array a is given already).
Since calc_m1 and calc_m2 are non recursive?
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] Re: BST represented in array
Sorry, I thought populatetest was part of the solution. I havent run
your code, but it seems not correct and have you tested it before you
posted here?
in your populatetest
a=++cnt;
doesnt it change a[0] only?
I am pretty amazed if you can do constant space. Can you explain your
algo?
On Mar 25, 2:58 pm, Karthik Singaram L [EMAIL PROTECTED]
wrote:
for(i=1; i=n; i++) {
p= calc_m1(i)*calc_m2(i) + calc_m1(i)/2;
if((pi a[p]a)|| (pi a[p]a))
continue;
j=i;
while(p!=i)
{
temp = a[j];
a[j] = a[p];
a[p] = temp;
p = calc_m1(p)*calc_m2(p) + calc_m1(p)/2;
}
}
Isnt this constant space (assuming that the array a is given already).
Since calc_m1 and calc_m2 are non recursive?
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] Re: BST represented in array
On Mar 25, 4:17 pm, leiz [EMAIL PROTECTED] wrote:
Sorry, I thought populatetest was part of the solution. I havent run
your code, but it seems not correct and have you tested it before you
posted here?
in your populatetest
a=++cnt;
it is a syntax error.
*a = ++cnt changes a[0]
my bad
doesnt it change a[0] only?
I am pretty amazed if you can do constant space. Can you explain your
algo?
On Mar 25, 2:58 pm, Karthik Singaram L [EMAIL PROTECTED]
wrote:
for(i=1; i=n; i++) {
p= calc_m1(i)*calc_m2(i) + calc_m1(i)/2;
if((pi a[p]a)|| (pi a[p]a))
continue;
j=i;
while(p!=i)
{
temp = a[j];
a[j] = a[p];
a[p] = temp;
p = calc_m1(p)*calc_m2(p) + calc_m1(p)/2;
}
}
Isnt this constant space (assuming that the array a is given already).
Since calc_m1 and calc_m2 are non recursive?
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] Re: BST represented in array
i am sorry that is a[i] = ++cnt I made a mistake when pasting the code... --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
