Форум на Исходниках.RU https://forum.sources.ru Форум на Исходниках.RU Форум на Исходниках.RU https://forum.sources.ru/index.php?showtopic=420994&view=findpost&p=3842716 Thu, 10 Dec 2020 06:22:09 +0000 Поиск наидлиннейшего пути в бинарном дереве поиска https://forum.sources.ru/index.php?showtopic=420994&view=findpost&p=3842716
Просто находил ДЛЯ КАЖДОГО УЗЛА ДДП высоты левого и правого поддерева, суммировал их и проверял с максимальной. На рис., как я понимаю, длиннейший путь = 6, ну, прожка так и выдает.

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

    int maxP = 0;
    int GMP(const TREE* root)
    {
        if(root != NULL)
        {
            LPK(root->left);
            LPK(root->right);
            int currentP = GH(root->left) + GH(root->right) - 1; // вот эта "-1" связана с логикой функции G(et)H(eight) + потомки не должны быть листьями оба одновременно, поэтому одного из потомка "поднимаем" на 1 уровень вверх, отбирая у пути одну единицу движения
            if(currentP > maxP)
                maxP = currentP;
            return maxP;
        }
        else
            return 0;
    }


__________________________________.png (, : 1623)

зы: когда ДДП-ЛОС, то в пути теряется 1, печалька) Хотя тут может проблема не только в этом...]]> FasterHarder Алгоритмы https://forum.sources.ru/index.php?showtopic=420994&view=findpost&p=3842706 Wed, 09 Dec 2020 16:37:05 +0000 Поиск наидлиннейшего пути в бинарном дереве поиска https://forum.sources.ru/index.php?showtopic=420994&view=findpost&p=3842706 Цитата FasterHarder @
би-родитель, это хто?) Вершина, имеющая левого и правого потомка?

Он
Цитата FasterHarder @
ты говоришь неоднократно "двигаться вверх", но структура дерева не имеет линка parent, а только left/right

Дерево - всего лишь исходные данные, к которым никто не мешает прилепить что-то дополнительное. Кстати, отсутствие линка на родителя - обычай, но не догма.
Цитата FasterHarder @
что ты будешь делать, когда ДДП является ЛОСом? Там всего лишь 1 узел является листом...

Обработаю этот единственный особый случай отдельно.
Цитата AVA12 @
Нет необходимости строить все возможные пути, а потом отбрасывать лишние. Достаточно знать высоты всех поддеревьев и "корень", через который проходит длиннейший путь.

Всё равно предобработка...]]> Akina Алгоритмы https://forum.sources.ru/index.php?showtopic=420994&view=findpost&p=3842704 Wed, 09 Dec 2020 15:54:59 +0000 Поиск наидлиннейшего пути в бинарном дереве поиска https://forum.sources.ru/index.php?showtopic=420994&view=findpost&p=3842704 Цитата AVA12 @
Для поиска "корня" нужно обойти дерево в глубину.

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

а также готовую рекурсивную функцию на шарпе, но там такая функция, что переписать на Си, например, пока непонятно как)]]> FasterHarder Алгоритмы https://forum.sources.ru/index.php?showtopic=420994&view=findpost&p=3842703 Wed, 09 Dec 2020 15:32:13 +0000 Поиск наидлиннейшего пути в бинарном дереве поиска https://forum.sources.ru/index.php?showtopic=420994&view=findpost&p=3842703 Akina:

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

Для поиска "корня" нужно обойти дерево в глубину. Для каждого узла/листа храним высоту его поддерева H (изначально 0). Отдельно храним длину лучшего найденного пути L (изначально 0) и ссылку на "корень" этого пути P. Каждый раз, поднимаясь из потомка к родителю, пишем в H родителя MAX(H_родителя, H_потомка + 1). Когда посещены оба потомка, длина максимального пути, для которого узел является "корнем", равна сумме H дочерних узлов. Если эта длина больше L, то в L пишем эту длину, а в P пишем ссылку на узел.]]> AVA12 Алгоритмы https://forum.sources.ru/index.php?showtopic=420994&view=findpost&p=3842702 Wed, 09 Dec 2020 12:32:21 +0000 Поиск наидлиннейшего пути в бинарном дереве поиска https://forum.sources.ru/index.php?showtopic=420994&view=findpost&p=3842702 Akina, спс за достаточно полное описание
би-родитель, это хто?) Вершина, имеющая левого и правого потомка?
2. Вот ты говоришь неоднократно "двигаться вверх", но структура дерева не имеет линка parent, а только left/right. Это ведь важно оказывается вроде

Добавлено
Цитата Akina @
Изначально очевидно, что одним концом такого пути будет лист, а другим - узел, потомки которого листья (или единственный потомок - лист). так что для унификации мы просто ищем максимальный путь между двумя листьями, а потом отбрасываем единичку (любой из конечных листов заменяем на его родителя).

это красивый подход, но, что ты будешь делать, когда ДДП является ЛОСом? Там всего лишь 1 узел является листом...]]> FasterHarder Алгоритмы https://forum.sources.ru/index.php?showtopic=420994&view=findpost&p=3842700 Wed, 09 Dec 2020 12:18:53 +0000 Поиск наидлиннейшего пути в бинарном дереве поиска https://forum.sources.ru/index.php?showtopic=420994&view=findpost&p=3842700 Цитата FasterHarder @
Нужно найти самый длинный путь (максимальной длины) между двумя любыми вершинами дерева с разным числом потомков.

Очевидно, речь идёт о пути, который посещает любой узел не более одного раза.

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

Как бы я решал. Берём все листья. От каждого начинаем двигаться вверх (желательно делать это по уровням). На каждом родителе для дальнейшего движения из двух пришедших в него путей оставляем длиннейший, а текущую сумму сравниваем с текущей максимальной в аккумуляторе, и если она больше, то перезаписываем аккумулятор, кладя в него и новую макс. сумму, и оба составляющих её пути. По завершении в аккумуляторе будем иметь длиннейший путь (если таковых несколько - какой-то один из них, или можно запоминать все).]]> Akina Алгоритмы https://forum.sources.ru/index.php?showtopic=420994&view=findpost&p=3842698 Wed, 09 Dec 2020 12:00:26 +0000 Поиск наидлиннейшего пути в бинарном дереве поиска https://forum.sources.ru/index.php?showtopic=420994&view=findpost&p=3842698 Дано двоичное дерево поиска. Ключи - целые числа. Нужно найти самый длинный путь (максимальной длины) между двумя любыми вершинами дерева с разным числом потомков.

Для начала я бы хотел уточнить:
1. путь может проходить как угодно по дереву, т е, например из левого дерева подниматься к корню и затем уходить в правое поддерево? Т е путю необязательно двигаться по связям вершин дерева?
2. вроде гарантируется, что одной из такой вершин будет лист, т к появление листа гарантировано увеличивает протяженность пути на +1. Два листа быть не может, т к у них будет равное число потомков = 0.
3. число потомков ведь может быть 0, когда берется лист
4. вроде не гарантируется, что эти две вершины будут лежать по разные стороны от корня исходного дерева? Например, ДДП, которое выродилось в ЛОС, там все элементы принадлежат одному из поддеревьев. Кстати, в случае ЛОС-ДДП максимальный путь будет проложен от корня до листа.

Какие мысли есть: найти кол-во потомков для КАЖДОГО узла исходного ДДП (это я знаю, как сделать). А даст ли это что-нибудь?! Наверное, придется еще получить номер уровня для каждого узла дерева, не знаю)

Может существует какое-то простое решение (типа одной рекурсивной функцией), решающее такую проблему??

P.S. возможно, что здесь нужно каким-то боком задействовать дин.прогр. + может быть, преобразовать структуру в граф (хотя дерево и так есть разновидность графа в любом случае)]]> FasterHarder Алгоритмы