asked on

AVL (balanced) tree from a sorted array

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

ASKER CERTIFIED SOLUTION

J K

membership

This solution is only available to members.

To access this solution, you must be a member of Experts Exchange.

Start Free Trial

xiromdim

ASKER

sorry my friend but it's the same....

Infinity08

>> 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 ?

xiromdim

ASKER

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

Infinity08

>> 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.

xiromdim

ASKER

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...

xiromdim

ASKER

As I see, I should insert a condition before the 2 returns...

Infinity08

>> 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.

xiromdim

ASKER

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

Infinity08

>> 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.

xiromdim

ASKER

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...

Infinity08

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 ?

xiromdim

ASKER

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.

xiromdim

ASKER

sorry, output: 1,3,4,5,6

Infinity08

>> 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 ?

Infinity08

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 */

J K

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....

xiromdim

ASKER

thanks, and sorry for the misunderstanding...