Структуры данных задачи деревья

Задания про двоичные деревья

В первой строке входа дано число N, после него следует N строк с командами для двоичной кучи. Необходимо начать с пустой кучи. Если в строке написано число, нужно добавить его в кучу. Если в строке написано GET, нужно написать в выходной файл текущий максимальный элемент кучи и удалить его из кучи.

11 10 30 GET 40 20 60 10 GET GET 0 GET 

Двоичные деревья поиска

Эту задачу можно решать для разных двоичных деревьев:

1. Двоичное дерево поиска, наивная реализация без оптимизаций: материалы про наивную реализацию
2. Декартово дерево: материалы про декартово дерево
3. Дерево из стандартной библиотеки вашего языка. Найдите у себя в языке такое дерево и воспользуйтесь им для решения задачи.

Реализуйте те деревья, которые сами считаете нужным. Я рекомендую реализовать пункт 3 всем, чтобы познакомиться со стандартной библиотекой своего языка. 1 я рекомендую только тем, кто этого не делал. 2 рекомендую всем, у кого осталось на это время после решения других задач.

Только проверка на вхождение элемента

В стандартном входе в первой строке написано число N, оно означет количество чисел, которые будут даны дальше для добавления в двоичное дерево. Заведите пустое двоичное дерево поиска. Дальшее в N строках находится по одному числу. Для каждого числа вы сначала проверяете, было ли это число в дереве, а потом добавляете число в дерево, если его не было. В вывод в отдельную строку нужно написть + или — в зависимости от того, было ли число в дереве. Т.е., встречалось ли оно раньше. Например, для входа 4 10 20 10 30 (в примере всё в одну строку) вы должны вывести — — + — .

Для проврки файлы с тестами заканчиваются на слово contains , например, 1.contains.out .

Поиск следующего элемента

Задача аналогична предыдущей, но кроме знака + или — в строку надо вывести следующее по порядку число за вставленным. Или — , если такого числа нет. Например, для входа 5 20 10 20 40 30 (в примере всё в одну строку) вы должны вывести

- - (потому что 20 еще нет) - 20 (потому что сразу за 10 в дереве идет число 20 по порядку) + - (число 20 есть, но следующего по порядку за ним нет) - - - 40 (числа 30 нет, но по порядку за ним идет 40) 

Для проверки файлы с тестами заканчиваются на слово min-after , например, 1.min-after.out .

Источник

14.10. Задачи на бинарные деревья

1. Найти сумму элементов бинарного дерева. 2. Найти вершины, у которых количество потомков в левом поддереве не равно количеству потомков в правом поддереве. 3. Найти вершины, для которых высота левого поддерева не равна высоте правого поддерева.

4. Написать функцию, которая определяет число вхождений элемента x в бинарное дерево. 5. Найти максимальный элемент бинарного дерева и количество повторений максимального элемента в данном дереве. 6. Написать функцию, которая определяет, есть ли в бинарном дереве хотя бы два одинаковых элемента. 7. Написать функцию, определяющую максимальное количество одинаковых элементов бинарного дерева. 8. Написать функцию, которая определяет, является ли бинарное дерево симметричным. 9. Написать функцию, которая определяет, является ли бинарное дерево деревом поиска. 10. Вывести все листья дерева поиска в порядке возрастания. 11. Пусть имеется бинарное дерево T . Сформировать два идеально сбалансированных дерева из отрицательных и неотрицательных элементов дерева T . 12. Вывести на экран все пути, ведущие от корня к листьям бинарного дерева, у которых суммарный вес элементов минимальный. 13. Найти последний номер из всех уровней бинарного дерева, на которых есть положительные элементы. 14. На каждом уровне бинарного дерева найти максимальный элемент. 15. На каждом уровне дерева найти количество внутренних вершин и количество листьев. 16. Найти суммы элементов всех нечетных уровней. 17. Найти минимальный и максимальный пути между листьями бинарного дерева. 18. Удалить из бинарного дерева наименьшее количество вершин таким образом, чтобы полученное дерево было строго бинарным. 19. Пусть имеется текстовый файл. Используя дерево поиска, создать другой текстовый файл – частотный словарь, содержащий слова и количество появлений каждого слова в исходном файле. 20. Написать функцию, которая осуществляет послойный обход бинарного дерева , при котором значения вершин печатаются от уровня к уровню, начиная с корневой вершины. Значения вершин дерева на каждом уровне печатаются слева направо. Для

реализации алгоритма использовать структуру очередь следующим образом. На первом шаге вставить в очередь корневую вершину. Затем прописать цикл, работающий по такому принципу. Пока очередь не пуста: 1) берем из очереди первый элемент q ; 2) выводим значение элемента q на экран; 3) если у вершины q есть левая вершина-потомок в дереве, то добавляем этот потомок в очередь; 4) если у вершины q есть правая вершина-потомок в дереве, то добавляем этот потомок в очередь; 5) удаляем из очереди элемент q .

Источник

Запросы на деревьях

В этой статье мы рассмотрим различные методы сведения задач на деревьях к задачам на отрезках, которые можно решать уже известными структурами данных.

Перед прочтением рекомендуется вспомнить свойства массивов $tin$ и $tout$, получаемых обходом в глубину.

#Запросы на поддеревьях

Первым важным свойством dfs является то, что $tin$-ы вершин любого поддеререва являются каким-то непрерывным отрезком.

Это свойство можно использовать для обработки разных запросов на поддеревьях, сводя их к запросам на подотрезках, которые уже можно решать стандартными методами — например, через дерево отрезков.

#Сумма на поддереве

Задача. Дано корневое дерево. Рядом с каждой вершиной записано число. Поступают два типа запросов: изменить какое-то из значений и найти сумму значений на поддереве вершины $v_i$.

Выпишем все числа у вершин в один массив в позиции, соответствующие их $tin$-ам. Что такое «сумма на поддереве $v$» в терминах этого массива? Это просто сумма на подотрезке $[tin_v, tout_v)$.

Построим поверх массива дерево отрезков или любую другую структуру для динамической суммы, и для запросов первого типа будем отправлять структуре запрос изменения ячейки $a_ = x$, а для второго будем делать запрос суммы на подотрезке $[tin_v, tout_v)$.

#Запросы на уровнях

Помимо $tin$ и $tout$ бывает полезно во время обхода считать глубину вершины. Будем в дальнейшем обозначать её за $depth_v$.

#Level Ancestor

Задача. Дано корневое дерево. Требуется отвечать на запросы нахождения $d_i$-того предка вершины $v_i$, то есть вершины-предка, находящейся на расстоянии $d_i$ от $v_i$.

Создадим $h$ векторов, где $h$ — высота дерева. Для каждой вершины, во время прохода в dfs, добавим её $tin$ в вектор, соответствующей её глубине. Получаем $h$ отсортированных векторов.

Теперь заметим, что внутри одного вектора все отрезки поддеревьев вершин — $[tin_v, tout_v)$ — тоже не пересекаются, а значит ещё и отсортированы. Тогда для ответа на запрос мы можем просто взять $tin$ вершины-запроса, посмотреть на вектор нужного уровня и за $O(\log n)$ сделать бинпоиск по нужному отрезку.

Также существует другой способ, требующий $O(1)$ времени на запрос, но $O(n \log n)$ памяти на предподсчет — лестничная декомпозиция.

#Поддеревья заданной глубины

Задача. Дано корневое дерево. Рядом с каждой вершиной записано число. Поступают два типа запросов: изменить какое-то из значений и найти сумму значений на поддереве вершины $v_i$ среди вершин на расстоянии не более $k_i$ от неё.

Когда используется одновременно и глубина, и структура дерева, обычно помогает взглянуть на задачу геометрически. Сопоставим каждой вершине точку $(tin_u, depth_u)$. Тогда как выглядят искомые множества вершин? Они соответствуют тем точкам, у которых первая координата лежит между $tin_v$ и $tout_v$, а вторая больше $depth_v$.

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

#Запросы на путях

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

#Сумма на пути

Задача. Дано дерево. У каждого ребра есть какое-то число. Нужно отвечать на запросы нахождения суммы на пути.

Предподсчитаем во время обхода в глубину массив $s$, где $s_v$ это сумма чисел на пути от корня до вершины $v$.

Любой путь в дереве разбивается на один или два вертикальных пути. Найдем наибольшего общего предка $c = lca(a, b)$ и разобьём сумму как $(s_a + s_b — 2 \cdot s_c)$.

#Xor на пути

Задача. Дано дерево. У каждого ребра есть какое-то число. Нужно отвечать на запросы нахождения xor -суммы на пути.

Заметим, что в случае с xor -суммой не нужно даже искать эти пути — по модулю двойки слагаемое $2 \cdot s_c$ «отменит» само себя. Достаточно просто вывести s[a] ^ s[b] .

#Число различных чисел на пути

Задача. Дано дерево. У каждого ребра есть какое-то число. Требуется отвечать на $q$ запросов нахождения числа различных значений на пути с $v$ по $u$.

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

• Выпишем эйлеров обход дерева: при каждом проходе по ребру выписываем номер ребра (номер нижней/верхней вершины). Заметим, что каждое ребро будет выписано дважды: при входе и выходе из нижней вершины.
• Получив запрос, определим «более раннюю» вершину $v$ (с меньшим $tin_v$) и рассмотрим подотрезок эйлерова обхода с $tin_v$ по $tin_u$.
• Какая-то подпоследовательность ребер на этом отрезке является кратчайшим путем между $v$ и $u$. А именно, это будут ровно те ребра, которые встречались на этом отрезке ровно один раз — все, которые встречались дважды, ведут в какие-то побочные поддеревья.

Теперь рядом с номерами ребер в обходе выпишем ещё и соответствующие им числа. Тогда запрос нахождения числа различных значений на пути эквивалентен нахождению числа различных значений у ребер, встречающихся ровно один раз на подотрезке. Эту задачу уже можно решить обычным алгоритмом Мо.

Источник