Билет 12. Деревья. Общие определения

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

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

Вершина, у которой нет потомков, называется листом дерева.

Вершина, находящаяся на 0 уровне, называется корнем дерева.

Вершина, которая не является листом, называется внутренне вершиной

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

Количество потомков вершины называется степенью данной вершины, степень дерева – максимально возможная степень.

Число ветвей (ребер), которые необходимо пройти от корня к вершине х, называется длиной пути к х. Длина пути всего дерева определяется как сумма всех путей для вершин.

Средняя длина пути обычного дерева определяется по формуле:

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

Упорядоченные деревья второй степени называются двоичными деревьями.

Деревья n-ной (большей 2) степени называются сильно ветвящимися.

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

Билет 13. Двоичные деревья

Двоичное дерево – конечное множество элементов (узлов), которое либо пусто, либо состоит из корня с двумя отдельными двоичными поддеревьями, которые называют левым и правым поддеревом корня.

Для построения двоичного дерева, имеющего минимальную высоту, используются следующие правила:

1. Использовать один узел в качестве корня

2. Построить левое поддерево так, чтобы число узлов n_l = n div 2

3. Построить правое поддерево так, чтобы число узлов n_r = n-n_l-1

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

Основными операциями, осуществляемыми с бинарными деревьями, являются:

• создание бинарного дерева;

• печать бинарного дерева;

• обход бинарного дерева;

• вставка элемента в бинарное дерево;

• удаление элемента из бинарного дерева;

• проверка пустоты бинарного дерева;

• удаление бинарного дерева

Билет 14. Деревья поиска

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

Операции:

• Обход дерева

О бход дерева можно совершать тремя способами:

1. A,L,R (префиксный обход)

2. L,A,R (инфиксный обход)

3. L,R,A (постфиксный обход)

• Поиск вершины

Использование двоичного дерева поиска позволит найти искомую вершину за О(log n), причем высота дерева составляет log₂n.

• Добавление

Данная операция соотносится с операцией поиска и они объединяются в одну – поиска-включения. При этом минимальной время – O(log₂n), максимальное - O(n). Аналогом по быстродействию является быстрая сортировка и поиск медианы в ней.

Алгоритм: Если дерево пусто, заменить его на дерево с одним корневым узлом ((K,V), null, null) и остановиться.

Иначе сравнить K с ключом корневого узла X.

• Если K>=X, рекурсивно добавить (K,V) в правое поддерево Т.

• Если K<X, рекурсивно добавить (K,V) в левое поддерево Т.

• Удаление

Алгоритм: Если дерево T пусто, остановиться;

Различают 3 случая:

• Отсутствует компонента с ключом, равным х.

• У компоненты с ключом х не более 1 потомка.

• У компоненты с ключом х 2 потомка. В этой ситуации элемент должен быть заменен либо на самый правый элемент левого поддерева. либо на самый левый элемент правого поддерева.

Вычисление средней длины пути в дереве поиска:

Красно-чёрное дерево - одно из самобалансирующихся двоичных деревьев поиска, гарантирующих логарифмический рост высоты дерева от числа узлов и быстро выполняющее основные операции дерева поиска: добавление, удаление и поиск узла. Сбалансированность достигается за счет введения дополнительного атрибута узла дерева — «цвет». Итак, дерево называется красно-черным, если:

1. Каждая вершина имеет цвет (красный или черный)

2. Если вершина красная, то оба ее потомка – черные

3. Все пути от корня к листьям содержат одинаковое количество черных вершин

Все основные операции имеют сложность O(log n).