Math.Max Stack Overflow

Please support our C# advertiser: Programming Forums - DaniWeb Sister Site
Thread Solved

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

Math.Max Stack Overflow

 
1
  #1
Nov 9th, 2009
Hi guys, I've searched this, but can't find a solution. Basically what I'm doing is writing a binary search tree (which works) and balancing it with AVL (which almost works). As far as I can tell my AVL tree is implemented correctly, but I'm getting a stack overflow error at this part:

  1. private int GetHeight(Node<T> node)
  2. {
  3. if (node!=null)
  4. {
  5. return (1+Math.Max(GetHeight(node.LeftChild), GetHeight(node.RightChild)));
  6. }
  7. else return 0;
  8. }

I'm using this to get the height of the tree, which I later use to calculate the tree's balance factor. I develop on Linux, but I tested this code in Windows just to be sure it wasn't an issue with MonoDevelop.

I'm retrieving this value in a method by doing

  1. return (GetHeight(node.RightChild) - GetHeight(node.LeftChild));

Any idea what's causing this problem?
Reply With Quote Quick reply to this message  
Join Date: Feb 2009
Posts: 3,474
Reputation: sknake has much to be proud of sknake has much to be proud of sknake has much to be proud of sknake has much to be proud of sknake has much to be proud of sknake has much to be proud of sknake has much to be proud of sknake has much to be proud of sknake has much to be proud of sknake has much to be proud of 
Solved Threads: 633
Sponsor
sknake's Avatar
sknake sknake is online now Online
.NET Enthusiast
 
0
  #2
Nov 9th, 2009
What are the values of the statement when you get the stack overflow message? Is this a recursion issue? Post the code for your entire class.
Scott Knake
Custom Software Development
Apex Software, Inc.
Reply With Quote Quick reply to this message  
Join Date: Aug 2009
Posts: 470
Reputation: Ryshad has a spectacular aura about Ryshad has a spectacular aura about Ryshad has a spectacular aura about 
Solved Threads: 93
Ryshad's Avatar
Ryshad Ryshad is offline Offline
Posting Pro in Training
 
0
  #3
Nov 9th, 2009
Originally Posted by sknake View Post
What are the values of the statement when you get the stack overflow message? Is this a recursion issue? Post the code for your entire class.
The logic looks sound to me, how deep is the tree that you are checking? As sknake said, it looks likely to be a recursion issue, but we'd need to see your code to be sure
Please don't take for granted the work that solvers do for you. Take the time to fully understand the code they give you so that you might adapt it to future problems.

"Learning is more than absorbing facts, it is acquiring understanding.” - William Arthur Ward
Reply With Quote Quick reply to this message  
Join Date: Sep 2009
Posts: 11
Reputation: Benderbrau is an unknown quantity at this point 
Solved Threads: 0
Benderbrau Benderbrau is offline Offline
Newbie Poster
 
0
  #4
Nov 9th, 2009
My tree isn't large at all...I'm just inserting about 30 nodes. You can probably ignore anything from Delete() and below.


This is my Binary Tree class. Insert() is used to insert nodes into a non-balanced binary search tree. Insert2() is the same, except at the end I call Rebalance() with the previous node passed through.

  1. using System;
  2. using System.Collections.Generic;
  3.  
  4. namespace BinaryTreeLib
  5. {
  6.  
  7.  
  8. public class BinaryTree<T> : IBinaryTree<T> where T: IComparable
  9. {
  10. private Node<T> root; //keep track of the root
  11. private Node<T> _root; //used later
  12.  
  13. public void Insert(T nodeValue) //used to insert Node in non-blanaced binary search tree
  14. {
  15. Console.WriteLine("***Adding "+nodeValue+" to tree...");
  16. if (root == null)
  17. {
  18. Console.WriteLine("Tree is empty, so let's make a root...");
  19. root = new Node<T>(nodeValue);
  20. Console.WriteLine("Root is "+root.Value);
  21. }
  22. else
  23. {
  24. Node<T> currentNode = root;
  25. Node<T> previousNode = root;
  26.  
  27. while (currentNode != null)
  28. {
  29. if (currentNode.CompareTo(nodeValue) < 0)
  30. {//if current node is less, then goto next node (previous = current, current = previous's left child)
  31. previousNode = currentNode;
  32. currentNode = previousNode.LeftChild;
  33. //LeftChild.Insert(newNode);
  34. }
  35. else if (currentNode.CompareTo(nodeValue) > 0)
  36. {//if current node is greater, then goto next node (previous = current, current = previous's right child)
  37. previousNode = currentNode;
  38. currentNode = previousNode.RightChild;
  39. // Console.WriteLine(nodeValue+" is greater than "+previousNode.Value+"...");
  40. }
  41. }
  42.  
  43.  
  44. //update the node's parents
  45. if (previousNode.CompareTo(nodeValue) < 0)
  46. {
  47. Console.WriteLine(nodeValue+" is a left child of "+previousNode.Value);
  48. previousNode.LeftChild = new Node<T>(nodeValue, previousNode);
  49. }
  50. else
  51. {
  52. Console.WriteLine(nodeValue+" is a right child of "+previousNode.Value);
  53. previousNode.RightChild = new Node<T>(nodeValue, previousNode);
  54. }
  55.  
  56. }
  57. }
  58. public void Insert2(T nodeValue) //used to insert nodes in AVL balanced tree
  59. {
  60. Node<T> newNode = new Node<T>(nodeValue);
  61. Console.WriteLine("***Adding "+nodeValue+" to tree...");
  62. if (root == null)
  63. {
  64. Console.WriteLine("Tree is empty, so let's make a root...");
  65. root = newNode;//new Node<T>(nodeValue);
  66. Console.WriteLine("Root is "+root.Value);
  67. }
  68. else
  69. {
  70. Node<T> currentNode = root; //used to traverse through each node
  71. Node<T> previousNode = root; //used to store the last used node
  72.  
  73. while (currentNode != null)
  74. {
  75. if (currentNode.CompareTo(nodeValue) < 0)
  76. {//if current node is less, then goto next node (previous = current, current = previous's left child)
  77. previousNode = currentNode;
  78. currentNode = previousNode.LeftChild;
  79. //LeftChild.Insert(newNode);
  80. }
  81. else if (currentNode.CompareTo(nodeValue) > 0)
  82. {//if current node is greater, then goto next node (previous = current, current = previous's right child)
  83. previousNode = currentNode;
  84. currentNode = previousNode.RightChild;
  85. }
  86. }
  87.  
  88.  
  89. //update node's parents
  90. if (previousNode.CompareTo(nodeValue) < 0)
  91. {
  92. //Console.WriteLine(nodeValue+" is a left child of "+previousNode.Value);
  93. previousNode.LeftChild = new Node<T>(nodeValue, previousNode);
  94. }
  95. else
  96. {
  97. //Console.WriteLine(nodeValue+" is a right child of "+previousNode.Value);
  98. previousNode.RightChild = new Node<T>(nodeValue, previousNode);
  99. }
  100. ReBalance(previousNode);
  101. }
  102. }
  103. private void ReBalance(Node<T> node)
  104. {
  105. Node<T> parent = node.Parent;
  106. while (parent != null)
  107. {
  108. int balance = GetBalance(parent);
  109. if (Math.Abs(balance) == 2)
  110. {
  111. BalanceAt(parent, balance);
  112. }
  113. parent = parent.Parent;
  114. }
  115. }
  116. private void BalanceAt(Node<T> node, int balance)
  117. {
  118. if (balance == 2) //if balance factor is 2, then tree is unbalanced
  119. {
  120. int rightBalance = GetBalance(node.RightChild);
  121. if (rightBalance == 1 || rightBalance == 0)
  122. {
  123. RotateLeft(node);
  124. }
  125. else if (rightBalance == -1)
  126. {
  127. Console.WriteLine("Performing Complex R-L rotation at node " +node.Value);
  128. RotateRight(node.RightChild);
  129. RotateLeft(node);
  130. }
  131. }
  132. else if (balance == -2) //if balance factor is -2, then tree is unbalanced
  133. {
  134. int leftBalance = GetBalance(node.LeftChild);
  135. if (leftBalance == -1 || leftBalance == 0)
  136. {
  137. RotateRight(node);
  138. }
  139. else if (leftBalance == 1)
  140. {
  141. Console.WriteLine("Performing complex L-R Rotation at node " + node.Value);
  142. RotateLeft(node.LeftChild);
  143. RotateRight(node);
  144. }
  145. }
  146. }
  147. private int GetHeight(Node<T> node)
  148. {
  149. if (node!=null)
  150. {
  151. return (1+Math.Max(GetHeight(node.LeftChild), GetHeight(node.RightChild)));
  152. }
  153. else return 0;
  154. }
  155. private int GetBalance(Node<T> node)
  156. {
  157. if (node != null)
  158. {
  159. return (GetHeight(node.RightChild) - GetHeight(node.LeftChild));
  160. }
  161. else return 0;
  162. }
  163. private void RotateLeft(Node<T> node)
  164. {
  165. if (node == null)
  166. {
  167. return;
  168. }
  169. Node<T> pivot = node.RightChild;
  170. if (pivot == null)
  171. {
  172. return;
  173. }
  174. else
  175. {
  176. Console.WriteLine("Performing Basic Left Rotation at node " + node.Value);
  177. Node<T> nodesParent = node.Parent;
  178. bool isLeftChild = (nodesParent != null) && nodesParent.LeftChild == node;
  179. bool makeTreeRoot = (_root == node);
  180. node.RightChild = pivot.LeftChild;
  181. pivot.LeftChild = node;
  182. node.Parent = pivot;
  183. pivot.Parent = nodesParent;
  184. if (node.RightChild != null)
  185. {
  186. node.RightChild.Parent = node;
  187. }
  188. if (makeTreeRoot)
  189. {
  190. _root = pivot;
  191. }
  192. if (isLeftChild)
  193. {
  194. nodesParent.LeftChild = pivot;
  195. }
  196. else
  197. {
  198. if (nodesParent != null)
  199. {
  200. nodesParent.RightChild = pivot;
  201. }
  202. }
  203. }
  204. }
  205. private void RotateRight(Node<T> node)
  206. {
  207. if (node == null)
  208. {
  209. return;
  210. }
  211. Node<T> pivot = node.LeftChild;
  212. if (pivot==null)
  213. {
  214. return;
  215. }
  216. else
  217. {
  218. Console.WriteLine("Performing Basic Right Rotation at node " + node.Value);
  219. Node<T> nodesParent = node.Parent;
  220. bool isLeftChild = (nodesParent != null) && nodesParent.LeftChild == node;
  221. bool makeTreeRoot = (_root == node);
  222. root.LeftChild = pivot.RightChild;
  223. pivot.RightChild = node;
  224. node.Parent = pivot;
  225. pivot.Parent = nodesParent;
  226. if (node.LeftChild != null)
  227. {
  228. node.LeftChild.Parent = node;
  229. }
  230. if (makeTreeRoot)
  231. {
  232. _root = pivot;
  233. }
  234. if (isLeftChild)
  235. {
  236. nodesParent.LeftChild = pivot;
  237. }
  238. else
  239. {
  240. if (nodesParent != null)
  241. {
  242. nodesParent.RightChild = pivot;
  243. }
  244. }
  245. }
  246.  
  247. }
  248. public void Delete(T nodeValue)
  249. {
  250. }
  251. /// <summary>
  252. /// START PREORDER
  253. /// </summary>
  254. public void Preorder()
  255. {
  256. PreorderTraverse(root);
  257. }
  258. private void PreorderTraverse(Node<T> node)
  259. {
  260. if (node == null)
  261. return;
  262. Console.WriteLine(node.Value);
  263. PreorderTraverse(node.LeftChild);
  264. PreorderTraverse(node.RightChild);
  265. }
  266.  
  267. /// <summary>
  268. /// START INORDER
  269. /// </summary>
  270. public void Inorder()
  271. {
  272. InorderTraversal(root);
  273. }
  274. private void InorderTraversal(Node<T> node)
  275. {
  276. if (node == null)
  277. return;
  278. InorderTraversal(node.LeftChild);
  279. Console.WriteLine(node.Value);
  280. InorderTraversal(node.RightChild);
  281. }
  282.  
  283. /// <summary>
  284. /// START POSTORDER
  285. /// </summary>
  286. public void Postorder()
  287. {
  288. PostorderTraversal(root);
  289. }
  290. private void PostorderTraversal(Node<T> node)
  291. {
  292. if (node == null)
  293. return;
  294. PostorderTraversal(node.LeftChild);
  295. PostorderTraversal(node.RightChild);
  296. Console.WriteLine(node.Value);
  297. }
  298.  
  299.  
  300. public void MakeNull()
  301. { //just deleting the root for now...eventually will delete from leaf nodes up
  302. if (root != null)
  303. {
  304. //PostOrderDelete(root);
  305. root = null;
  306. }
  307. }
  308. private void PostOrderACE(Node<T> node, int currentLevel, List<int> levelCounts)
  309. {
  310. if (node.LeftChild != null)
  311. {
  312. PostOrderACE(node.LeftChild, currentLevel + 1, levelCounts);
  313. }
  314. if (node.RightChild != null)
  315. {
  316. PostOrderACE(node.RightChild, currentLevel +1, levelCounts);
  317. }
  318. levelCounts.Add(currentLevel);
  319. }
  320. public float ACE
  321. {
  322. get
  323. {
  324. if (root != null)
  325. {
  326. List<int> levelCounts = new List<int>();
  327. PostOrderACE(root, 1, levelCounts);
  328.  
  329. float total = 0.0F;
  330. float nodeCount = (float)levelCounts.Count;
  331. foreach (int i in levelCounts)
  332. {
  333. total += (float)i;
  334. }
  335. return total / nodeCount;
  336. }
  337. else return 0.0F;
  338. }
  339. }
  340. }
  341. }

And then to insert the nodes, I use these lines in my main class...

  1. int[] NodeValueList = {8,22,14,35,43,56,82,19,17,27,54,89,75,29,16,21,23,24,25,26,55,36,49,20,1,9,11,86,5,50};
  2. IBinaryTree<int> Tree = new BinaryTree<int>();
  3. foreach (int numbers in NodeValueList)
  4. {
  5. Tree.Insert2(numbers);
  6. }

My Node<T> class that is called is simply used to keep track of the node properties, such as Parent, Left and Right Child, and Value.
Reply With Quote Quick reply to this message  
Join Date: Aug 2009
Posts: 470
Reputation: Ryshad has a spectacular aura about Ryshad has a spectacular aura about Ryshad has a spectacular aura about 
Solved Threads: 93
Ryshad's Avatar
Ryshad Ryshad is offline Offline
Posting Pro in Training
 
1
  #5
Nov 9th, 2009
Have you tried stepping through the recursion to see what point the stack overflow occurs? I'm afraid i'm not overly familiar with debugging the call stack so someone else might offer a better way to find your problem, but looking at your code it would seem that the problem is in the recursive calls to GetHeight().
When the parent is the root node then the number of calls in the stack is equal to the total number of nodes. How many calls it takes to overflow the stack depends on the size of your stack and the size of the passed object. How big is a single node object and how big is your stack?
Please don't take for granted the work that solvers do for you. Take the time to fully understand the code they give you so that you might adapt it to future problems.

"Learning is more than absorbing facts, it is acquiring understanding.” - William Arthur Ward
Reply With Quote Quick reply to this message  
Join Date: Sep 2009
Posts: 11
Reputation: Benderbrau is an unknown quantity at this point 
Solved Threads: 0
Benderbrau Benderbrau is offline Offline
Newbie Poster
 
0
  #6
Nov 9th, 2009
Ah, got it! Thanks for the help everyone, it was a silly mistake. In line #222 i had
  1. root.LeftChild = pivot.RightChild;

I replaced root with node and everything's working fine! Whew! Sorry for the wasted time, it seems like I spend hours on silly errors like these! At least I know more about what causes a stack overflow now, ha.
Reply With Quote Quick reply to this message  
Join Date: Aug 2009
Posts: 470
Reputation: Ryshad has a spectacular aura about Ryshad has a spectacular aura about Ryshad has a spectacular aura about 
Solved Threads: 93
Ryshad's Avatar
Ryshad Ryshad is offline Offline
Posting Pro in Training
 
0
  #7
Nov 9th, 2009
Originally Posted by Benderbrau View Post
Ah, got it! Thanks for the help everyone, it was a silly mistake. In line #222 i had
  1. root.LeftChild = pivot.RightChild;

I replaced root with node and everything's working fine! Whew! Sorry for the wasted time, it seems like I spend hours on silly errors like these! At least I know more about what causes a stack overflow now, ha.
That is so often the way :p Glad you got this one under control. Remember to mark the thread as solved.
Please don't take for granted the work that solvers do for you. Take the time to fully understand the code they give you so that you might adapt it to future problems.

"Learning is more than absorbing facts, it is acquiring understanding.” - William Arthur Ward
Reply With Quote Quick reply to this message  
Join Date: Jun 2005
Posts: 2,056
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
 
-4
  #8
Nov 9th, 2009
Originally Posted by Ryshad View Post
Remember to mark the thread as solved.
Who cares?
All my posts may be redistributed under the GNU Free Documentation License.
Reply With Quote Quick reply to this message  
Join Date: Aug 2009
Posts: 470
Reputation: Ryshad has a spectacular aura about Ryshad has a spectacular aura about Ryshad has a spectacular aura about 
Solved Threads: 93
Ryshad's Avatar
Ryshad Ryshad is offline Offline
Posting Pro in Training
 
3
  #9
Nov 10th, 2009
Originally Posted by Rashakil Fol View Post
Who cares?
Firstly, me...secondly, a fair few of the solvers i've seen here on the boards. Marking a thread as solved indicates to others that the problem no longer requries attention, and a reminder to mark seems to be a very common closing comment.

You're hardly new to the boards, why make such an inane comment?
Please don't take for granted the work that solvers do for you. Take the time to fully understand the code they give you so that you might adapt it to future problems.

"Learning is more than absorbing facts, it is acquiring understanding.” - William Arthur Ward
Reply With Quote Quick reply to this message  
Join Date: Jun 2005
Posts: 2,056
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
 
-1
  #10
Nov 10th, 2009
Originally Posted by Ryshad View Post
Firstly, me...secondly, a fair few of the solvers i've seen here on the boards.
Really, you and other people? Who would have thought?

Originally Posted by Ryshad
Marking a thread as solved indicates to others that the problem no longer requries attention,
No, it indicates that people think it no longer requires attention, but adds a presumption of the correctness of the answer -- and frequently a thread's OP isn't qualified to judge that matter.

and a reminder to mark seems to be a very common closing comment.
So?
All my posts may be redistributed under the GNU Free Documentation License.
Reply With Quote Quick reply to this message  
Reply

Tags
algorithm, avltree, c#, datastructure

This thread has been marked solved.
Perhaps start a new thread instead?
Message:




Views: 1449 | Replies: 21
Thread Tools Search this Thread



Tag cloud for algorithm, avltree, c#, datastructure
About Us | Contact Us | Advertise | DaniWeb | Acceptable Use Policy | RSS Feed

©2003 - 2009 DaniWeb® LLC