3

ここにあるAlexAllainの例に基づいてバイナリツリーを作成しました。約5000〜6000の要素を追加した後、スタックオーバーフロー例外をスローします。スタックオーバーフローを防ぐ方法について何か考えはありますか？原因は、Insert()自分自身を再帰的に呼び出すことです。

2013年3月6日更新

スタックオーバーフローを回避するためにコードをリファクタリングした方法は次のとおりです。

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;
            }
        }
}
4

4 に答える 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;
      }
    }
  }
}
于 2013-03-05T19:59:33.280 に答える
1

提供された詳細の欠如による推測: 最悪の場合、6000 回の挿入後、スタックの深さがすべて 6000 回の再帰呼び出しであると想定します。おそらく 20 バイトの妥当なスタック フレーム サイズを想定すると、スタック サイズは 6000 * 20 = 120,000 バイトになります。スタック フレームが実際に 160 バイト (8 倍大きい) の場合、スタック サイズは 6000 * 160 で、1MB よりわずかに小さくなります。かな…要素数に制限はありますか？割り当てられたスタック サイズは?
上記のコメントは、実際に問題を解決する方法を示しています (平衡木)。追加するかもしれませんが、ほぼすべての再帰アルゴリズムを反復アルゴリズムに変換できます-それはそれほどエレガントではなく、正しくするのに労力がかかりますが、スタックがいっぱいになることはありません. しかし、入力要素の数に実際に制限がある場合 (あなたが考えているだけではありません)、挿入用のスタック フレームのサイズを決定し、スタック サイズを #elements * に適合するのに十分な大きさにすることができるようです *最悪の場合のスタック フレーム サイズに加えて、スタック上に余分なものがある場合はもう少し大きくなります。

于 2013-03-05T20:04:54.163 に答える
1

そのアルゴリズムはinsert再帰的ではありません。挿入する場所を検索するだけでよいので、そのための呼び出しのスタックは必要ありません。

于 2013-03-05T19:53:20.417 に答える
0

前述のように、最も可能性の高い原因は、再帰的な挿入呼び出しが多すぎることによるスタック オーバーフローです。

以下は、さまざまなオプションです

  1. 自己均衡ツリーを使用するhttp://en.wikipedia.org/wiki/Self-balancing_binary_search_tree

  2. 非再帰的なツリーの適切なアルゴリズムを使用しますn.この例を見てくださいC++を使用した二分木での非再帰的な加算関数

于 2013-03-05T20:00:23.943 に答える