Рубрики

Алгоритм самого низкого общего предка Тарьяна

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

Нам дано дерево (может быть расширено до группы DAG), и у нас есть много запросов вида LCA (u, v), то есть найти LCA узлов 'u' и 'v'.

Мы можем выполнить эти запросы за O (N + QlogN), используя RMQ , где O (N) время для предварительной обработки и O (log N) для ответа на запросы, где
N = количество узлов и
Q = количество запросов, на которые нужно ответить.

Можем ли мы сделать лучше, чем это? Можем ли мы сделать за линейное (почти) время? Да.
В статье представлен автономный алгоритм, который выполняет эти запросы примерно за O (N + Q) времени . Хотя это не совсем линейно, поскольку в анализе временной сложности участвует обратная функция Аккермана. Для более подробной информации об обратной функции Аккермана смотрите это . Точно так же можно сказать, что обратная функция Аккермана остается меньше 4 для любого значения входного размера, которое может быть записано в физическом обратном порядке. Таким образом, мы считаем это почти линейным.

Мы рассматриваем входное дерево, как показано ниже. Мы предварительно обработаем дерево и заполним два массива: child [] и sibling [] в соответствии с приведенным ниже объяснением.

Пусть мы хотим обработать эти запросы — LCA (5,4), LCA (1,3), LCA (2,3)

Теперь, после предварительной обработки, мы выполняем LCA-обход, начиная с корня дерева (здесь — узел «1»). Но перед прогулкой по LCA мы окрашиваем все узлы в БЕЛЫЙ . В течение всей прогулки по LCA мы используем три непересекающиеся функции объединения множеств — makeSet (), findSet (), unionSet ().
Эти функции используют технику объединения по рангу и сжатию пути для улучшения времени выполнения. Во время обхода LCA наши запросы обрабатываются и выводятся (в случайном порядке). После обхода LCA всего дерева все узлы окрашиваются в ЧЕРНЫЙ .

Шаги алгоритма автономного LCA Tarjan из CLRS, раздел 21-3, стр. 584, 2-е / 3-е издание.

Примечание. Запросы не могут быть обработаны в исходном порядке. Мы можем легко изменить процесс и отсортировать их в соответствии с порядком ввода.

На рисунках ниже четко изображены все происходящие шаги. Красная стрелка показывает направление движения нашей рекурсивной функции LCA () .

Как видно из рисунков выше, запросы обрабатываются в следующем порядке: LCA (5,4), LCA (2,3), LCA (1,3), который не соответствует порядку ввода (LCA (5,4), LCA (1,3), LCA (2,3)).

Ниже приведена реализация C ++.

// Программа на C ++ для реализации алгоритма Taran Offline LCA
#include <bits/stdc++.h>

  
#define V 5       // number of nodes in input tree
#define WHITE 1   // COLOUR 'WHITE' is assigned value 1
#define BLACK 2   // COLOUR 'BLACK' is assigned value 2

  
/ * Узел двоичного дерева содержит данные, указатель на левого потомка

   и указатель на правого ребенка * /

struct Node

{

    int data;

    Node* left, *right;

};

  
/ *

 subset [i] .parent -> Содержит родителя узла -i

 subset [i] .rank -> Содержит ранг узла-'i '

 subset [i] .ancestor -> Содержит ответы на запросы LCA

 subset [i] .child -> Содержит одного из потомков узла-'i '

                    если присутствует, иначе -'0 '

 subset [i] .sibling -> Содержит правообладателя узла -i

                    если присутствует, иначе -'0 '

 subset [i] .color -> Содержит цвет узла -i

* /

struct subset

{

    int parent, rank, ancestor, child, sibling, color;

};

  
// Структура для представления запроса
// Запрос состоит из (L, R) и мы обработаем
// запрашивает офлайн а / с алгоритм Тарьяна офлайн LCA

struct Query

{

    int L, R;

};

  
/ * Вспомогательная функция, которая выделяет новый узел с

   данные даны и NULL левый и правый указатели. * /

Node* newNode(int data)

{

    Node* node = new Node;

    node->data = data;

    node->left = node->right = NULL;

    return(node);

}

  
// Утилита для создания набора

void makeSet(struct subset subsets[], int i)

{

    if (i < 1 || i > V)

        return;

  

    subsets[i].color = WHITE;

    subsets[i].parent = i;

    subsets[i].rank = 0;

  

    return;

}

  
// Полезная функция для поиска множества элементов i
// (использует технику сжатия пути)

int findSet(struct subset subsets[], int i)

{

    // найти root и сделать root родителем i (сжатие пути)

    if (subsets[i].parent != i)

        subsets[i].parent = findSet (subsets, subsets[i].parent);

  

    return subsets[i].parent;

}

  
// Функция, которая объединяет два набора x и y
// (использует объединение по рангу)

void unionSet(struct subset subsets[], int x, int y)

{

    int xroot = findSet (subsets, x);

    int yroot = findSet (subsets, y);

  

    // Прикрепить дерево меньшего ранга под корень дерева высокого ранга

    // (Объединение по рангу)

    if (subsets[xroot].rank < subsets[yroot].rank)

        subsets[xroot].parent = yroot;

    else if (subsets[xroot].rank > subsets[yroot].rank)

        subsets[yroot].parent = xroot;

  

    // Если ранги одинаковы, сделать из них корень и увеличить

    // его ранг на единицу

    else

    {

        subsets[yroot].parent = xroot;

        (subsets[xroot].rank)++;

    }

}

  
// Основная функция, которая печатает LCA. у вас есть данные root.
// m это размер q []

void lcaWalk(int u, struct Query q[], int m,

             struct subset subsets[])

{

    // Сделать наборы

    makeSet(subsets, u);

  

    // Первоначально, предком каждого узла является узел

    // сам.

    subsets[findSet(subsets, u)].ancestor = u;

  

    int child = subsets[u].child;

  

    // Цикл while не запускается более 2 раз

    // как может быть при макс. двое детей узла

    while (child != 0)

    {

        lcaWalk(child, q, m, subsets);

        unionSet (subsets, u, child);

        subsets[findSet(subsets, u)].ancestor = u;

        child = subsets[child].sibling;

    }

  

    subsets[u].color = BLACK;

  

    for (int i = 0; i < m; i++)

    {

        if (q[i].L == u)

        {

            if (subsets[q[i].R].color == BLACK)

            {

                printf("LCA(%d %d) -> %d\n",

                  q[i].L,

                  q[i].R,

                  subsets[findSet(subsets,q[i].R)].ancestor);

            }

        }

        else if (q[i].R == u)

        {

            if (subsets[q[i].L].color == BLACK)

            {

                printf("LCA(%d %d) -> %d\n",

                  q[i].L,

                  q[i].R,

                  subsets[findSet(subsets,q[i].L)].ancestor);

            }

        }

    }

  

    return;

}

  
// Это в основном обход по порядку и
// мы предварительно обрабатываем массивы-> child []
// и брат [] в "struct subset" с
// древовидная структура, использующая эту функцию.

void preprocess(Node * node, struct subset subsets[])

{

    if (node == NULL)

        return;

  

    // Повторение левого ребенка

    preprocess(node->left, subsets);

  

    if (node->left != NULL&&node->right != NULL)

    {

        / * Обратите внимание, что следующие две строки также могут быть

        подмножества [узел-> данные] .child = узел-> право-> данные;

        подмножества [node-> right-> data] .sibling =

                                         node-> лево-> данные;

  

        Это потому, что если левые и правые дети

        присутствуют node-'i ', тогда мы можем сохранить любой из них

        в подмножествах [i] .child и, соответственно, его родственнике * /

        subsets[node->data].child = node->left->data;

        subsets[node->left->data].sibling =

            node->right->data;

  

    }

    else if ((node->left != NULL && node->right == NULL)

             || (node->left == NULL && node->right != NULL))

    {

        if(node->left != NULL && node->right == NULL)

            subsets[node->data].child = node->left->data;

        else

            subsets[node->data].child = node->right->data;

    }

  

    // Возврат на правильного ребенка

    preprocess (node->right, subsets);

}

  
// Функция для инициализации до предварительной обработки и
// LCA walk

void initialise(struct subset subsets[])

{

    // Инициализация структуры с нулями

    memset(subsets, 0, (V+1) * sizeof(struct subset));

  

    // Мы окрашиваем все узлы БЕЛЫМ перед LCA Walk.

    for (int i=1; i<=V; i++)

        subsets[i].color=WHITE;

  

    return;

}

  
// Печатает LCA для заданных запросов q [0..m-1] в дереве
// с заданным корнем

void printLCAs(Node *root, Query q[], int m)

{

    // Выделим память для V подмножеств и узлов

    struct subset * subsets = new subset[V+1];

  

    // Создаем подмножества и окрашиваем их БЕЛЫМ

    initialise(subsets);

  

    // Предварительная обработка дерева

    preprocess(root, subsets);

  

    // Выполнение обхода дерева для обработки запросов LCA

    // не в сети

    lcaWalk(root->data , q, m, subsets);

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    / *

     Строим бинарное дерево: -

            1

          / /

         2 3

       / /

      4 5 * /

  

    Node *root = newNode(1);

    root->left        = newNode(2);

    root->right       = newNode(3);

    root->left->left  = newNode(4);

    root->left->right = newNode(5);

  

    // LCA Запросы на ответ

    Query q[] = {{5, 4}, {1, 3}, {2, 3}};

    int m = sizeof(q)/sizeof(q[0]);

  

    printLCAs(root, q, m);

  

    return 0;

}

Выход :

LCA(5 4) -> 2
LCA(2 3) -> 1
LCA(1 3) -> 1

Сложность времени: суперлинейная, т. Е. Чуть более медленная, чем линейная. O (N + Q) время, где O (N) время для предварительной обработки и почти O (1) время для ответа на запросы.

Вспомогательное пространство: мы используем множество массивов parent [], rank [], ancestor [], которые используются в операциях объединения несвязанных множеств, каждый из которых имеет размер, равный количеству узлов. Мы также используем массивы child [], sibling [], color [], которые полезны в этом автономном алгоритме. Следовательно, мы используем O (N).
Для удобства все эти массивы помещены в подмножество структур-структур для хранения этих массивов.

Ссылки
https://en.wikipedia.org/wiki/Tarjan%27s_off-line_lowest_common_ancestors_algorithm
CLRS, раздел 21-3, стр. 584, 2-е / 3-е издание
http://wcipeg.com/wiki/Lowest_common_ancestor#Offline

Эта статья предоставлена Rachit Belwariar . Если вам нравится GeeksforGeeks и вы хотите внести свой вклад, вы также можете написать статью и отправить ее по почте на contrib@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Алгоритм самого низкого общего предка Тарьяна

0.00 (0%) 0 votes