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

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

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

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

Answer 2

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


}

Answer 3

Нет, я прошу прощения. Но твой алгоритм не хорош. возьмите следующий BST:

10
  \
   \
   15
  / \
 14 16

Ваш алгоритм вернет 10 как наименьший общий предок.

Таким образом, вы могли бы написать алгоритм, который принимает, скажем, левый узел и затем переходит к его родительскому узлу и запускает его по порядку и проверяет, было ли право в выходных данных по порядку