Определите, сбалансировано ли дерево или нет за линейное время - PullRequest
Новая
       22

Определите, сбалансировано ли дерево или нет за линейное время

0 голосов
/ 13 мая 2018

Следующая программа возвращает баланс или нет.Говорят, что дерево сбалансировано, если путь от корня к любому листу имеет одинаковую длину. 

using System;
namespace BalancedTree
{
public class MainClass 
{
    static bool isBalanced(int[][] sons) 
    {
        return isBalanced(sons, 0);
    }

    static bool isBalanced(int[][] sons, int startNode) 
    {
        int[] children = sons[startNode];

        int minHeight = int.MaxValue;
        int maxHeight = int.MinValue;

        bool allChildBalanced = true;

        if(children.Length == 0)
                return true;
        else 
        {
            foreach (int node in children) 
            {
                int h = height(sons, node);
                if(h > maxHeight)
                    maxHeight = h;

                if(h < minHeight)
                    minHeight = h;  
            }
        }
        foreach (int node in children) 
        {
            allChildBalanced = allChildBalanced && isBalanced(sons, node);

            if(!allChildBalanced)
                return false;
        }
        return Math.Abs(maxHeight - minHeight) < 2 && allChildBalanced;
    }

    static int height(int[][] sons, int startNode) 
    {
        int maxHeight = 0;

        foreach (int child in sons[startNode]) 
        {
            int thisHeight = height(sons, child);
            if(thisHeight > maxHeight) 
                maxHeight = thisHeight;
        }
        return 1 + maxHeight;
    }

    public static void Main (string[] args) 
    {
        int[][] sons = new int[6][];

        sons[0] = new int[] { 1, 2, 4 };
        sons[1] = new int[] { };
        sons[2] = new int[] { 3, 5};
        sons[3] = new int[] { };
        sons[4] = new int[] { };
        sons[5] = new int[] { };

        Console.WriteLine (isBalanced(sons));
    }

}
}

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

static int height(int[][] sons, int startNode)

делая сложность времени экспоненциальной.Я знаю, что это может быть оптимизировано в случае бинарного дерева, но я ищу способ оптимизировать мою программу в случае общего дерева, как описано выше.Одной из идей было бы, например, вызвать функцию 'height' из текущего узла вместо startNode.Мое единственное ограничение - временная сложность, которая должна быть линейной, но я могу использовать дополнительную память.

1 Ответ

0 голосов
/ 16 мая 2018

Извините, но я никогда не делал C #. Таким образом, пример кода не будет.

Однако вам не должно быть слишком сложно это сделать.

Рекурсивное определение isBalanced () никогда не даст наилучшей производительности. Причина проста: дерево все еще может быть неуравновешенным, если все поддеревья сбалансированы. Таким образом, вы не можете просто пройти через дерево один раз.

Однако ваша функция height () уже делает правильные вещи. Он посещает каждый узел дерева только один раз, чтобы найти высоту (то есть максимальную длину от корня до листа).

Все, что вам нужно сделать, это написать функцию minDistance (), которая находит минимальную длину от корня до листа. Вы можете сделать это, используя почти тот же код.

С этими функциями дерево уравновешивается тогда и только тогда, когда высота (...) == minDistance (...).

Наконец, вы можете объединить обе функции в одну, которая возвращает пару (min, max). Это не изменит сложность времени, но может немного сократить время выполнения, если возвращение пар не слишком дорого в C #

...