ارتفاع یک درخت عمومی از آرایه والدین


سطح دشواری متوسط
اغلب در گوگل PayU سامسونگ آبپاش حال بارگذاری
عرض اول جستجو برنامه نویسی پویا گراف صف درخت

بیان مسأله

مسئله "ارتفاع یک درخت عمومی از آرایه والد" بیان می کند که به شما یک درخت با n راس به عنوان پارامتر آرایه داده می شود [0… n-1]. در اینجا هر شاخص i در پاراگراف [] یک گره را نشان می دهد و مقدار i نمایانگر اصلی آن گره است. برای گره ریشه بدون والد ، مقدار آن در آرایه par [] برابر با 1 خواهد بود. اکنون باید ارتفاع درخت را با توجه به پیوندهای والدین پیدا کنیم.

آرایه 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. برنامه نویسی پویا

جستجو برای اولین بار

رویکردی برای یافتن ارتفاع یک درخت عمومی از آرایه والدین

برای حل این مشکل ما یک درخت (ساختار داده نمودار) را با استفاده از آرایه [] داده شده خواهیم ساخت. اکنون 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

برنامه جاوا برای یافتن ارتفاع یک درخت عمومی از آرایه والدین

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

تحلیل پیچیدگی

پیچیدگی زمان

T (n) = O (V + E) = O (2V-1) = O (V). در اینجا ما یک جستجو برای اولین بار انجام داده ایم که تمام درخت را پوشش می دهد بنابراین در مجموع رئوس V را پوشش می دهد. بنابراین به ما یک پیچیدگی زمانی خطی می بخشد.

پیچیدگی فضا

A (n) = O (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

برنامه جاوا برای یافتن ارتفاع یک درخت عمومی از آرایه والدین

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 تعداد گره های درخت را نشان می دهد.

پیچیدگی فضا

بر)، ما باید ارتفاع هر یک از گره ها را ذخیره کنیم. از آنجا که توسط فرزندان گره فعلی استفاده خواهد شد. بنابراین الگوریتم دارای پیچیدگی فضای خطی است.