Высота общего дерева из родительского массива


Сложный уровень средний
Часто спрашивают в Google PayU Компания Qualcomm Sprinklr Uber
Поиск в ширину Динамическое программирование График Очередь дерево

Постановка задачи

Задача «Высота общего дерева из родительского массива» состоит в том, что вам дано дерево с n вершинами в виде массива par [0… n-1]. Здесь каждый индекс i в par [] представляет узел, а значение в i представляет непосредственного родителя этого узла. Для корневого узла без родителя его значение в массиве par [] будет -1. Теперь нам нужно найти высоту дерева с учетом родительских связей.

Рассмотрим массив par [], приведенный ниже:

Высота общего дерева из родительского массива

Дерево, построенное с использованием этих связей массивов par [], приведено ниже:

Высота общего дерева из родительского массива

Примечание: высота дерева не может превышать 100 единиц.

Высота общего дерева из родительского массива

Пример

[-1 0 0 1 2 2 4]
3

Пояснение: количество ребер на самом длинном пути равно 3.

[-1 0 0 1 1 2 2 3 3 4 7]
4

Пояснение: количество ребер на самом длинном пути (0-> 1-> 3-> 7-> 10) равно 4.

Типы решений

  1. Поиск в ширину
  2. Динамическое программирование

Поиск в ширину

Подход к нахождению высоты общего дерева из родительского массива

Чтобы решить эту проблему, мы построим дерево (структуру данных графа), используя заданный массив par []. Теперь мы выполняем BFS, начиная с корневого узла, и находим самый длинный путь (или расстояние до самой дальней вершины) вдоль пути дерева. Итак, само значение этого расстояния называется высотой дерева. BFS - это не что иное, как алгоритм обхода графа, который проходит через весь граф. Поиск в ширину работает так, что узлы, ближайшие к текущему узлу, проходят раньше, чем узлы, имеющие большее расстояние. Таким образом, мы можем найти расстояние каждого узла от корня. А узел с наибольшим расстоянием называется узлом на высоте дерева.

Алгоритм

1. Construct the directed graph using the par[] array values.
2. The edges in graph should be directed from node par[i] to i. i.e, par[i] --> i.
3. The root node has no parent and hence, no incoming edge.
4. Now starting from the root node, perform BFS, and calculate distance of each of the nodes in the tree from the root node itself.
5. The largest distance value is the height of the tree.

 

Алгоритм изображен ниже:

Высота общего дерева из родительского массива

Высота общего дерева из родительского массива

Высота общего дерева с использованием BFS

Код:

Программа на C ++ для определения высоты общего дерева из родительского массива

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

// perform BFS to calculate Height
int BFS(vector <int> par)
{
    int root;
    int n = par.size();
    vector <int> graph[n];
    
    // construct graph from given parent array
    for(int i=0;i<n;i++)
    {
        if(par[i] != -1)
        graph[par[i]].push_back(i);    
        
        else
        root = i;
    }
    
    // to store distance of each node from the root
    vector <int> distance(n,0);
    
    // create BFS queue
    queue <int> q;
    // insert the root node
    q.push(root);
    
    // Begin BFS & calculate distance of each node from root
    while(!q.empty())
    {
        int front = q.front();
        q.pop();
        
        for(auto i : graph[front])
        {
            distance[i] = distance[front] + 1;
            q.push(i);
        }
    }
    
    // return height of the Tree
    return *max_element(distance.begin(),distance.end());
}

int main()
{
    // define parent array
    vector <int> par = {-1,0,0,1,2,2,4};
    cout<<"Height of the Tree : "<<BFS(par)<<endl;
    return 0;
}
Height of the Tree : 3

Программа на Java для определения высоты общего дерева из родительского массива

import java.util.*;
import java.io.*;

class TutorialCup 
{
    // perform BFS to calculate Height
    static int BFS(int [] par)
    {
        int root = 0;
        int n = par.length;
        ArrayList <ArrayList <Integer>> graph = new ArrayList<ArrayList<Integer>>();
        
        // construct graph from given parent array
        for(int i=0;i<n;i++)
        {
            graph.add(new ArrayList<Integer>());
            
            if(par[i] != -1)
            graph.get(par[i]).add(i);    
            
            else
            root = i;
        }
        
        // to store distance of each node from the root
        int distance[] = new int[n];
        
        // create BFS queue
        Queue <Integer> q = new LinkedList<>();
        // insert the root node
        q.add(root);
        
        // Begin BFS & calculate distance of each node from root
        while(!q.isEmpty())
        {
            int front = q.poll();
            
            Iterator itr = graph.get(front).iterator();
            
            while(itr.hasNext())
            {
                int i = (Integer)itr.next();
                distance[i] = distance[front] + 1;
                q.add(i);
            }
        }
        
        // return height of the Tree
        int height = 0;
        for(int i=0;i<distance.length;i++)
        height = Math.max(height,distance[i]);
        
        return height;
    }
    
    public static void main (String[] args)
    {
        // define parent array
        int [] par = {-1,0,0,1,2,2,4};
        System.out.println("Height of the Tree : "+BFS(par));
    }
}
Height of the Tree : 3

Анализ сложности

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

Т (п) = O (V + E) = O (2V-1) = О (В). Здесь мы выполнили поиск в ширину, который покроет все дерево, таким образом, покрывая в общей сложности V вершин. Таким образом, мы получаем линейную временную сложность.

Космическая сложность

А (п) = О (В), для очереди BFS и созданного графа-дерева. В худшем случае мы можем получить звездообразное дерево, в котором все узлы имеют одного и того же родителя, кроме корня. Таким образом, в этом случае будет достигнута наихудшая пространственная сложность, которая составит O (V).

где,

V = количество вершин в дереве.

E = количество ребер в дереве = V-1

Динамическое программирование

Подход к нахождению высоты общего дерева из родительского массива

В дерево из N узлов, посещают каждый узел в порядке от 0 до N-1. Для каждого узла рассчитайте его высоту с помощью функции findHeight () (высота узла - это количество ребер между этим конкретным узлом и корневым узлом).

Перед вычислением высоты узла необходимо рекурсивно рассчитать высоту всех его узлов-предков. В findDistance () выполняет эту задачу рекурсивно. После вычисления высоты узла в дереве. Он должен быть помечен как посещенный (посетил [] для этого используется массив).

Алгоритм

1. Define two functions findDistance( ) & findHeight( ) for calculating height of each node in the tree.
2. Visit each node iteratively in order from 0 to V-1 (where V = number of vertices).
3. For a particular node, calculate heights of all it's ancestors recursively before the calculating height of the node itself, this is done using findDistance() recursive function.
4. every ancestor node visited should be marked as visited (using visited[ ] array).
5. Return the maximum value in the height[ ].
6. steps 1 to 5 are encapsulated in findHeight( ) function.

 

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

 

Код:

Программа на C ++ для определения высоты общего дерева из родительского массива

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

// function to find height of node - i from tree root
int findDistance(vector <int> par, int i, vector <bool> &visited, vector <int> &height)
{
    // if root node is encountered
    if(par[i] == -1)
    {
        visited[i] = true;
        return 0;
    }
    
    // if node is already visited
    // return it's calculated height
    if(visited[i])
    return height[i];
    
    // if a node is not visited
    // below steps are executed
    
    // mark node visited
    visited[i] = true;
    // calculate height of node
    height[i] = 1+findDistance(par,par[i],visited,height);
    // return height after calculation    
    return height[i];
}

// function to calculate maximum height
int findHeight(vector <int> par)
{
    int maxHeight = 0;
    
    int n = par.size();
    
    // visited array is used to check if a node is visited
    vector <bool> visited(n,false);
    // calculate height of each node in the tree
    vector <int> height(n,0);
    
    // traverse each node of the tree
    // evaluate height of each node & store maximum of all heights 
    for(int i=0;i<n;i++)
    {
        height[i] = findDistance(par,i,visited,height);
        maxHeight = max(maxHeight,height[i]);
    }
    
    // return maximum of all heights
    return maxHeight;
}

int main()
{
    // define parent array
    vector <int> par = {-1,0,0,1,2,2,4};
    cout<<"Height of the Tree : "<<findHeight(par)<<endl;
    return 0;
}
Height of the Tree : 3

Программа на Java для определения высоты общего дерева из родительского массива

import java.util.*;
import java.io.*;

class TutorialCup 
{
    // function to find height of node - i from tree root
    static int findDistance(int [] par, int i, boolean [] visited, int [] height)
    {
        // if root node is encountered
        if(par[i] == -1)
        {
            visited[i] = true;
            return 0;
        }
        
        // if node is already visited
        // return it's calculated height
        if(visited[i] == true)
        return height[i];
        
        // if a node is not visited
        // below steps are executed
        
        // mark node visited
        visited[i] = true;
        // calculate height of node
        height[i] = 1+findDistance(par,par[i],visited,height);
        // return height after calculation    
        return height[i];
    }

    // function to calculate maximum height
    static int findHeight(int [] par)
    {
        int maxHeight = 0;
        
        int n = par.length;
        
        // visited array is used to check if a node is visited
        boolean [] visited = new boolean[n];
        // calculate height of each node in the tree
        int [] height = new int[n];
        
        // traverse each node of the tree
        // evaluate height of each node & store maximum of all heights 
        for(int i=0;i<n;i++)
        {
            height[i] = findDistance(par,i,visited,height);
            maxHeight = Math.max(maxHeight,height[i]);
        }
        
        // return maximum of all heights
        return maxHeight;
    }
    
    public static void main (String[] args)
    {
        // define parent array
        int [] par = {-1,0,0,1,2,2,4};
        System.out.println("Height of the Tree : "+findHeight(par));
    }
}
Height of the Tree : 3

Анализ сложности

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

НА),  потому что здесь мы также будем обходить все узлы дерева. Поскольку мы будем обходить все узлы дерева. Благодаря этому мы достигли линейной временной сложности O (N), где N обозначало количество узлов в дереве.

Космическая сложность

НА), нам нужно сохранить высоту для каждого из узлов. Поскольку это будет использоваться дочерними элементами текущего узла. Таким образом, алгоритм имеет линейную пространственную сложность.