[Okta Webinar] Learn how to a build a cloud-first strategyRegister Now

x
?
Solved

AVL (balanced) tree from a sorted array

Posted on 2009-12-24
18
Medium Priority
?
1,525 Views
Last Modified: 2012-05-08
I have a sorted array of integers and I want to create a AVL tree.
To do so, I insert the middle element of the array to the tree, then the middle of the left part of the array and so on (binary logic).
What's going wrong whith my code below?
Thanks
#include <stdio.h>
#include<stdlib.h>
typedef struct TreeNode* SearchTree;

        struct TreeNode
        {
			int Element;
			SearchTree  Left;
			SearchTree  Right;
		};
SearchTree Insert( int X, SearchTree T )
        {
			if( T == NULL )
            {
                /* Create and return a one-node tree */
				T = (struct TreeNode*)malloc( sizeof( struct TreeNode ) );
				if( T == NULL ){
					printf( "Out of space!!!" );exit(1);
                }
                else
                {
					T->Element = X;
					T->Left = T->Right = NULL;
                }
            }
            else
			if( X < T->Element )
				T->Left = Insert( X, T->Left );
            else
			if( X > T->Element )
				T->Right = Insert( X, T->Right );
            /* Else X is in the tree already; we'll do nothing */

			return T;
        }

void arrayToAVL(SearchTree *T,int A[], int left, int right){
     int mid;
     if (right<left) return;
     
     mid=(left+right)/2;
     (*T)=Insert(A[mid],*T);
     return arrayToAVL(T,A,left,mid-1);
     return arrayToAVL(T,A,mid+1,right);
     
}
void InOrderPrintTree(SearchTree T){
             
             if (T==NULL) return;
             
             InOrderPrintTree(T->Left);
             printf("%d ",T->Element);
             InOrderPrintTree(T->Right);
             
        }
int main(){
    SearchTree t=NULL;
    int A[]={1,3,5,6,8};
    //testing insert function
    //t=Insert(10,t);t=Insert(5,t);t=Insert(1,t);t=Insert(12,t);
    InOrderPrintTree(t);printf("\n");
    arrayToAVL(&t,A,0,4);
    InOrderPrintTree(t);
    
    getchar();
    return 0;
}

Open in new window

0
Comment
Question by:xiromdim
  • 9
  • 7
  • 2
18 Comments
 
LVL 5

Accepted Solution

by:
Jalpa Kotak earned 2000 total points
ID: 26118304
try this,
 

#include <stdio.h>
#include<stdlib.h>
typedef struct TreeNode* SearchTree;

        struct TreeNode
        {
			int Element;
			SearchTree  Left;
			SearchTree  Right;
		};
SearchTree Insert( int X, SearchTree T )
        {
			if( T == NULL )
            {
                /* Create and return a one-node tree */
				T = (struct TreeNode*)malloc( sizeof( struct TreeNode ) );
				if( T == NULL ){
					printf( "Out of space!!!" );exit(1);
                }
                else
                {
					T->Element = X;
					T->Left = T->Right = NULL;
                }
            }
            else
			if( X < T->Element )
				T->Left = Insert( X, T->Left );
            else
			if( X > T->Element )
				T->Right = Insert( X, T->Right );
            /* Else X is in the tree already; we'll do nothing */

			return T;
        }

void arrayToAVL(SearchTree *T,int A[], int left, int right){
     int mid;
     if (right<left) return;
     
     mid=(left+right)/2;
     (*T)=Insert(A[mid],*T);
	 
     arrayToAVL(T,A,left,mid-1);
     arrayToAVL(T,A,mid+1,right);
     
}
void InOrderPrintTree(SearchTree T){
             
             if (T==NULL) return;
             
             InOrderPrintTree(T->Left);
             printf("%d ",T->Element);
             InOrderPrintTree(T->Right);
             
        }
int main(){
    SearchTree t=NULL;
    int A[]={1,3,5,6,8};
    //testing insert function
    //t=Insert(10,t);t=Insert(5,t);t=Insert(1,t);t=Insert(12,t);
    InOrderPrintTree(t);printf("\n");
    arrayToAVL(&t,A,0,4);
    InOrderPrintTree(t);
    
    getchar();
    return 0;
}

Open in new window

0
 

Author Comment

by:xiromdim
ID: 26119930
sorry my friend but it's the same....
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 26121819
>> What's going wrong whith my code below?

It would be easier to tell us what's going wrong ... That way, we can explain to you why it's going wrong that way, and how to fix it ... ;)

Could you tell us what is happening when you run the code (which input do you give, which output do you get, etc.), and where/how it's going wrong ?
0
Concerto's Cloud Advisory Services

Want to avoid the missteps to gaining all the benefits of the cloud? Learn more about the different assessment options from our Cloud Advisory team.

 

Author Comment

by:xiromdim
ID: 26122932
As I said, I have a sorted array and I want to built an AVL tree using the insert function for simple (unbalanced) BS trees. To do so, I insert the middle elemnt of the array, then the middle of the left subarray, and so on (binary logic).
In the specific code snippet, I declare an array A[]={1,3,5,6,8}, I run the avl function, and the bst created has only 1 and 5. I miss all the others.
I cannot find where is the problem in arrayToAVL funcion.
thanks
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 26124047
>> As I said

Note that you didn't say that ;) But thanks for clarifying.


>> I have a sorted array and I want to built an AVL tree using the insert function for simple (unbalanced) BS trees. To do so, I insert the middle elemnt of the array, then the middle of the left subarray, and so on (binary logic).

An AVL tree is self-balancing, and is sorted. So there's no need to have a sorted array for insertion.
You're using the wrong insertion approach. Insertion into an AVL tree happens "at the root" - the tree insertion algorithm itself takes care of where to place the value, and whether or not to re-arrange (re-balance) the tree.

For insertion, first you find the location where the new node has to be inserted, and then, depending on a few possible situations, you insert the node there by re-arranging the nodes around it.


>> In the specific code snippet, I declare an array A[]={1,3,5,6,8}, I run the avl function, and the bst created has only 1 and 5. I miss all the others.

So, instead of trying to make this approach work, I recommend writing an actual AVL tree insertion implementation.

Either way, the problem in your current code is that you have two return statements in the arrayToAVL function :

>>      return arrayToAVL(T,A,left,mid-1);
>>      return arrayToAVL(T,A,mid+1,right);

As soon as the first return statement is executed, the function ends ... ie. The second line will never be reached.
0
 

Author Comment

by:xiromdim
ID: 26124491
thanks a lot infinity08! The point is that it is an assignment, that's why I want to do it in a specific way...
If you have any idea...
0
 

Author Comment

by:xiromdim
ID: 26124505
As I see, I should insert a condition before the 2 returns...
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 26124512
>> If you have any idea...

The idea is to have only one return statement in the arrayToAVL function, because now you have one too many.

Note also that the arrayToAVL function does not return anything ... so you don't even need a return statement (in fact it's wrong to return something).

So, just remove the return's, and just call the function recursively twice.
0
 

Author Comment

by:xiromdim
ID: 26124748
I removed the returns, but I'm still getting a wrong result.
Anyway, there is a way to wright arrayToAVL function to return a SearchTree...
#include <stdio.h>
#include<stdlib.h>
typedef struct TreeNode* SearchTree;

        struct TreeNode
        {
			int Element;
			SearchTree  Left;
			SearchTree  Right;
		};
SearchTree Insert( int X, SearchTree T )
        {
			if( T == NULL )
            {
                /* Create and return a one-node tree */
				T = (struct TreeNode*)malloc( sizeof( struct TreeNode ) );
				if( T == NULL ){
					printf( "Out of space!!!" );exit(1);
                }
                else
                {
					T->Element = X;
					T->Left = T->Right = NULL;
                }
            }
            else
			if( X < T->Element )
				T->Left = Insert( X, T->Left );
            else
			if( X > T->Element )
				T->Right = Insert( X, T->Right );
            /* Else X is in the tree already; we'll do nothing */

			return T;
        }

void arrayToAVL(SearchTree *T,int A[], int left, int right){
     int mid;
     if (right<left) return;
     
     mid=(left+right)/2;
     (*T)=Insert(A[mid],*T);
     arrayToAVL(T,A,left,mid-1);
     arrayToAVL(T,A,mid+1,right);
     
}
void InOrderPrintTree(SearchTree T){
             
             if (T==NULL) return;
             
             InOrderPrintTree(T->Left);
             printf("%d ",T->Element);
             InOrderPrintTree(T->Right);
             
        }
int main(){
    SearchTree t=NULL;
    int A[]={1,3,4,5,6,8,10};
    
    arrayToAVL(&t,A,0,4);
    InOrderPrintTree(t);
    
    getchar();getchar();
    return 0;
}

Open in new window

0
 
LVL 53

Expert Comment

by:Infinity08
ID: 26124783
>> but I'm still getting a wrong result.

What result are you getting now ? Please be more precise when you refer to a problem. The more information you can give, the easier it is for us to help you, and the faster you'll get your answer.
0
 

Author Comment

by:xiromdim
ID: 26124937
my friend, I dont refer to teh specific results, because I believe that you will run the code with copy-paste. It is time consuming to explain the results of a code snippet...If you can help...
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 26125160
I don't have a compiler available atm. Nor do I have a lot of time.

You know the problem you're referring to ... It can't be that hard to just tell me. Otherwise you'll have to wait until I have the time to analyse your code in detail.

Btw :

>> It is time consuming to explain the results of a code snippet...

Why don't you just copy-paste the output ? That can't be that time consuming, can it ?
0
 

Author Comment

by:xiromdim
ID: 26125293
ok! the output is 1,3,4,5 ,and it is the 1st half of the array. That happens because the function returns always at line 43, so the second half of the array is never accessed.
0
 

Author Comment

by:xiromdim
ID: 26125306
sorry, output: 1,3,4,5,6
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 26125315
>> That happens because the function returns always at line 43, so the second half of the array is never accessed.

I thought you removed the return statement ?
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 26125321
Oh, and, you did adapt the boundaries, didn't you ?

>>     int A[]={1,3,4,5,6,8,10};
>>     
>>     arrayToAVL(&t,A,0,4);

should be :

    int A[]={1,3,4,5,6,8,10};
   
    arrayToAVL(&t,A,0,6);                               /* <--- 6 instead of 4 */
0
 
LVL 5

Expert Comment

by:Jalpa Kotak
ID: 26129735
Sorry
But I have posted the solution before is not the same as yours.....
Your code having.......
void arrayToAVL(SearchTree *T,int A[], int left, int right){
     int mid;
     if (right<left) return;
     
     mid=(left+right)/2;
     (*T)=Insert(A[mid],*T);
     return arrayToAVL(T,A,left,mid-1);
     return arrayToAVL(T,A,mid+1,right);
     
}

I have put  
arrayToAVL(T,A,left,mid-1);
arrayToAVL(T,A,mid+1,right);
instead of
  return arrayToAVL(T,A,left,mid-1);
  return arrayToAVL(T,A,mid+1,right);
because return was creating the problem....
try to run the code with these corrections...
Its working fine here....


0
 

Author Closing Comment

by:xiromdim
ID: 31669723
thanks, and sorry for the misunderstanding...
0

Featured Post

Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Windows programmers of the C/C++ variety, how many of you realise that since Window 9x Microsoft has been lying to you about what constitutes Unicode (http://en.wikipedia.org/wiki/Unicode)? They will have you believe that Unicode requires you to use…
Examines three attack vectors, specifically, the different types of malware used in malicious attacks, web application attacks, and finally, network based attacks.  Concludes by examining the means of securing and protecting critical systems and inf…
The goal of this video is to provide viewers with basic examples to understand opening and writing to files in the C programming language.
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use nested-loops in the C programming language.
Suggested Courses

872 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question