| | |
Math.Max Stack Overflow
Please support our C# advertiser: Programming Forums - DaniWeb Sister Site
Thread Solved |
•
•
Join Date: Sep 2009
Posts: 11
Reputation:
Solved Threads: 0
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:
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
Any idea what's causing this problem?
C# Syntax (Toggle Plain Text)
private int GetHeight(Node<T> node) { if (node!=null) { return (1+Math.Max(GetHeight(node.LeftChild), GetHeight(node.RightChild))); } else return 0; }
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
C# Syntax (Toggle Plain Text)
return (GetHeight(node.RightChild) - GetHeight(node.LeftChild));
Any idea what's causing this problem?
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.
0
#3 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.
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
"Learning is more than absorbing facts, it is acquiring understanding.” - William Arthur Ward
•
•
Join Date: Sep 2009
Posts: 11
Reputation:
Solved Threads: 0
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.
And then to insert the nodes, I use these lines in my main class...
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.
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.
C# Syntax (Toggle Plain Text)
using System; using System.Collections.Generic; namespace BinaryTreeLib { public class BinaryTree<T> : IBinaryTree<T> where T: IComparable { private Node<T> root; //keep track of the root private Node<T> _root; //used later public void Insert(T nodeValue) //used to insert Node in non-blanaced binary search tree { Console.WriteLine("***Adding "+nodeValue+" to tree..."); if (root == null) { Console.WriteLine("Tree is empty, so let's make a root..."); root = new Node<T>(nodeValue); Console.WriteLine("Root is "+root.Value); } else { Node<T> currentNode = root; Node<T> previousNode = root; while (currentNode != null) { if (currentNode.CompareTo(nodeValue) < 0) {//if current node is less, then goto next node (previous = current, current = previous's left child) previousNode = currentNode; currentNode = previousNode.LeftChild; //LeftChild.Insert(newNode); } else if (currentNode.CompareTo(nodeValue) > 0) {//if current node is greater, then goto next node (previous = current, current = previous's right child) previousNode = currentNode; currentNode = previousNode.RightChild; // Console.WriteLine(nodeValue+" is greater than "+previousNode.Value+"..."); } } //update the node's parents if (previousNode.CompareTo(nodeValue) < 0) { Console.WriteLine(nodeValue+" is a left child of "+previousNode.Value); previousNode.LeftChild = new Node<T>(nodeValue, previousNode); } else { Console.WriteLine(nodeValue+" is a right child of "+previousNode.Value); previousNode.RightChild = new Node<T>(nodeValue, previousNode); } } } public void Insert2(T nodeValue) //used to insert nodes in AVL balanced tree { Node<T> newNode = new Node<T>(nodeValue); Console.WriteLine("***Adding "+nodeValue+" to tree..."); if (root == null) { Console.WriteLine("Tree is empty, so let's make a root..."); root = newNode;//new Node<T>(nodeValue); Console.WriteLine("Root is "+root.Value); } else { Node<T> currentNode = root; //used to traverse through each node Node<T> previousNode = root; //used to store the last used node while (currentNode != null) { if (currentNode.CompareTo(nodeValue) < 0) {//if current node is less, then goto next node (previous = current, current = previous's left child) previousNode = currentNode; currentNode = previousNode.LeftChild; //LeftChild.Insert(newNode); } else if (currentNode.CompareTo(nodeValue) > 0) {//if current node is greater, then goto next node (previous = current, current = previous's right child) previousNode = currentNode; currentNode = previousNode.RightChild; } } //update node's parents if (previousNode.CompareTo(nodeValue) < 0) { //Console.WriteLine(nodeValue+" is a left child of "+previousNode.Value); previousNode.LeftChild = new Node<T>(nodeValue, previousNode); } else { //Console.WriteLine(nodeValue+" is a right child of "+previousNode.Value); previousNode.RightChild = new Node<T>(nodeValue, previousNode); } ReBalance(previousNode); } } private void ReBalance(Node<T> node) { Node<T> parent = node.Parent; while (parent != null) { int balance = GetBalance(parent); if (Math.Abs(balance) == 2) { BalanceAt(parent, balance); } parent = parent.Parent; } } private void BalanceAt(Node<T> node, int balance) { if (balance == 2) //if balance factor is 2, then tree is unbalanced { int rightBalance = GetBalance(node.RightChild); if (rightBalance == 1 || rightBalance == 0) { RotateLeft(node); } else if (rightBalance == -1) { Console.WriteLine("Performing Complex R-L rotation at node " +node.Value); RotateRight(node.RightChild); RotateLeft(node); } } else if (balance == -2) //if balance factor is -2, then tree is unbalanced { int leftBalance = GetBalance(node.LeftChild); if (leftBalance == -1 || leftBalance == 0) { RotateRight(node); } else if (leftBalance == 1) { Console.WriteLine("Performing complex L-R Rotation at node " + node.Value); RotateLeft(node.LeftChild); RotateRight(node); } } } private int GetHeight(Node<T> node) { if (node!=null) { return (1+Math.Max(GetHeight(node.LeftChild), GetHeight(node.RightChild))); } else return 0; } private int GetBalance(Node<T> node) { if (node != null) { return (GetHeight(node.RightChild) - GetHeight(node.LeftChild)); } else return 0; } private void RotateLeft(Node<T> node) { if (node == null) { return; } Node<T> pivot = node.RightChild; if (pivot == null) { return; } else { Console.WriteLine("Performing Basic Left Rotation at node " + node.Value); Node<T> nodesParent = node.Parent; bool isLeftChild = (nodesParent != null) && nodesParent.LeftChild == node; bool makeTreeRoot = (_root == node); node.RightChild = pivot.LeftChild; pivot.LeftChild = node; node.Parent = pivot; pivot.Parent = nodesParent; if (node.RightChild != null) { node.RightChild.Parent = node; } if (makeTreeRoot) { _root = pivot; } if (isLeftChild) { nodesParent.LeftChild = pivot; } else { if (nodesParent != null) { nodesParent.RightChild = pivot; } } } } private void RotateRight(Node<T> node) { if (node == null) { return; } Node<T> pivot = node.LeftChild; if (pivot==null) { return; } else { Console.WriteLine("Performing Basic Right Rotation at node " + node.Value); Node<T> nodesParent = node.Parent; bool isLeftChild = (nodesParent != null) && nodesParent.LeftChild == node; bool makeTreeRoot = (_root == node); root.LeftChild = pivot.RightChild; pivot.RightChild = node; node.Parent = pivot; pivot.Parent = nodesParent; if (node.LeftChild != null) { node.LeftChild.Parent = node; } if (makeTreeRoot) { _root = pivot; } if (isLeftChild) { nodesParent.LeftChild = pivot; } else { if (nodesParent != null) { nodesParent.RightChild = pivot; } } } } public void Delete(T nodeValue) { } /// <summary> /// START PREORDER /// </summary> public void Preorder() { PreorderTraverse(root); } private void PreorderTraverse(Node<T> node) { if (node == null) return; Console.WriteLine(node.Value); PreorderTraverse(node.LeftChild); PreorderTraverse(node.RightChild); } /// <summary> /// START INORDER /// </summary> public void Inorder() { InorderTraversal(root); } private void InorderTraversal(Node<T> node) { if (node == null) return; InorderTraversal(node.LeftChild); Console.WriteLine(node.Value); InorderTraversal(node.RightChild); } /// <summary> /// START POSTORDER /// </summary> public void Postorder() { PostorderTraversal(root); } private void PostorderTraversal(Node<T> node) { if (node == null) return; PostorderTraversal(node.LeftChild); PostorderTraversal(node.RightChild); Console.WriteLine(node.Value); } public void MakeNull() { //just deleting the root for now...eventually will delete from leaf nodes up if (root != null) { //PostOrderDelete(root); root = null; } } private void PostOrderACE(Node<T> node, int currentLevel, List<int> levelCounts) { if (node.LeftChild != null) { PostOrderACE(node.LeftChild, currentLevel + 1, levelCounts); } if (node.RightChild != null) { PostOrderACE(node.RightChild, currentLevel +1, levelCounts); } levelCounts.Add(currentLevel); } public float ACE { get { if (root != null) { List<int> levelCounts = new List<int>(); PostOrderACE(root, 1, levelCounts); float total = 0.0F; float nodeCount = (float)levelCounts.Count; foreach (int i in levelCounts) { total += (float)i; } return total / nodeCount; } else return 0.0F; } } } }
And then to insert the nodes, I use these lines in my main class...
C# Syntax (Toggle Plain Text)
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}; IBinaryTree<int> Tree = new BinaryTree<int>(); foreach (int numbers in NodeValueList) { Tree.Insert2(numbers); }
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.
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?
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
"Learning is more than absorbing facts, it is acquiring understanding.” - William Arthur Ward
•
•
Join Date: Sep 2009
Posts: 11
Reputation:
Solved Threads: 0
0
#6 Nov 9th, 2009
Ah, got it! Thanks for the help everyone, it was a silly mistake. In line #222 i had
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.
C# Syntax (Toggle Plain Text)
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.
0
#7 Nov 9th, 2009
•
•
•
•
Ah, got it! Thanks for the help everyone, it was a silly mistake. In line #222 i had
C# Syntax (Toggle Plain Text)
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.
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
"Learning is more than absorbing facts, it is acquiring understanding.” - William Arthur Ward
3
#9 Nov 10th, 2009
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?
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
"Learning is more than absorbing facts, it is acquiring understanding.” - William Arthur Ward
-1
#10 Nov 10th, 2009
•
•
•
•
Firstly, me...secondly, a fair few of the solvers i've seen here on the boards.
•
•
•
•
Originally Posted by Ryshad
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.
All my posts may be redistributed under the GNU Free Documentation License.
![]() |
Similar Threads
- stack overflow at line 0 (JavaScript / DHTML / AJAX)
- Stack overflow issue (C++)
- Run time stack overflow error help (C++)
- Math.max prob???...XD (Java)
- Stack Overflow Error (C++)
- Stack Overflow Error (C#)
Other Threads in the C# Forum
- Previous Thread: programmatically sort manually built datagrid
- Next Thread: help for my final year research based project
Views: 1449 | Replies: 21
| Thread Tools | Search this Thread |
Tag cloud for algorithm, avltree, c#, datastructure
.net 2d access activedirectory ado.net algorithm app array asp.net associations bot c# c++ calendar chat class client code combobox custom database datagridview datastructure datetime dbconnection default degrees development dialog directrobot dll drawing dubai e-commerce eventhandlers excel exectuable expression file form forms gcd gdi+ google grid httpwebrequest image index javascript keypress label lisp list listbox login mailmerge math mdd mono msword mysql networking open operator oracle photoshop picturebox post programming read recursion remote remoting resource resourcefile richtextbox save saving softwaredevelopment sql sql-server ssh string syntactic table textbox totaldays treeview using-keyword vb vistaflaw visualbasic visualstudio webbrowser windows winforms wordautomation working wpf xml







