هل هناك طريقة أفضل للعثور على أدنى سلف مشترك?

Question

أنا أعرف مماثلة الأسئلة طرحت من قبل لكن أعتقد أن الحل أبسط بكثير.لا سيما بالمقارنة مع ويكيبيديا.

يرجى يثبت لي خطأ!

إذا كان لديك شجرة مع العقد أن يكون بالنظر إلى بنية البيانات:

struct node
{
    node * left;
    node * right;
    node * parent;
    int key;
}

هل يمكن كتابة دالة مثل هذا:

node* LCA(node* m, node* n)
{
    // determine which of the nodes is the leftmost
    node* left = null;
    node* right = null;
    if (m->key < n->key)
    {
        left = m;
        right = n;
    }
    else
    {
        left = n;
        right = m;
    }
    // start at the leftmost of the two nodes,
    // keep moving up the tree until the parent is greater than the right key
    while (left->parent && left->parent->key < right->key)
    {
        left = left->parent;
    }
    return left;
}

هذا الكود بسيط جدا و أسوأ الأحوال O(n), متوسط الحال ربما O(logn) ، خاصة إذا كانت شجرة متوازنة (حيث n هو عدد العقد في الشجرة).

Answer 1

خوارزمية الخاص بك تبدو بخير بالنسبة لي على الأقل لم أستطع التفكير في أي شيء أفضل.لاحظ أنك لا تحتاج الأم المؤشر ؛ بدلا من ذلك يمكنك الذهاب إلى أسفل الشجرة بدءا من جذورها ، و العثور على العقدة الأولى التي المفتاح يضع بين اثنين الأولي المفاتيح.

بيد أن المشكلة لا علاقة له مع أحد Tarjan حلها.أولا عليك أن تنظر الأشجار الثنائية و هو يعتبر n-ary الأشجار ؛ ولكن ربما هذا هو التفصيل.والأهم من ذلك هو أنك تنظر أشجار البحث ، في حين Tarjan ترى العامة الأشجار (لا يأمر على مفاتيح).المشكلة أبسط من ذلك بكثير ، لأن اعتمادا على المفتاح يمكنك تخمين حيث بعض عقدة في الشجرة.

Answer 2

لا, أنا آسف.ولكن الخوارزمية الخاصة بك ليست جيدة.تأخذ التالية BST:

10
  \
   \
   15
  /  \
 14  16

you'r خوارزمية عودة 10 أقل سلف مشترك.

وبالتالي يمكن كتابة الخوارزمية التي تأخذ تقول تركت عقدة من الذهاب إلى الأم في النظام على أن تحقق إذا كان الحق في إخراج في النظام

Answer 3

Node* getAncestor( Node* root, Node* node1 , Node* node2 )
{
    if( root->val > node1->val && root->val > node2->val )
        getAncestor( root->left , node1 , node2 );
    //recursive call with left subtree

    if( root->val < node1->val && root->val < node2->val )
        getAncestor( root->right , node1 , node2 );
    //recursive call with right subtree

    return root ;
    //returning the root node as ancestor

    //initial call is made with the tree's root node
    //node1 and node2 are nodes whose ancestor is to be located


}