Рубрики

Найти LCA в двоичном дереве с помощью RMQ

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

Самый низкий общий предок (LCA) из двух узлов u и v в укорененном дереве T определяется как узел, расположенный дальше всего от корня, который имеет u и v в качестве потомков.

Например, на приведенной ниже схеме LCA узла 4 и узла 9 является узлом 2.

Может быть много подходов для решения проблемы LCA. Подходы отличаются своей временной и пространственной сложностью. Вот ссылка на пару из них (они не связаны с сокращением до RMQ).

Range Minimum Query (RMQ) используется для массивов, чтобы найти позицию элемента с минимальным значением между двумя указанными индексами. Различные подходы к решению RMQ обсуждались здесь и здесь . В этой статье обсуждается подход на основе дерева сегментов. Для дерева сегментов время предварительной обработки равно O (n), а время для минимального диапазона запроса равно O (Logn). Требуется дополнительное пространство O (n) для хранения дерева сегментов.

Сокращение LCA до RMQ:
Идея состоит в том, чтобы пройти по дереву, начиная с корня, с помощью обхода Эйлера (обход без поднятия карандаша), который представляет собой обход типа DFS с характеристиками обхода предварительного заказа.

Наблюдение : LCA узлов 4 и 9 является узлом 2, который оказывается узлом, ближайшим к корню среди всех тех, которые встречаются между посещениями 4 и 9 во время DFS T. Это наблюдение является ключом к сокращению. Давайте перефразируем: наш узел — это узел наименьшего уровня и единственный узел на этом уровне среди всех узлов, которые встречаются между последовательными вхождениями (любыми) u и v в туре Эйлера по T.

Нам нужны три массива для реализации:

  1. Узлы, посещаемые в порядке Эйлера тура Т
  2. Уровень каждого посещенного узла в Эйлеровом туре T
  3. Индекс первого вхождения узла в туре Эйлера T (поскольку любое вхождение было бы хорошо, давайте отследим первое)

Алгоритм:

  1. Проведите тур Эйлера по дереву и заполните массивы Эйлера, уровня и первого вхождения.
  2. Используя первый массив вхождений, получите индексы, соответствующие двум узлам, которые будут углами диапазона в массиве уровней, который подается в алгоритм RMQ для минимального значения.
  3. Как только алгоритм возвращает индекс минимального уровня в диапазоне, мы используем его для определения LCA с использованием массива тура Эйлера.

Ниже приведена реализация вышеуказанного алгоритма.

C ++

/ * C ++ Программа для поиска LCA для u и v путем уменьшения проблемы до RMQ * /
#include<bits/stdc++.h>
#define V 9               // number of nodes in input tree

  

int euler[2*V - 1];       // Для последовательности тура Эйлера

int level[2*V - 1];       // Уровень узлов в последовательности тура

int firstOccurrence[V+1]; // Первые появления узлов в туре

int ind;                  // Переменная для заполнения массивов Эйлера и уровня

  
// Узел двоичного дерева

struct Node

{

    int key;

    struct Node *left, *right;

};

  
// Служебная функция создает новый узел двоичного дерева с заданным ключом

Node * newNode(int k)

{

    Node *temp = new Node;

    temp->key = k;

    temp->left = temp->right = NULL;

    return temp;

}

  
// регистрируем базу 2 из x

int Log2(int x)

{

    int ans = 0 ;

    while (x>>=1) ans++;

    return ans ;

}

  
/ * Рекурсивная функция для получения минимального значения в заданном диапазоне

     индексов массива. Ниже приведены параметры для этой функции.

  

    st -> Указатель на дерево сегментов

    index -> Индекс текущего узла в дереве сегментов. Первоначально

              0 передается как root всегда с индексом 0

    ss & se -> Начальный и конечный индексы представленного сегмента

                  текущим узлом, т. е. st [index]

    qs & qe -> начальные и конечные индексы диапазона запросов * /

int RMQUtil(int index, int ss, int se, int qs, int qe, int *st)

{

    // Если сегмент этого узла является частью заданного диапазона, возвращаем

    // мин отрезка

    if (qs <= ss && qe >= se)

        return st[index];

  

    // Если сегмент этого узла находится за пределами указанного диапазона

    else if (se < qs || ss > qe)

        return -1;

  

    // Если часть этого сегмента перекрывается с заданным диапазоном

    int mid = (ss + se)/2;

  

    int q1 = RMQUtil(2*index+1, ss, mid, qs, qe, st);

    int q2 = RMQUtil(2*index+2, mid+1, se, qs, qe, st);

  

    if (q1==-1) return q2;

  

    else if (q2==-1) return q1;

  

    return (level[q1] < level[q2]) ? q1 : q2;

}

  
// Возвращаем минимум элементов в диапазоне от индекса qs (начало запроса) до
// qe (конец запроса). В основном использует RMQUtil ()

int RMQ(int *st, int n, int qs, int qe)

{

    // Проверяем ошибочные входные значения

    if (qs < 0 || qe > n-1 || qs > qe)

    {

        printf("Invalid Input");

        return -1;

    }

  

    return RMQUtil(0, 0, n-1, qs, qe, st);

}

  
// Рекурсивная функция, которая создает дерево сегментов для массива [ss..se].
// si - индекс текущего узла в сегментном дереве st

void constructSTUtil(int si, int ss, int se, int arr[], int *st)

{

    // Если в массиве есть один элемент, сохраняем его в текущем узле

    // сегментируем дерево и возвращаем

    if (ss == se)st[si] = ss;

  

    else

    {

        // Если есть более одного элемента, то повторить для левого и

        // правильные поддеревья и храним минимум двух значений в этом узле

        int mid = (ss + se)/2;

        constructSTUtil(si*2+1, ss, mid, arr, st);

        constructSTUtil(si*2+2, mid+1, se, arr, st);

  

        if (arr[st[2*si+1]] < arr[st[2*si+2]])

            st[si] = st[2*si+1];

        else

            st[si] = st[2*si+2];

    }

}

  
/ * Функция для построения дерева сегментов из заданного массива. Эта функция

   выделяет память для дерева сегментов и вызывает constructSTUtil () для

   заполнить выделенную память * /

int *constructST(int arr[], int n)

{

    // Выделить память для дерева сегментов

  

    // Высота сегмента дерева

    int x = Log2(n)+1;

  

    // Максимальный размер дерева сегментов

    int max_size = 2*(1<<x) - 1;  // 2 * pow (2, x) -1

  

    int *st = new int[max_size];

  

    // Заполняем выделенную память st

    constructSTUtil(0, 0, n-1, arr, st);

  

    // Возвращаем построенное дерево сегментов

    return st;

}

  
// Рекурсивная версия тура Эйлера T

void eulerTour(Node *root, int l)

{

    / * если переданный узел существует * /

    if (root)

    {

        euler[ind] = root->key; // вставить в массив euler

        level[ind] = l;         // вставляем l в массив уровня

        ind++;                  // инкрементный индекс

  

        / * если не посещено, отметьте первое вхождение * /

        if (firstOccurrence[root->key] == -1)

            firstOccurrence[root->key] = ind-1;

  

        / * обход левого поддерева, если существует, и замечание эйлера

           и уровень массивов для родителя по возвращении * /

        if (root->left)

        {

            eulerTour(root->left, l+1);

            euler[ind]=root->key;

            level[ind] = l;

            ind++;

        }

  

        / * обходить правильное поддерево, если оно существует, и замечание Эйлера

           и уровень массивов для родителя по возвращении * /

        if (root->right)

        {

            eulerTour(root->right, l+1);

            euler[ind]=root->key;

            level[ind] = l;

            ind++;

        }

    }

}

  
// Возвращает LCA узлов n1, n2 (при условии, что они
// присутствует в дереве)

int findLCA(Node *root, int u, int v)

{

    / * Пометить все узлы как непосещенные. Обратите внимание, что размер

        firstOccurrence равен 1 как значения узла, которые варьируются от

        От 1 до 9 используются в качестве индексов * /

    memset(firstOccurrence, -1, sizeof(int)*(V+1));

  

    / * Чтобы начать заполнение массивов Эйлера и уровня с индекса 0 * /

    ind = 0;

  

    / * Запустить тур Эйлера с корневым узлом на уровне 0 * /

    eulerTour(root, 0);

  

    / * построить дерево сегментов на массиве уровней * /

    int *st = constructST(level, 2*V-1);

  

    / * Если v перед тобой в туре Эйлера. Чтобы RMQ работал, сначала

       параметр 'u' должен быть меньше второго 'v' * /

    if (firstOccurrence[u]>firstOccurrence[v])

       std::swap(u, v);

  

    // Начальный и конечный индексы диапазона запроса

    int qs = firstOccurrence[u];

    int qe = firstOccurrence[v];

  

    // запрос индекса LCA в туре

    int index = RMQ(st, 2*V-1, qs, qe);

  

    / * возврат узла LCA * /

    return euler[index];

}

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

int main()

{

    // Давайте создадим двоичное дерево, как показано на диаграмме.

    Node * root = newNode(1);

    root->left = newNode(2);

    root->right = newNode(3);

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

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

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

    root->right->right = newNode(7);

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

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

  

    int u = 4, v = 9;

    printf("The LCA of node %d and node %d is node %d.\n"

            u, v, findLCA(root, u, v));

    return 0;

}

Джава

// Java-программа для поиска LCA для u и v путем уменьшения проблемы до RMQ

   

import java.util.*;

   
// Узел двоичного дерева

class Node 

{

    Node left, right;

    int data;

   

    Node(int item) 

    {

        data = item;

        left = right = null;

    }

}

   

class St_class 

{

    int st;

    int stt[] = new int[10000];

}

   

class BinaryTree 

{

    Node root;

    int v = 9; // v - это наибольшее значение узла в нашем дереве

    int euler[] = new int[2 * v - 1]; // для последовательности тура Эйлера

    int level[] = new int[2 * v - 1]; // уровень узлов в последовательности тура

    int f_occur[] = new int[2 * v - 1]; // хранить 1-е вхождение узлов

    int fill; // переменная для заполнения массивов эйлеров и уровней

    St_class sc = new St_class();

   

    // регистрируем базу 2 из x

    int Log2(int x) 

    {

        int ans = 0;

        int y = x >>= 1;

        while (y-- != 0)

            ans++;

        return ans;

    }

   

    int swap(int a, int b) 

    {

        return a;

    }

   

    / * Рекурсивная функция для получения минимального значения в заданном диапазоне

     индексов массива. Ниже приведены параметры для этой функции.

    

     st -> Указатель на дерево сегментов

     index -> Индекс текущего узла в дереве сегментов. Первоначально

     0 передается как root всегда с индексом 0

     ss & se -> Начальный и конечный индексы представленного сегмента

     текущим узлом, т. е. st [index]

     qs & qe -> начальные и конечные индексы диапазона запросов * /

    int RMQUtil(int index, int ss, int se, int qs, int qe, St_class st) 

    {

        // Если сегмент этого узла является частью заданного диапазона, возвращаем

        // мин отрезка

        if (qs <= ss && qe >= se)

            return st.stt[index];

   

        // Если сегмент этого узла находится за пределами указанного диапазона

        else if (se < qs || ss > qe)

            return -1;

   

        // Если часть этого сегмента перекрывается с заданным диапазоном

        int mid = (ss + se) / 2;

   

        int q1 = RMQUtil(2 * index + 1, ss, mid, qs, qe, st);

        int q2 = RMQUtil(2 * index + 2, mid + 1, se, qs, qe, st);

   

        if (q1 == -1)

            return q2;

        else if (q2 == -1)

            return q1;

   

        return (level[q1] < level[q2]) ? q1 : q2;

    }

   

    // Возвращаем минимум элементов в диапазоне от индекса qs (начало запроса) до

    // qe (конец запроса). В основном использует RMQUtil ()

    int RMQ(St_class st, int n, int qs, int qe) 

    {

        // Проверяем ошибочные входные значения

        if (qs < 0 || qe > n - 1 || qs > qe) 

        {

            System.out.println("Invalid input");

            return -1;

        }

   

        return RMQUtil(0, 0, n - 1, qs, qe, st);

    }

   

    // Рекурсивная функция, которая создает дерево сегментов для массива [ss..se].

    // si - индекс текущего узла в сегментном дереве st

    void constructSTUtil(int si, int ss, int se, int arr[], St_class st) 

    {

        // Если в массиве есть один элемент, сохраняем его в текущем узле

        // сегментируем дерево и возвращаем

        if (ss == se)

            st.stt[si] = ss;

        else 

        {

            // Если есть более одного элемента, то повторить для левого и

            // правильные поддеревья и храним минимум двух значений в этом узле

            int mid = (ss + se) / 2;

            constructSTUtil(si * 2 + 1, ss, mid, arr, st);

            constructSTUtil(si * 2 + 2, mid + 1, se, arr, st);

   

            if (arr[st.stt[2 * si + 1]] < arr[st.stt[2 * si + 2]])

                st.stt[si] = st.stt[2 * si + 1];

            else

                st.stt[si] = st.stt[2 * si + 2];

        }

    }

   

    / * Функция для построения дерева сегментов из заданного массива. Эта функция

     выделяет память для дерева сегментов и вызывает constructSTUtil () для

     заполнить выделенную память * /

    int constructST(int arr[], int n) 

    {

        // Выделить память для дерева сегментов

        // Высота сегмента дерева

        int x = Log2(n) + 1;

           

        // Максимальный размер дерева сегментов

        int max_size = 2 * (1 << x) - 1// 2 * pow (2, x) -1

   

        sc.stt = new int[max_size];

   

        // Заполняем выделенную память st

        constructSTUtil(0, 0, n - 1, arr, sc);

           

        // Возвращаем построенное дерево сегментов

        return sc.st;

    }

   

    // Рекурсивная версия тура Эйлера T

    void eulerTour(Node node, int l) 

    {

        / * если переданный узел существует * /

        if (node != null

        {

            euler[fill] = node.data; // вставить в массив euler

            level[fill] = l;         // вставляем l в массив уровня

            fill++;                  // инкрементный индекс

   

            / * если не посещено, отметьте первое вхождение * /

            if (f_occur[node.data] == -1)

                f_occur[node.data] = fill - 1;

   

            / * обход левого поддерева, если существует, и замечание эйлера

               и уровень массивов для родителя по возвращении * /

            if (node.left != null

            {

                eulerTour(node.left, l + 1);

                euler[fill] = node.data;

                level[fill] = l;

                fill++;

            }

   

            / * обходить правильное поддерево, если оно существует, и замечание Эйлера

               и уровень массивов для родителя по возвращении * /

            if (node.right != null

            {

                eulerTour(node.right, l + 1);

                euler[fill] = node.data;

                level[fill] = l;

                fill++;

            }

        }

    }

   

    // возвращает LCA узла n1 и n2, предполагая, что они присутствуют в дереве

    int findLCA(Node node, int u, int v) 

    {

        / * Пометить все узлы как непосещенные. Обратите внимание, что размер

           firstOccurrence равен 1 как значения узла, которые варьируются от

           От 1 до 9 используются в качестве индексов * /

        Arrays.fill(f_occur, -1);

   

        / * Чтобы начать заполнение массивов Эйлера и уровня с индекса 0 * /

        fill = 0;

   

        / * Запустить тур Эйлера с корневым узлом на уровне 0 * /

        eulerTour(root, 0);

          

        / * построить дерево сегментов на массиве уровней * /

        sc.st = constructST(level, 2 * v - 1);

           

        / * Если v перед тобой в туре Эйлера. Чтобы RMQ работал, сначала

         параметр 'u' должен быть меньше второго 'v' * /

        if (f_occur[u] > f_occur[v])

            u = swap(u, u = v);

   

        // Начальный и конечный индексы диапазона запроса

        int qs = f_occur[u];

        int qe = f_occur[v];

   

        // запрос индекса LCA в туре

        int index = RMQ(sc, 2 * v - 1, qs, qe);

   

        / * возврат узла LCA * /

        return euler[index];

   

    }

   

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

    public static void main(String args[]) 

    {

        BinaryTree tree = new BinaryTree();

   

        // Давайте создадим двоичное дерево, как показано на диаграмме.

        tree.root = new Node(1);

        tree.root.left = new Node(2);

        tree.root.right = new Node(3);

        tree.root.left.left = new Node(4);

        tree.root.left.right = new Node(5);

        tree.root.right.left = new Node(6);

        tree.root.right.right = new Node(7);

        tree.root.left.right.left = new Node(8);

        tree.root.left.right.right = new Node(9);

   

        int u = 4, v = 9;

        System.out.println("The LCA of node " + u + " and " + v + " is "

                + tree.findLCA(tree.root, u, v));

    }

   
}

  
// Этот код предоставлен Mayank Jaiswal

C #

// C # программа для поиска LCA и
// v путем уменьшения проблемы до RMQ

using System;

  
// Узел двоичного дерева

class Node 

{

    public Node left, right;

    public int data;

  

    public Node(int item) 

    {

        data = item;

        left = right = null;

    }

}

  

class St_class 

{

    public int st;

    public int []stt = new int[10000];

}

  

public class BinaryTree 

{

    Node root;

    static int v = 9; // v - это наибольшее значение узла в нашем дереве

    int []euler = new int[2 * v - 1]; // для последовательности тура Эйлера

    int []level = new int[2 * v - 1]; // уровень узлов в последовательности тура

    int []f_occur = new int[2 * v - 1]; // хранить 1-е вхождение узлов

    int fill; // переменная для заполнения массивов эйлеров и уровней

    St_class sc = new St_class();

  

    // регистрируем базу 2 из x

    int Log2(int x) 

    {

        int ans = 0;

        int y = x >>= 1;

        while (y-- != 0)

            ans++;

        return ans;

    }

  

    int swap(int a, int b) 

    {

        return a;

    }

  

    / * Рекурсивная функция для получения

    минимальное значение в заданном диапазоне

    индексов массива. Следующее

    параметры для этой функции

      

    st -> Указатель на дерево сегментов

    index -> Index текущего узла

    в сегментном дереве. Первоначально

    0 передается как root всегда с индексом 0

    ss & se -> Начало и конец

    индексы представленного сегмента

    текущим узлом, т. е. st [index]

    qs & qe -> Начало и конец

    индексы диапазона запросов * /

    int RMQUtil(int index, int ss, int se, 

                    int qs, int qe, St_class st) 

    {

        // Если сегмент этого узла является частью

        // заданного диапазона, затем возврат

        // мин отрезка

        if (qs <= ss && qe >= se)

            return st.stt[index];

  

        // Если сегмент этого узла

        // вне заданного диапазона

        else if (se < qs || ss > qe)

            return -1;

  

        // Если часть этого сегмента

        // перекрывается с заданным диапазоном

        int mid = (ss + se) / 2;

  

        int q1 = RMQUtil(2 * index + 1, 

                        ss, mid, qs, qe, st);

        int q2 = RMQUtil(2 * index + 2,

                        mid + 1, se, qs, qe, st);

  

        if (q1 == -1)

            return q2;

        else if (q2 == -1)

            return q1;

  

        return (level[q1] < level[q2]) ? q1 : q2;

    }

  

    // Возвращаем минимум элементов в

    // диапазон от индекса qs (начало запроса) до

    // qe (конец запроса). В основном использует RMQUtil ()

    int RMQ(St_class st, int n, int qs, int qe) 

    {

        // Проверяем ошибочные входные значения

        if (qs < 0 || qe > n - 1 || qs > qe) 

        {

            Console.WriteLine("Invalid input");

            return -1;

        }

  

        return RMQUtil(0, 0, n - 1, qs, qe, st);

    }

  

    // Рекурсивная функция, которая создает

    // Сегментное дерево для массива [ss..se].

    // si - индекс текущего узла в сегментном дереве st

    void constructSTUtil(int si, int ss, int se,

                        int []arr, St_class st) 

    {

        // Если в массиве есть один элемент,

        // сохранить его в текущем узле

        // сегментируем дерево и возвращаем

        if (ss == se)

            st.stt[si] = ss;

        else

        {

            // Если есть более одного элемента,

            // затем повторяем для левого и правого поддеревьев

            // и сохранить минимум двух значений в этом узле

            int mid = (ss + se) / 2;

            constructSTUtil(si * 2 + 1, ss, mid, arr, st);

            constructSTUtil(si * 2 + 2, mid + 1, se, arr, st);

  

            if (arr[st.stt[2 * si + 1]] < arr[st.stt[2 * si + 2]])

                st.stt[si] = st.stt[2 * si + 1];

            else

                st.stt[si] = st.stt[2 * si + 2];

        }

    }

  

    / * Функция для построения дерева сегментов

    из данного массива. Эта функция

    выделяет память для дерева сегментов

    и вызывает constructSTUtil () для

    заполнить выделенную память * /

    int constructST(int []arr, int n) 

    {

        // Выделить память для дерева сегментов

        // Высота сегмента дерева

        int x = Log2(n) + 1;

          

        // Максимальный размер дерева сегментов

        int max_size = 2 * (1 << x) - 1; // 2 * pow (2, x) -1

  

        sc.stt = new int[max_size];

  

        // Заполняем выделенную память st

        constructSTUtil(0, 0, n - 1, arr, sc);

          

        // Возвращаем построенное дерево сегментов

        return sc.st;

    }

  

    // Рекурсивная версия тура Эйлера T

    void eulerTour(Node node, int l) 

    {

        / * если переданный узел существует * /

        if (node != null

        {

            euler[fill] = node.data; // вставить в массив euler

            level[fill] = l;         // вставляем l в массив уровня

            fill++;                 // инкрементный индекс

  

            / * если не посещено, отметьте первое вхождение * /

            if (f_occur[node.data] == -1)

                f_occur[node.data] = fill - 1;

  

            / * обходить левое поддерево, если существует,

                и замечание эйлера и уровня

                массивы для родителя по возвращении * /

            if (node.left != null

            {

                eulerTour(node.left, l + 1);

                euler[fill] = node.data;

                level[fill] = l;

                fill++;

            }

  

            / * обходить правильное поддерево, если оно существует, и замечание Эйлера

            и уровень массивов для родителя по возвращении * /

            if (node.right != null

            {

                eulerTour(node.right, l + 1);

                euler[fill] = node.data;

                level[fill] = l;

                fill++;

            }

        }

    }

  

    // возвращает LCA узла n1 и n2

    // при условии, что они присутствуют в дереве

    int findLCA(Node node, int u, int v) 

    {

        / * Пометить все узлы как непосещенные. Заметка

         что размер первого появления

         1 как значения узла, которые

         варьируются от 1 до 9, используются в качестве индексов * /

        //Arrays.fill(f_occur, -1);

        for(int i = 0; i < f_occur.Length; i++)

            f_occur[i] = -1;

  

  

        / * Чтобы начать заполнение Эйлера и

        массив уровней из индекса 0 * /

        fill = 0;

  

        / * Начать тур Эйлера с

        корневой узел на уровне 0 * /

        eulerTour(root, 0);

          

        / * построить дерево сегментов на массиве уровней * /

        sc.st = constructST(level, 2 * v - 1);

          

        / * Если v перед тобой в туре Эйлера.

        Чтобы RMQ работал, первый параметр

        'u' должно быть меньше чем

         второй 'v' * /

        if (f_occur[u] > f_occur[v])

            u = swap(u, u = v);

  

        // Начальный и конечный индексы диапазона запроса

        int qs = f_occur[u];

        int qe = f_occur[v];

  

        // запрос индекса LCA в туре

        int index = RMQ(sc, 2 * v - 1, qs, qe);

  

        / * возврат узла LCA * /

        return euler[index];

  

    }

  

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

    public static void Main(String []args) 

    {

        BinaryTree tree = new BinaryTree();

  

        // Давайте создадим двоичное дерево

        // как показано на диаграмме.

        tree.root = new Node(1);

        tree.root.left = new Node(2);

        tree.root.right = new Node(3);

        tree.root.left.left = new Node(4);

        tree.root.left.right = new Node(5);

        tree.root.right.left = new Node(6);

        tree.root.right.right = new Node(7);

        tree.root.left.right.left = new Node(8);

        tree.root.left.right.right = new Node(9);

  

        int u = 4, v = 9;

        Console.WriteLine("The LCA of node " + u + " and " + v + " is "

                + tree.findLCA(tree.root, u, v));

    }

}

  
// Этот код предоставлен 29AjayKumar


Выход:

The LCA of node 4 and node 9 is node 2.

Замечания:

  1. Мы предполагаем, что запрашиваемые узлы присутствуют в дереве.
  2. Мы также предположили, что если в дереве есть V узлов, то ключи (или данные) этих узлов находятся в диапазоне от 1 до V.

Сложность времени:

  1. Тур Эйлера: число узлов равно V. Для дерева E = V-1. Эйлер тур (DFS) будет принимать O (V + E), который является O (2 * V), который может быть записан как O (V).
  2. Построение дерева сегментов: O (n), где n = V + E = 2 * V — 1.
  3. Диапазон Минимальный запрос: O (log (n))

В целом, этот метод занимает O (n) время для предварительной обработки, но занимает O (Log n) время для запроса. Поэтому это может быть полезно, когда у нас есть одно дерево, для которого мы хотим выполнить большое количество запросов LCA (обратите внимание, что LCA полезен для нахождения кратчайшего пути между двумя узлами двоичного дерева)

Вспомогательное пространство:

  1. Массив Эйлера: O (n), где n = 2 * V — 1
  2. Массив уровней узлов: O (n)
  3. Массив первых вхождений: O (V)
  4. Сегментное дерево: O (n)

Всего: O (n)

Другое наблюдение состоит в том, что соседние элементы в массиве уровней отличаются на 1. Это можно использовать для преобразования проблемы RMQ в проблему LCA.

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

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

Найти LCA в двоичном дереве с помощью RMQ

0.00 (0%) 0 votes