Copying a sorted array to a balanced inorder Binary Search Tree

Please support our C++ advertiser: Programming Forums - DaniWeb Sister Site
Thread Solved
1 2

•
•
Join Date: Jan 2009
Posts: 11
Reputation: RingmasterTJ is an unknown quantity at this point 
Solved Threads: 0
RingmasterTJ RingmasterTJ is offline Offline
Newbie Poster

Copying a sorted array to a balanced inorder Binary Search Tree

 
0
  #1
Jan 21st, 2009
Hey everyone,

So, for my C++ course I am implementing a Binary Search Tree. In this Binary Search Tree we are to create a function to copy the values of a passed array into a Balanced Binary Search Tree that will render a correct inorder traversal.

I.E. an array of 0, 1, 2 will be in the tree in Root->1, Left->0, Right->2

I think I'm pretty close to figuring out the function (which is good considering how long I've been working on it ). However, I'm having issues on figuring out not only my base case, but also if passing mid in is the correct way to go about "altering" my values.

I know line 25 is wrong, as well as (I think) line 20 but I'm not sure where to go from here...Any help would be greatly appreciated!

PS: The while loop in the first function is to find out what the highest subscript with a stored value in the array is. We are guaranteed to be passed a statically allocated array of 99 elements, but we have to find out how many elements are in the array. Thus the loop.

c++ Syntax (Toggle Plain Text) 
  1. //------------------------------ arrayToBSTree --------------------------------
  2. void BSTree::arrayToBSTree(NodeData *data[]) {
  3. 	this->makeEmpty();
  4. 	int i = 0;
  5. 	int high = i;
  6. 	while(data[i] != NULL && i <= 99) {
  7. 		high = i;
  8. 		i++;
  9. 	}
  10. 	this->overallRoot = toTreeHelper(data, 0, high, this->overallRoot);
  11. }
  12.  
  13. //------------------------------ toTreeHelper ---------------------------------
  14. BSTree::Node* BSTree::toTreeHelper(NodeData *data[], int low, int high, 
  15. 								   Node *root) {
  16. 	int mid = (low + high) / 2;
  17. 	root = new Node;
  18. 	root->left = root->right = NULL;
  19. 	root->data = NULL;
  20. 	if(mid != 0) {
  21. 		root->left = toTreeHelper(data, low, mid, root->left);
  22. 	}
  23. 	root->data = data[mid];
  24. 	data[mid] = NULL;
  25. 	if(mid != 0 || mid != high - 1) {
  26. 		root->right = toTreeHelper(data, mid + 1, high, root->right);
  27. 	}
  28. 	return root;
  29. }
Reply With Quote Quick reply to this message  
•
•
Join Date: May 2008
Posts: 639
Reputation: Murtan is a jewel in the rough Murtan is a jewel in the rough Murtan is a jewel in the rough Murtan is a jewel in the rough 
Solved Threads: 103
Murtan Murtan is offline Offline
Practically a Master Poster

Re: Copying a sorted array to a balanced inorder Binary Search Tree

 
0
  #2
Jan 22nd, 2009
I'd like to experiment with the code to try it, but in the interest of a quick answer, try low < mid on line 20 and mid < high on line 25.

Basic translation: If there are values between low and high that are lower than mid, add them to the left. If there are values between low and high that are higher than mid, add them to the right.
Reply With Quote Quick reply to this message  
•
•
Join Date: Jun 2005
Posts: 2,055
Reputation: Rashakil Fol is just really nice Rashakil Fol is just really nice Rashakil Fol is just really nice Rashakil Fol is just really nice 
Solved Threads: 139
Team Colleague
Rashakil Fol's Avatar
Rashakil Fol Rashakil Fol is offline Offline
Super Senior Demiposter

Re: Copying a sorted array to a balanced inorder Binary Search Tree

 
2
  #3
Jan 22nd, 2009
It makes no sense to check if mid != 0. How could mid be 0? Well, in most cases, mid could not be 0, except at the very left edge of the tree. So your checks for the base case are bad.

Basically your hard job is to consider the cases where high - low is 0 (if possible), 1 (if possible), 2, 3, maybe 4, and in general, even or odd.

Also, you should look twice at your arrayToBSTree function: you might go past the end of the array.

Basically, this problem is designed to get you to practice thinking about off-by-one errors.
Reply With Quote Quick reply to this message  
•
•
Join Date: Jan 2009
Posts: 11
Reputation: RingmasterTJ is an unknown quantity at this point 
Solved Threads: 0
RingmasterTJ RingmasterTJ is offline Offline
Newbie Poster

Re: Copying a sorted array to a balanced inorder Binary Search Tree

 
0
  #4
Jan 22nd, 2009
Appreciate the help Murtan, but unfortunately, that doesn't quite give the optimal balance for the tree. Another big sticking point with me...
Last edited by RingmasterTJ; Jan 22nd, 2009 at 2:09 am.
Reply With Quote Quick reply to this message  
•
•
Join Date: May 2008
Posts: 639
Reputation: Murtan is a jewel in the rough Murtan is a jewel in the rough Murtan is a jewel in the rough Murtan is a jewel in the rough 
Solved Threads: 103
Murtan Murtan is offline Offline
Practically a Master Poster

Re: Copying a sorted array to a balanced inorder Binary Search Tree

 
0
  #5
Jan 22nd, 2009
Ok, so what kind of tree does it build?

How is it sub-optimal?

What would you have to change to make it optimal?
Reply With Quote Quick reply to this message  
•
•
Join Date: Jun 2005
Posts: 2,055
Reputation: Rashakil Fol is just really nice Rashakil Fol is just really nice Rashakil Fol is just really nice Rashakil Fol is just really nice 
Solved Threads: 139
Team Colleague
Rashakil Fol's Avatar
Rashakil Fol Rashakil Fol is offline Offline
Super Senior Demiposter

Re: Copying a sorted array to a balanced inorder Binary Search Tree

 
1
  #6
Jan 22nd, 2009
If you want optimal balance, you'll need to think carefully about the case where the size of the segment you're working on is a power of two. You need to split that cleanly in half. Are you splitting it cleanly in half?

Also, what do you think the value of root->left is in:
C++ Syntax (Toggle Plain Text) 
  1. root->left = toTreeHelper(data, low, mid, root->left);
Reply With Quote Quick reply to this message  
•
•
Join Date: May 2008
Posts: 639
Reputation: Murtan is a jewel in the rough Murtan is a jewel in the rough Murtan is a jewel in the rough Murtan is a jewel in the rough 
Solved Threads: 103
Murtan Murtan is offline Offline
Practically a Master Poster

Re: Copying a sorted array to a balanced inorder Binary Search Tree

 
0
  #7
Jan 22nd, 2009
Ok, so I have the values 0,1,2,3,4,5,6,7,8,9,10 in those positions in the input array...

You caclulate mid as (low + high) /2 so the first mid is 5?

we put 5 at the root and iterate left with (0,4) and right with (6,10)

(0,4): mid=2 we put 2 to the left of 5 [left: (0,1) right: (3,4)]
(0,1): mid=0 we put 0 to the left of 2 [left: none right: (1,1)]
(1,1): mid=1 we put 1 to the right of 0 [none]
(3,4): mid=3 we put 3 to the right of 2 [left:none right: (4,4)]
(4,4): mid=4 we put 4 to the right of 3

(6,10): mid=8 we put 8 to the right of 5 [left: (6,7) right: (9,10)]
(6,7): mid=6 we put 6 to the left of 8 [left: none right: (7,7)]
(7,7): mid=7 we put 7 to the right of 6
(9,10): mid=9 we put 9 to the right of 8 [left:none right: (10,10)]
(10,10): mid=10 we put 10 to the right of 9 [none]

so we built something like:
C++ Syntax (Toggle Plain Text) 
  1.        5
  2.     2      8
  3.  0   3   6   9
  4. z 1 z 4 z 7 z 10

The z's are empty nodes. How much more balanced does that need to be?
Last edited by Murtan; Jan 22nd, 2009 at 2:37 am. Reason: should have drawn the tree in notepad
Reply With Quote Quick reply to this message  
•
•
Join Date: Jan 2009
Posts: 11
Reputation: RingmasterTJ is an unknown quantity at this point 
Solved Threads: 0
RingmasterTJ RingmasterTJ is offline Offline
Newbie Poster

Re: Copying a sorted array to a balanced inorder Binary Search Tree

 
0
  #8
Jan 22nd, 2009
Wow, you both are amazing. Thank you so much. You guys not only helped me to get the program to work, but made me find bugs I did not even realize I had.

Again, thank you, I really appreciate both of you taking time out of your day to help me get this ironed out!
Reply With Quote Quick reply to this message  
•
•
Join Date: Jan 2009
Posts: 2
Reputation: monster8 is an unknown quantity at this point 
Solved Threads: 0
monster8 monster8 is offline Offline
Newbie Poster

Re: Copying a sorted array to a balanced inorder Binary Search Tree

 
0
  #9
Jan 22nd, 2009
what was changed to get it to work?
Reply With Quote Quick reply to this message  
•
•
Join Date: Jan 2009
Posts: 11
Reputation: RingmasterTJ is an unknown quantity at this point 
Solved Threads: 0
RingmasterTJ RingmasterTJ is offline Offline
Newbie Poster

Re: Copying a sorted array to a balanced inorder Binary Search Tree

 
0
  #10
Jan 22nd, 2009
The values I was passing in were off, that was the big issue. & as Murtan stated, the checks should have been changed.
Reply With Quote Quick reply to this message  
Reply
1 2

Quick Reply to Thread
This thread has been marked solved.
Perhaps start a new thread instead?
•
•
•
•
•
•
•
•
Message:
•
•
•
•



Other Threads in the C++ Forum


Views: 1428 | Replies: 10
Thread Tools Search this Thread



Tag cloud for C++
6 add api array arrays assignment beginner binary bitmap c++ c/c++ calculator char class classes code compile compiler console conversion convert count data delete desktop directshow dll encryption error file forms fstream function functions game getline givemetehcodez google graph homeworkhelper iamthwee ifstream input int integer java lazy lib linkedlist linux loop looping loops map math matrix memory multidimensional newbie news node number output parameter pointer problem program programming project proxy python random read recursion recursive reference return sort string strings struct studio system template templates text tree unix url variable vector video visual visualstudio win32 windows winsock word wordfrequency wxwidgets
About Us | Contact Us | Advertise | DaniWeb | Acceptable Use Policy | RSS Feed

©2003 - 2009 DaniWeb® LLC