Поиск наидлиннейшего пути в бинарном дереве поиска

@FasterHarder · Регистрация: 28.04.2015

Студворк — интернет-сервис помощи студентам

Всем привет!

Дано двоичное дерево поиска. Ключи - целые числа. Нужно найти самый длинный путь (максимальной длины) между двумя любыми вершинами дерева с разным числом потомков.

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

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

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

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

@Shamil1 · 09.12.2020, 16:53

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

Добавлено через 33 минуты
Можно и рекурсивно:

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public (int length, int height) Solve(Node node)
{
    if(node == null) return (0, 0);
    
    var left = Solve(node.Left);
    var right = Solve(node.Right);
    
    var height = Math.Max(left.height, right.height) + 1;
    
    var length1 = Math.Max(left.length, right.length);
    var length2 = left.height + right.height + 1;
    var length = Math.Max(length1, length2);
    
    return (length, height);
}
 
public class Node
{
    public Node Left { get; set; }
    public Node Right { get; set; }
}

Максимальная длина пути в поддереве - это (что больше) длина пути с вершиной в корне или максимальная длина пути в одном из поддеревьев.

@FasterHarder · 09.12.2020, 16:54 **[ТС]**

Shamil1, у меня такое чувство, что ты почему-то уверен, что искомый путь должен проходить через корень начального дерева, но это вроде ведь не так + фраза "останавливаемся, когда становится известно", как бы не поясняет эту известность совсем)

@Shamil1 · 09.12.2020, 16:54

Вершиной пути я называю "точку перелома".

Добавлено через 43 секунды

Сообщение от FasterHarder

у меня такое чувство, что ты почему-то уверен, что искомый путь должен проходить через корень начального дерева

Нет, конечно.

@FasterHarder · 09.12.2020, 16:57 **[ТС]**

кода не видел, когда писал мессагу выше)
за код спс. Кстати, странный синтаксис для C# при объявлении функции,ну да ладно)

p.s. а ты код тестировал?) или вот прям уверен, что там все идеально работает.

@Shamil1 · 09.12.2020, 16:59

Сообщение от FasterHarder

фраза "останавливаемся, когда становится известно"

Максимальная длина пути в поддереве не может быть больше, чем 2*h(root) - 1, где h(root) - высота.
Максимальная длина пути в дереве не может быть меньше, чем h(left) + h(right) + 1.
Эти правила можно использовать для отсечения (в нерекурсивном алгоритме).

Добавлено через 55 секунд

Сообщение от FasterHarder

а ты код тестировал?

Даже не запускал.

@FasterHarder · 09.12.2020, 17:00 **[ТС]**

Shamil1, сколько времени ты уделял изучению деревьев, что вот так вот сходу понимаешь их анатомию насквозь??) Деревья ведь совсем нетривиальная структура, ИМХО!

p.s. на данный момент я пока не понял твое решение даже на 30%, наверное, надо разбираться оч.плотно

@Shamil1 · 09.12.2020, 17:29

Вот описание решения:

Сообщение от Shamil1

Максимальная длина пути в поддереве - это (что больше) длина пути с вершиной в корне или максимальная длина пути в одном из поддеревьев.

Подробней:
Функция возвращает высоту и максимальную длину пути.
Высота = максимальная высота поддерева плюс 1
Максимальная длина пути = максимальная длина пути в поддеревьях или длина пути от самого глубокого листа в левом поддереве через корень до самого глубокого листа в правом поддереве

@FasterHarder · 09.12.2020, 18:30 **[ТС]**

Сообщение от Shamil1

Максимальная длина пути = максимальная длина пути в поддеревьях или длина пути от самого глубокого листа в левом поддереве через корень до самого глубокого листа в правом поддереве

только я бы еще добавил, что "-1", т к кол-во потомков на концах пути должно быть разным
разве не так?

@Shamil1 · 10.12.2020, 09:28

Сообщение от FasterHarder

кол-во потомков на концах пути должно быть разным

Нет. Оба поддерева могут иметь одинаковую высоту.

@FasterHarder · 10.12.2020, 10:46 **[ТС]**

у меня получилось нечто такое, ВРОДЕ работает, но, например, когда ДДП-ЛОС, то путь короче на 1, печаль)

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
    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;
    }

в чем тут загвоздка или совсем не то все??

@Shamil1 · 10.12.2020, 15:27

Сообщение от FasterHarder

у меня получилось нечто такое

Что такое GMP, LPK, GH?
Зачем нужна глобальная переменная maxP?

Сообщение от FasterHarder

вот эта "-1" связана с логикой

Не зная, что возвращает GH и что такое "длина пути" (количество узлов или количество рёбер?), ничего не могу сказать.

Сообщение от FasterHarder

ВРОДЕ работает

МаксПуть проходит через корень или не проходит.
В первом случае длина (количество узлов) равна сумме высот поддеревьев + 1 (корень).
Во втором случае длина равна длине МаксПути в одном из двух поддеревьев.
На этом основана рекурсия.

Хотя, конечно, можно найти максимум (по всем узлам) суммы высот поддеревьев. Но тогда надо заранее вычислить высоту для каждго узла, чтобы не делать это много раз для одного узла. Высоту можно вычислить за один обход дерева. Но тогда почему бы одновременно с вычислением высоты не вычислять МаксПуть (как в моём коде)?

@FasterHarder · 12.12.2020, 07:44 **[ТС]**

Сообщение от Shamil1

Что такое GMP, LPK, GH?
Зачем нужна глобальная переменная maxP?

Сообщение от Shamil1

Не зная, что возвращает GH и что такое "длина пути" (количество узлов или количество рёбер?), ничего не могу сказать.

GMP - G - получить, M - максимальный, Р - путь - это сама функция, которая нужна
LPK - левый + правый + корень - это функция сейчас не используется
GH - получить высоту заданного поддерева

Вот исходники этих функций:

C++ (Qt)
1
2
3
4
5
6
int GH(const TREE* proot)
{
    if(proot == NULL)
        return 0;
    return (1 + max(GH(proot->left), GH(proot->right)));
}

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int maxP = 0;   // хранит длину максимального пути
int GMP(const TREE* proot)
{
    if(proot != NULL)
    {
        GMP(proot->left);
        GMP(proot->right);
        int currentP = GH(proot->left) + GH(proot->right);
        if(currentP > maxP)
            maxP = currentP;
        return maxP;
    }
    else
        return 0;
}

я не знаю, как сделать без глобальной переменной.
Все вроде шикарно работает, кроме одного вырожденного случая, когда двоичное дерево является ЛОСом, т е все узлы в одном поддереве.

Длина пути: количество посещенный связей/ребер.

Вот как победить двоичное дерево в виде списка???

Добавлено через 1 минуту
Еще забыл добавить, что в качестве ответа печатается GMP(корень) - 1, т е вычитаем 1цу из результата, т к один из концов пути не должен быть листом.

@Shamil1 · 12.12.2020, 14:48

Сообщение от FasterHarder

GH - получить высоту заданного поддерева

Для получения высоты обходится всё поддерво. Зачем обходить поддерово для получения высоты узла, если мы его уже обходили для получения высоты его родителя?
Лучше пусть GMP возвращает и максимальный путь и высоту (кортеж, пару или структуру с двумя полями).

Сообщение от FasterHarder

я не знаю, как сделать без глобальной переменной.

В данном случае - просто уберите её за ненадобностью. МДП дерева (которую Вы возвращаете), не может быть меньше МДП поддерева.
У Вас же получается не рекурсия, итеррация по дереву с помощью рекурсии.

Сообщение от FasterHarder

Вот как победить двоичное дерево в виде списка???

В строке 8 добавить "+ 1".
Сейчас у Вас МДП от NULL равна 0 и МДП листа равна 0. Вы не различаете эти случаи.

@FasterHarder · 12.12.2020, 15:58 **[ТС]**

Shamil1, спс за ответ, но, сорри, я ничего не понял

@Shamil1 · 12.12.2020, 17:54

Сообщение от FasterHarder

я ничего не понял

А конкретней? Если Вас интересует объяснение, то напишите подробно, что Вы не поняли.

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .	SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .	SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .	SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .	Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .	SDL3 для Android: Загрузка PNG с альфа-каналом с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .

@FasterHarder 383 / 280 / 112 Регистрация: 28.04.2015 Сообщений: 1,726

	Поиск наидлиннейшего пути в бинарном дереве поиска 09.12.2020, 15:02. Показов 6581. Ответов 15 Метки нет (Все метки) Всем привет! Дано двоичное дерево поиска. Ключи - целые числа. Нужно найти самый длинный путь (максимальной длины) между двумя любыми вершинами дерева с разным числом потомков. Для начала я бы хотел уточнить: 1. путь может проходить как угодно по дереву, т е, например из левого дерева подниматься к корню и затем уходить в правое поддерево? Т е путю необязательно двигаться по связям вершин дерева? 2. вроде гарантируется, что одной из такой вершин будет лист, т к появление листа гарантировано увеличивает протяженность пути на +1. Два листа быть не может, т к у них будет равное число потомков = 0. 3. число потомков ведь может быть 0, когда берется лист 4. вроде не гарантируется, что эти две вершины будут лежать по разные стороны от корня исходного дерева? Например, ДДП, которое выродилось в ЛОС, там все элементы принадлежат одному из поддеревьев. Кстати, в случае ЛОС-ДДП максимальный путь будет проложен от корня до листа. Какие мысли есть: найти кол-во потомков для КАЖДОГО узла исходного ДДП (это я знаю, как сделать). А даст ли это что-нибудь?! Наверное, придется еще получить номер уровня для каждого узла дерева, не знаю) Может существует какое-то простое решение (типа одной рекурсивной функцией), решающее такую проблему?? P.S. возможно, что здесь нужно каким-то боком задействовать дин.прогр. + может быть, преобразовать структуру в граф (хотя дерево и так есть разновидность графа в любом случае) 0

@FasterHarder 383 / 280 / 112 Регистрация: 28.04.2015 Сообщений: 1,726
	09.12.2020, 16:54 [ТС]
	Shamil1, у меня такое чувство, что ты почему-то уверен, что искомый путь должен проходить через корень начального дерева, но это вроде ведь не так + фраза "останавливаемся, когда становится известно", как бы не поясняет эту известность совсем) 0

@FasterHarder 383 / 280 / 112 Регистрация: 28.04.2015 Сообщений: 1,726
	09.12.2020, 16:57 [ТС]
	кода не видел, когда писал мессагу выше) за код спс. Кстати, странный синтаксис для C# при объявлении функции,ну да ладно) p.s. а ты код тестировал?) или вот прям уверен, что там все идеально работает. 0

@FasterHarder 383 / 280 / 112 Регистрация: 28.04.2015 Сообщений: 1,726
	09.12.2020, 17:00 [ТС]
	Shamil1, сколько времени ты уделял изучению деревьев, что вот так вот сходу понимаешь их анатомию насквозь??) Деревья ведь совсем нетривиальная структура, ИМХО! p.s. на данный момент я пока не понял твое решение даже на 30%, наверное, надо разбираться оч.плотно 0

@FasterHarder 383 / 280 / 112 Регистрация: 28.04.2015 Сообщений: 1,726
	12.12.2020, 15:58 [ТС]
	Shamil1, спс за ответ, но, сорри, я ничего не понял 0