logo标签列表

二叉树堆栈溢出

c++binary-treestack-overflow
3
我已经基于Alex Allain的示例创建了一个基于二叉树的数据结构。在向其中添加大约5000-6000个元素后，它会抛出堆栈溢出异常。有什么方法可以防止堆栈溢出？Insert() 调用自身递归是导致这种情况发生的原因。 更新 3/6/2013 以下是我重构代码以避免堆栈溢出的方式：
void Insert(Key_T key, Value_T val, QuickMapNode<Key_T, Value_T> *leaf)
{
    while (true)
        if(key < leaf->key)
        {
            if(leaf->left) leaf = leaf->left;
            else
            {
                leaf->left = new QuickMapNode<Key_T, Value_T>;
                leaf->left->key = key;
                leaf->left->val = val;
                leaf->left->parent = leaf;
                leaf->left->left = NULL;    // Sets the left child of the child node to null
                leaf->left->right = NULL;   // Sets the right child of the child node to null
                break;
            }  
        }
        else if (key >= leaf->key)
        {
            if(leaf->right) leaf = leaf->right;
            else
            {
                leaf->right = new QuickMapNode<Key_T, Value_T>;
                leaf->right->key = key;
                leaf->right->val = val;
                leaf->right->parent = leaf;
                leaf->right->left = NULL;  // Sets the left child of the child node to null
                leaf->right->right = NULL; // Sets the right child of the child node to null
                break;
            }
        }
}
我认为根据输入模式，您可能会遇到堆栈溢出的问题。比如说，如果输入已经排序，那么它就变成了“倾斜树”，这会导致递归堆栈深度达到6000，这是非常巨大的。 - sundar
1
你可能需要平衡树，比如AVL或红黑树。 - zch
添加一个函数来跟踪树的最大深度。对于平衡良好的树，它应该略高于12。 - andre
一种不需要使用自平衡树就能“平衡”树的简单方法是在插入元素之前对它们进行随机排序。如果树的不平衡是由于这个原因造成的，那么这种方法可能会解决问题。 - Tom
另一种简单的方法是跟踪每个操作的最小/最大高度，当它超过最优值的4倍（12x4〜48）时，以完全平衡的方式将所有节点移动到新树中，然后进行交换。这比实时平衡要容易得多，尽管会更加“抖动”。 - Mooing Duck
4个回答
5
就像Öö Tiib所说，您应该将insert更改为非递归。每个递归函数都可以通过在其他数据结构中存储将要进入堆栈的数据来转换为非递归函数。这样，您就可以将堆用于这些数据，而不需要在堆栈上进行函数调用（返回地址等）。您通常可以使用类似堆栈的向量或列表：获取（并弹出）向量的back()以获取当前参数，并在当前代码会递归调用自身的地方，您push_back()将要传递给递归函数调用的内容。

这是您链接中的insert()方法的迭代版本：

void btree::insert(int key, node *leaf)
{
  std::list<node*> leafs;
  leafs.push_back(leaf);

  while (leafs.size() > 0)
  {
    leaf = leafs.back();
    leafs.pop_back();
    if(key < leaf->key_value)
    {
      if(leaf->left!=NULL)
        leafs.push_back(leaf->left);
      else
      {
        leaf->left=new node;
        leaf->left->key_value=key;
        leaf->left->left=NULL;    //Sets the left child of the child node to null
        leaf->left->right=NULL;   //Sets the right child of the child node to null
      }  
    }
    else if(key>=leaf->key_value)
    {
      if(leaf->right!=NULL)
        leafs.push_back(leaf->right);
      else
      {
        leaf->right=new node;
        leaf->right->key_value=key;
        leaf->right->left=NULL;  //Sets the left child of the child node to null
        leaf->right->right=NULL; //Sets the right child of the child node to null
      }
    }
  }
}

我运行了这段代码，看起来它能工作。但是它比递归版本要慢得多，不确定为什么会这样... 两个版本都可以很好地处理10000个及以上元素，所以可能在你的实现中还有其他问题...
实际上，当像我们在这里一样遍历二叉树时，没有必要存储任何先前的信息，因为我们不进行回溯。一旦找到新元素的位置，我们就完成了。所以我们可以完全摆脱列表/向量：
void btree::insert(int key, node *leaf)
{
  while (leaf != NULL)
  {
    if(key < leaf->key_value)
    {
      if(leaf->left!=NULL)
        leaf = leaf->left;
      else
      {
        leaf->left=new node;
        leaf->left->key_value=key;
        leaf->left->left=NULL;    //Sets the left child of the child node to null
        leaf->left->right=NULL;   //Sets the right child of the child node to null
        return;
      }  
    }
    else if(key>=leaf->key_value)
    {
      if(leaf->right!=NULL)
        leaf = leaf->right;
      else
      {
        leaf->right=new node;
        leaf->right->key_value=key;
        leaf->right->left=NULL;  //Sets the left child of the child node to null
        leaf->right->right=NULL; //Sets the right child of the child node to null
        return;
      }
    }
  }
}
你还可以从自平衡树中获得更好的性能。我最喜欢的是AA树。 - hookenz
1
制作一个非递归的insert算法。您只需要搜索插入位置，因此不需要调用堆栈。
我该怎么做呢？你有没有一个不使用递归调用的例子或二叉树？谢谢。 - user152949
1
由于缺乏提供的细节，我们做出猜测：假设最坏情况是在6000次插入后，堆栈深度为6000个递归调用。假设合理的堆栈帧大小可能为20字节 - 那么堆栈大小为6000 * 20 = 120,000字节。如果堆栈帧实际上是160字节（8倍大），则堆栈大小为6000 * 160，略小于1MB。我想知道...你的元素数量有限制吗？分配的堆栈大小是多少？
以上评论告诉您如何实际解决问题（平衡树）。我可以补充说，几乎任何递归算法都可以转换为迭代算法 - 它不够优雅，并且需要努力才能做到正确，但是您不会填满堆栈。但是，如果确实存在（不仅是您认为存在）输入元素数量的限制，则似乎您可以确定插入的堆栈帧大小，并使堆栈大小足够大以适应#elements * stack frame size，最坏情况，再加上一些额外的堆栈空间。
0
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接