Есть ли лучший способ найти наименьшего общего предка?
-
27-09-2019 - |
Вопрос
Я знаю, что подобные вопросы задавались и раньше, но я думаю, что мое решение намного проще.Особенно по сравнению с Википедия.
Пожалуйста, докажите, что я ошибаюсь!
Если у вас есть дерево с узлами, имеющими заданную структуру данных:
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 — количество узлов в дереве).
Решение
Мне ваш алгоритм кажется нормальным, по крайней мере, я не мог придумать ничего лучше.Обратите внимание, что вам не нужен родительский указатель;вместо этого вы можете спуститься по дереву, начиная с корня, и найти первый узел, ключ которого находится между двумя начальными ключами.
Однако ваша проблема не имеет ничего общего с той, которую решил Тарьян.Прежде всего, вы рассматриваете бинарные деревья, а он рассматривает n-арные деревья;но это, наверное, деталь.Что еще более важно, вы учитываете деревья поиска, а Тарьян рассматривает общие деревья (без порядка ключей).Ваша проблема намного проще, потому что в зависимости от ключа вы можете угадать, где в дереве должен находиться определенный узел.
Другие советы
Нет, я прошу прощения.Но ваш алгоритм не очень хорош.возьмите следующий BST:
10 \ \ 15 / \ 14 16
ваш алгоритм вернет 10 как наименьшего общего предка.
Таким образом, вы можете написать алгоритм, который берет, скажем, левый узел, затем переходит к его родительскому узлу, выполняет его по порядку и проверяет, было ли правое на выходе упорядоченного узла.
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
}