6

みなさん、こんにちは。以下のアルゴリズムを読んで、バイナリ検索ツリーで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）

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

ここで説明してくれてありがとう！

4

2 に答える 2

10

このアルゴリズムには末尾再帰が含まれます。質問のコンテキストでは、呼び出し元のスタック フレームを呼び出し先で再利用できます。言い換えれば、関数呼び出しのネストされたシーケンスはすべて、バケツ旅団のように結果を渡すだけです。したがって、実際に必要なスタック フレームは 1 つだけです。

詳細については、Wikipedia のTail Callを参照してください。

于 2010-10-20T15:24:50.813 に答える
4

スタック領域が必要なため、アルゴリズムの再帰的な実装には 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セマンティクスを変更しないようにするには、 を追加する必要があることに注意してください。)

于 2010-10-20T15:29:22.560 に答える