Основные понятия. Деревом называется связный граф без циклов

Т е м а 1. БИНАРНЫЕ ПОИСКОВЫЕ ДЕРЕВЬЯ

Деревом называется связный граф без циклов. На практике часто приходится иметь дело со специальными видами деревьев. Наиболее распространенным среди них является корневое дерево.

Корневое дерево - это ориентированный граф, который удовлетворяет следующим условиям:

1) имеется в точности одна вершина, в которую не входит ни одна дуга, называемая корнем;

2) в каждую вершину, кроме корня, входит ровно одна дуга;

3) из корня имеется путь к каждой вершине.

Если в корневом дереве существует путь из v в w, то v называют предком вершины w, а w - потомком вершины. Если вершина не имеет потомков, то ее называют висячей вершиной или листом. Остальные вершины называют внутренними. Если (v, w) - дуга корневого дерева, то v называется отцом (непосредственным предком) вершины w, а w называется сыном (непосредственным потомком) вершины v. Вершина корневого дерева T и все ее потомки вместе образуют поддерево корневого дерева T с корнем в вершине v.

Глубиной вершины v в корневом дереве называется длина в дугах пути (этот путь единственный) из корня в эту вершину.

Высотой вершины v в корневом дереве называется длина (в дугах) максимального пути из вершины v до одного из его потомков. Высота корневого дерева - высота корня. Высота дерева, состоящего из одной единственной вершины, полагается равной 0.

Уровнем вершины v называется разность высоты дерева и глубины вершины v.

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

Бинарное дерево - это упорядоченное корневое дерево, у каждой вершины которого имеется не более двух сыновей. В бинарном дереве каждый сын произвольной вершины определяется как левый или правый. Поддерево (если оно существует), корнем которого является левый сын вершины v, называется левым поддеревом вершин ы v. Аналогичным образом определяется правое поддерево для вершины v.

Существует несколько способов представления бинарных деревьев (предполагаем, что вершины дерева занумерованы целыми числами от 1 до n).

1. Представление в виде двух массивов - Left и Right:

· если вершина является левым (правым) сыном вершины i, то ;

· если у вершины i нет левого (правого) сына, то .

2. Представление в виде списковой структуры:

type

tree_ptr = ^ tree node;

tree_node = record

element: element type;

left: tree_ptr;

right: tree_ptr;

end;

Предположим, что каждой вершине бинарного дерева соответствует некоторое ключевое значение (например, целое число). Бинарное дерево называется деревом поиска (бинарным поисковым деревом), если оно организовано так, что для каждой вершины v,справедливо утверждение, что все ключи в левом поддереве вершины v, меньше ключа вершины v, а все ключи в правом поддереве больше. В поисковом дереве нет двух вершин с одинаковыми ключевыми значениями. Минимальный (максимальный) элемент бинарного поискового дерева соответствует ключевому значению самой левой (правой) вершины дерева.

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

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

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

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

procedure order1 (v: tree_ptr);

begin

if v ≠ nil then

begin

solve (v);

order1 (v ^. left);

order1 (v ^. right);

end;

end;

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

procedure order2 (v: tree_ptr);

begin

if v ≠ nil then

begin

order2 (v ^. left);

order2 (v ^. right);

solve (v);

end;

end;

3. Внутренний порядок обхода (слева направо) заключается в том, что корень посещается после посещения одного из его поддеревьев. Если корень посещается после его левого (правого) поддерева, то обход называется левым (правым) внутренним обходом. Приведем процедуру левого внутреннего обхода.

procedure order3 (v: tree_ptr);

begin

if v ≠ nil then

begin

order3 (v ^. l eft);

solve (v);

order3 (v ^. right);

end;

end;

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

В некоторых задачах требуется выполнить удаление вершиныv из дерева (предположим, что f – отец этой вершины).

Задача удаления достаточно проста, если у удаляемой вершины v не более одного поддерева (предположим, что если поддерево существует, то w – его корень). В этом случае происходит непосредственное удаление вершины v, после чего выполняются следующие действия:

· если v - корень дерева, то корнем дерева станет вершина w (если у вершины v поддеревьев не было, то получаем пустое дерево);

· если v - лист, то ссылка у вершины f, указывающая на вершину v, станет пустой;

· если v не лист и не корень дерева, то ссылка у f, указывающая на v, будет указывать на w (рис. 1).

Рис. 1

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

Предположим, что минимальный ключ в правом поддереве вершины v имела вершина z. Теперь в дереве появились две вершины v и z с одинаковыми ключевыми значениями, что не допустимо для бинарного поискового дерева (рис. 2).

Рис. 2

Удаляем вершину z из дерева (заметим, что вершина z не имеет правого поддерева) и завершаем процедуру удаления.

Задачи

Необходимо построить бинарное поисковое дерево для последовательности вводимых чисел и выполнить для него требуемые действия. В задачах предполагается, что у пустого дереваколичество вершин равно 0, а высота пустого дерева равна −1.

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

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

3. Найти и удалить (правым удалением) среднюю по значению вершину из вершин дерева, у которых количество потомков в левом поддереве отличается от количества потомков в правом поддереве на 1. Выполнить прямой (левый) обход полученного дерева (5 баллов).

4. Найти высоту дерева h и удалить (правым удалением) среднюю по значению вершину из вершин дерева на уровне [ h / 2], для которых количество потомков в левом поддереве больше, чем количество потомков в правом поддереве. Выполнить прямой (левый) обход полученного дерева (6 баллов).

5. Среди минимальных путей между листьями выбрать тот, у которого сумма ключей всех его вершин минимальна, и удалить (правым удалением) центральную вершину этого пути. Выполнить прямой (левый) обход полученного дерева (8 баллов).

6. Среди максимальных путей в дереве выбрать тот, у которого сумма ключей всех его вершин максимальна, затем удалить центральную вершину и корень этого пути (правым удалением). Выполнить прямой (левый) обход полученного дерева (8 баллов).

7. Найти высоту дерева h и удалить (правым удалением) среднюю по значению из вершин на уровне [ h / 2], у которых высота левого поддерева равна высоте правого поддерева. Выполнить прямой (левый) обход полученного дерева (6 баллов).

8. Среди максимальных путей в дереве выбрать тот, у которого корневая вершина находится на наименьшей глубине, и удалить (правым удалением) корневую вершину этого пути. Выполнить прямой (левый) обход полученного дерева (6 баллов).

9. Найти все вершины дерева, через которые проходят пути максимальной длины, и удалить (правым удалением) ту из них, ключ которой является вторым по значению. Выполнить прямой (левый) обход полученного дерева (8-9 баллов).

10. Найти все вершины дерева, через которые проходит наибольшее количество путей максимальной длины, и удалить их (правым удалением). Выполнить прямой (левый) обход полученного дерева (8-9 баллов).

11. Среди максимальных путей дерева выбрать тот, у которого сумма ключей конечных вершин минимальна, и удалить (правым удалением) корневую вершину этого пути. Выполнить прямой (левый) обход полученного дерева (7-8 баллов).

12. Среди всех путей дерева, соединяющих вершины с разным числом потомков, выбрать путь максимальной длины, у которого сумма ключей конечных вершин минимальна. Удалить (правым удалением) среднюю по значению вершину этого пути. Выполнить прямой (левый) обход полученного дерева (9-10 баллов).

13. Среди всех путей дерева, соединяющих вершины на разной высоте, выбрать путь максимальной длины, у которого сумма ключей конечных вершин минимальна. Удалить (правым удалением) среднюю по значению вершину этого пути. Выполнить прямой (левый) обход полученного дерева (9-10 баллов).

14. Среди всех путей, соединяющих корень и листья дерева, выбрать пути минимальной длины. Для каждого из этих путей найти и удалить (левым удалением) среднюю по значению вершину пути. Выполнить прямой (левый) обход полученного дерева (6-7 баллов).

15. Заданы два дерева. Удалить (правым удалением) корень каждого дерева и определить, являются ли два полученных дерева зеркальным отражением друг друга по структуре. Выполнить прямой (левый) обход каждого из полученных деревьев (5 баллов).

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

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

18. Найти все вершины, через которые проходит четное число путей максимальной длины, и удалить (правым удалением) ту из них, ключ которой наименьший. Выполнить прямой (левый) обход полученного дерева (9-10 баллов).

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

20. Среди всех путей дерева, соединяющих вершины на разном уровне, выбрать путь максимальной длины, для которого сумма ключей конечных вершин минимальна. Сделать центральную вершину этого пути корнем дерева методом поворотов (дерево не обязательно останется поисковым). Выполнить прямой (левый) обход полученного дерева (9-10 баллов).

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

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

23. Пусть k – некоторое неотрицательное число. Найти все вершины, через которые проходят пути длины k, соединяющие листья дерева. Выбрать те из них, которые находятся на наименьшей глубине, и удалить (левым удалением) среднюю по значению вершину. Выполнить прямой (левый) обход полученного дерева (9-10 баллов).

24. Найти все пути длины h, соединяющие листья дерева (h – высота дерева). Среди корней этих путей выбрать те, которые расположены на максимальной глубине, и удалить (правым удалением) тот из них, который является средним по значению. Выполнить прямой (левый) обход полученного дерева (9-10 баллов).

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

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

27. Найти все листья дерева, выбрать из них средний по значению и удалить (правым удалением) его отца (если дерево состоит из единственной вершины, то удаляем эту вершину). Выполнить прямой (левый) обход полученного дерева (4-5 баллов).

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

29. Найти и удалить (левым удалением) среднюю по значению вершину дерева, у которой количество потомков в левом поддереве отличается от количества потомков в правом поддереве на 2. Выполнить прямой (левый) обход полученного дерева (6 баллов).

30. Найти и удалить (левым удалением) среднюю по значению вершину дерева, у которой высота левого поддерева отличается от высоты правого поддерева на 2. Выполнить прямой (левый) обход полученного дерева (6 баллов).

31. Найти вершины, через которые проходит нечетное число путей максимальной длины, и удалить (правым удалением) ту из них, ключ которой наибольший. Выполнить прямой (левый) обход полученного дерева (9-10 баллов).

32. Найти и удалить (правым удалением) среднюю по значению вершину дерева, через которую проходит четное число путей максимальной длины. Выполнить прямой (левый) обход полученного дерева (9-10 баллов).