asked on

from a sorted array to AVL tree

I want to built a AVL tree from a sorted array (of ints).
Below is my code, but I'm doing something wrong...

typedef struct TreeNode* SearchTree;

        struct TreeNode
        {
			int Element;
			SearchTree  Left;
			SearchTree  Right;
		};
SearchTree avl(int A[],int N, int left, int right,SearchTree T){
           SearchTree temp=NULL;
           int mid = (left+right)/2;printf("mid=%d",mid);getchar();
           temp= Insert(A[mid],T);
           right=mid-1;printf(" right=%d",right);
           if (right<left) return temp;
           avl(A,N,left,right,T);
           left=mid+1;
           if (left>=right) return temp;
           avl(A,N,left,right,T);
}
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 )
					FatalError( "Out of space!!!" );
                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;  
        }

Open in new window

mnh

Hi,

In function avl(int A[],int N, int left, int right,SearchTree T), why don't you just iterate over the elements of A, inserting them one after the other in the tree?

I don't understand why you keep splitting the array in two and inserting the middle element. This looks incorrect...

Regards,
-- mnh

phoffric

Quick look & question for you. Last line in avl() is a recursive call to avl(). But after this last line, you do not return anything. Shouldn't you return a SearchTree?

phoffric

Follow-up comment: avl() defined to return SearchTree, and it does do this sometimes; but whenever avl() is called, the return value is ignored. If you do not need a return value, then do not return anything (make return void); if you do need a return value, then use the return value.

ASKER CERTIFIED SOLUTION

phoffric

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

I will try to change the function to void... I 'll come back soon.

phoffric

I submitted recommendations to the author, which was incorporated into the code submitted in the follow-up question. https://www.experts-exchange.com/questions/25001363/AVL-balanced-tree-from-a-sorted-array.html?cid=1576

My 3rd comment was the result of debugging the author's code and identifying major tree insertion issue.

So, why close this, and why not award points to contributors?

xiromdim

ASKER

very good advice, but he didn't give some code

phoffric

Hi xiromdim,
I was just starting the dialog with you, and it ended in an hour. I would have answered further questions.