?
Solved

from a sorted array to AVL tree

Posted on 2009-12-20
8
Medium Priority
?
646 Views
Last Modified: 2012-06-21
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

0
Comment
Question by:xiromdim
  • 5
  • 2
8 Comments
 
LVL 3

Expert Comment

by:mnh
ID: 26093006
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
0
 
LVL 32

Expert Comment

by:phoffric
ID: 26093289
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?
0
 
LVL 32

Expert Comment

by:phoffric
ID: 26093312
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.
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.

 
LVL 32

Accepted Solution

by:
phoffric earned 1500 total points
ID: 26093413
When inserting the middle element, I believe you are inadvertently missing other elements. You can confirm this in your debugger stepping through each line (or use lots of printf statements).
0
 

Author Comment

by:xiromdim
ID: 26097026
I will try to change the function to void... I 'll come back soon.
0
 
LVL 32

Expert Comment

by:phoffric
ID: 26118005
I submitted recommendations to the author, which was incorporated into the code submitted in the follow-up question. http://www.experts-exchange.com/Programming/Languages/C/Q_25001363.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?
0
 

Author Closing Comment

by:xiromdim
ID: 31668311
very good advice, but he didn't give some code
0
 
LVL 32

Expert Comment

by:phoffric
ID: 26118285
Hi xiromdim,
I was just starting the dialog with you, and it ended in an hour. I would have answered further questions.
0

Featured Post

Concerto Cloud for Software Providers & ISVs

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

Learn how Concerto can help you.

Question has a verified solution.

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

Summary: This tutorial covers some basics of pointer, pointer arithmetic and function pointer. What is a pointer: A pointer is a variable which holds an address. This address might be address of another variable/address of devices/address of fu…
This is a short and sweet, but (hopefully) to the point article. There seems to be some fundamental misunderstanding about the function prototype for the "main" function in C and C++, more specifically what type this function should return. I see so…
The goal of this video is to provide viewers with basic examples to understand recursion in the C programming language.
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use for-loops in the C programming language.
Suggested Courses

840 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