Stackoverflow exception on BST transition

Question

I use BST (binary search tree) based on links in C ++ for one of my purposes. I wrote my whole class, and everything works well, but my job asks me to talk about runtime:

a. A sorted list of 50000, 75000, and 100000 items b. A random list of 50000, 75000, and 100000 items 

Well, I can insert numbers, but also asks me to call the FindHeight() and CountLeaves() methods on the tree. My problem is that I implemented two functions using recursion . Since I have such a large list of numbers, I get a stackoverflow exception.

Here is my class definition:

 template <class TItem> class BinarySearchTree { public: struct BinarySearchTreeNode { public: TItem Data; BinarySearchTreeNode* LeftChild; BinarySearchTreeNode* RightChild; }; BinarySearchTreeNode* RootNode; BinarySearchTree(); ~BinarySearchTree(); void InsertItem(TItem); void PrintTree(); void PrintTree(BinarySearchTreeNode*); void DeleteTree(); void DeleteTree(BinarySearchTreeNode*&); int CountLeaves(); int CountLeaves(BinarySearchTreeNode*); int FindHeight(); int FindHeight(BinarySearchTreeNode*); int SingleParents(); int SingleParents(BinarySearchTreeNode*); TItem FindMin(); TItem FindMin(BinarySearchTreeNode*); TItem FindMax(); TItem FindMax(BinarySearchTreeNode*); }; 

FindHeight () implementation

 template <class TItem> int BinarySearchTree<TItem>::FindHeight() { return FindHeight(RootNode); } template <class TItem> int BinarySearchTree<TItem>::FindHeight(BinarySearchTreeNode* Node) { if(Node == NULL) return 0; return 1 + max(FindHeight(Node->LeftChild), FindHeight(Node->RightChild)); } 

CountLeaves () function

 template <class TItem> int BinarySearchTree<TItem>::CountLeaves() { return CountLeaves(RootNode); } template <class TItem> int BinarySearchTree<TItem>::CountLeaves(BinarySearchTreeNode* Node) { if(Node == NULL) return 0; else if(Node->LeftChild == NULL && Node->RightChild == NULL) return 1; else return CountLeaves(Node->LeftChild) + CountLeaves(Node->RightChild); } 

I tried to think about how I can implement two methods without recursion, but I'm completely at a dead end. Does anyone have any ideas?

Answer 1

Recursion on a tree with 100,000 nodes should not be a problem if it is balanced. The depth will be only 17, which will not use too much stack in the shown implementations. (log2(100,000) = 16.61) . Thus, it seems that the code that builds the tree does not balance it correctly.

Answer 2

I found this page very interesting because it talks about a mechanism for converting a function that uses recursion into one that uses iteration.

It has examples showing the code.

Answer 3

To count leaves without recursion, use the concept of an iterator, for example, using STL for the RB tree underlying std::set and std::map ... Create a begin() and end() function for you tree that defines the first ordinal and the last node (in this case, the left-most node, and then the right-most node). Then create a function called

BinarySearchTreeNode* increment(const BinarySearchTreeNode* current_node)

that for a given current_node will return a pointer to the next node in the tree. Remember that to complete this implementation, you will need an extra parent pointer in your node type to help with the iteration process.

Your algorithm for increment() will look something like this:

• Check if there is a correct child for the current node.
• If there is a right child, use the while loop to find the leftmost node of this right subtree. This will be the "next" node. Otherwise, go to step # 3.
• If there is no child right in the current node, then check if the current node is the left-descendant of its parent node.
• If step # 3 is true, then the “next” node is the parent node, so you can stop at this stage, otherwise go to the next step.
• If step # 3 was false, then the current node is the right parent of the parent. Thus, you will need to move on to the next parent node using a while loop until you meet a node, which is the left-descendant of the parent node. The parent of this left-child node will then be the "next" node, and you can stop.
• Finally, if step # 5 takes you back to the root, then the current node is the last node in the tree, and the iterator will reach the end of the tree.

Finally, you will need the bool leaf(const BinarySearchTreeNode* current_node) function bool leaf(const BinarySearchTreeNode* current_node) , which will check if the given node is a node leaf. Thus, the counter function can simply iterate over the tree and find all leaf nodes, returning the final count after its completion.

If you want to measure the maximum depth of an unbalanced tree without recursion, you must track the depth at which the node was inserted in your tree insert() function. It may just be a variable in your node type, which is set when the node is inserted into the tree. Then you can iterate through three and find the maximum node leaf depth.

By the way, the complexity of this method, unfortunately, will be O (N) ... nowhere is as beautiful as O (log N).

Answer 4

You may need to figure this out by inserting. Store the heights of the nodes, add an integer field, such as height in the Node object. Also have height counters and leaves for the tree. When you insert a node, if its parent has (had) a leaf, the number of leaves does not change, but if not, increase the number of leaves by 1. Also, the height of the new Node is equal to the height of the parent + 1, therefore if it is greater than the current height of the tree, and then update it. His homework, so I will not help with the actual code

Answer 5

Balance your tree from time to time. If your tree gets stackoverflow on FindHeight (), it means your tree is uneven. If the tree is balanced, it should have a depth of about 20 knots for 100,000 elements.

The simplest (but rather slow) way to balance an unbalanced binary tree is to allocate a TItem array TItem enough to store all the data in the tree, insert all the data into it in a sorted order, and delete all the nodes. Then rebuild the tree from the array recursively. The root is the node in the middle. root->left is the middle of the left half, root->right is the middle of the right half. Repeat recursively. This is the easiest way to rebalance, but it is slow and takes a lot of memory temporarily. On the other hand, you only need to do this when you find that the tree is very unbalanced (the depth of the insert is greater than 100).

Another (best) option is to balance during insertions. The most intuitive way to do this is to keep track of how many nodes are under the current node. If the right child has twice as many "child" nodes as the left child, "turn" to the left. And vice versa. There installations on how to make a tree rotate all over the Internet. This makes the inserts a little slower, but then you do not have random massive stalls that the first option creates. On the other hand, you must constantly update all the "child" counts as you rotate, which is not trivial.