このアルゴリズムの空間の複雑さがO（1）である理由

Question

こんにちは：以下のアルゴリズムを読んで、バイナリ検索ツリーに2つのノードの最も低い共通の祖先を見つけます。

 /* A binary tree node has data, pointer to left child
   and a pointer to right child */
 struct node
 {
  int data;
  struct node* left;
  struct node* right;
 };

 struct node* newNode(int );

/* Function to find least comman ancestor of n1 and n2 */
int leastCommanAncestor(struct node* root, int n1, int n2)
{
 /* If we have reached a leaf node then LCA doesn't exist
 If root->data is equal to any of the inputs then input is
 not valid. For example 20, 22 in the given figure */
 if(root == NULL || root->data == n1 || root->data == n2)
 return -1;

 /* If any of the input nodes is child of the current node
 we have reached the LCA. For example, in the above figure
 if we want to calculate LCA of 12 and 14, recursion should
 terminate when we reach 8*/
 if((root->right != NULL) &&
  (root->right->data == n1 || root->right->data == n2))
  return root->data;
 if((root->left != NULL) &&
 (root->left->data == n1 || root->left->data == n2))
 return root->data;   

 if(root->data > n1 && root->data < n2)
   return root->data;
 if(root->data > n1 && root->data > n2)
  return leastCommanAncestor(root->left, n1, n2);
 if(root->data < n1 && root->data < n2)
  return leastCommanAncestor(root->right, n1, n2);
}    

上記の関数は、N1がN2よりも小さいことを前提としていることに注意してください。時間の複雑さ：o（n）空間の複雑さ：o（1）

このアルゴリズムは再帰的です。再帰関数呼び出しを呼び出すと、関数引数とその他の関連するレジスタがスタックにプッシュされるため、余分なスペースが必要です。一方、再帰的な深さはのサイズまたは高さに関連しています。木、たとえば、o（n）になる方が理にかなっていますか？

ここで説明をありがとう！

Answer 1

アルゴリズムの再帰的実装には、必要なスタックスペースのためにO（n）スペースが必要であると言うのは正しいことですが、テールの再帰のみを使用します。つまり、ループを備えたO（1）スペースを使用するために再実装できます。

int leastCommanAncestor(struct node* root, int n1, int n2)
    while (1)
    {
     /* If we have reached a leaf node then LCA doesn't exist
     If root->data is equal to any of the inputs then input is
     not valid. For example 20, 22 in the given figure */
     if(root == NULL || root->data == n1 || root->data == n2)
     return -1;

     /* If any of the input nodes is child of the current node
     we have reached the LCA. For example, in the above figure
     if we want to calculate LCA of 12 and 14, recursion should
     terminate when we reach 8*/
     if((root->right != NULL) &&
      (root->right->data == n1 || root->right->data == n2))
      return root->data;
     if((root->left != NULL) &&
     (root->left->data == n1 || root->left->data == n2))
     return root->data;   

     if(root->data > n1 && root->data < n2)
       return root->data;
     if(root->data > n1 && root->data > n2)
      root = root->left;
     else if(root->data < n1 && root->data < n2)
      root = root->right;
    }
}

（ご了承ください else セマンティクスを変更しないようにするには、追加する必要があります。）

Answer 2

このアルゴリズムには、尾の再帰が含まれます。質問の文脈では、発信者のスタックフレームをCalleeによって再利用できます。言い換えれば、機能の呼び出しのネストされたすべてのシーケンスは、結果をバケツ旅団のように渡すことです。その結果、実際に必要なスタックフレームは1つだけです。

詳細については、参照してください テールコール ウィキペディアで。