Есть ли лучший способ найти самого низкого общего предка?

Question

Я знаю, что подобные вопросы были заданы раньше, но я думаю, что мое решение намного проще. Особенно по сравнению с Wikipedia.

Просьба доказать, что я ошибаюсь!

Если у вас есть дерево с узлами, которые имеют заданную структуру данных:

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

Ваш Алгоритм выглядит хорошо для меня, по крайней мере, я не мог придумать ничего лучшего. Обратите внимание, что вам не нужен указатель родителя; вместо этого вы можете спуститься по дереву, начиная с корня, и найти первый узел, ключ которого лежит между двумя начальными ключами.

Однако ваша проблема не имеет ничего общего с тем, что решил Тарьян. Прежде всего, вы рассматриваете бинарные деревья, и он рассматривает n-арные деревья; но это, вероятно, деталь. Что еще более важно, вы рассматриваете деревья поиска, в то время как Тарьян рассматривает общие деревья (без указания ключей). Ваша проблема намного проще, потому что в зависимости от ключа вы можете догадаться, где должен находиться определенный узел в дереве.

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 


}