32. Деревья. Бинарные деревья.

Дерево — это связный ациклический граф.^[1] Связность означает наличие путей между любой парой вершин (связаны между собой отношениями типа «родительская вершина – дочерняя вершина), ацикличность — отсутствие циклов и то, что между парами вершин имеется только по одному пути.

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

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

Термин двоичное дерево (оно же бинарное дерево) имеет несколько значений:

• Неориентированное дерево, в котором число рёбер не превосходят 3.

• Ориентированное дерево, в котором число исходящих рёбер не превосходят 2.

Особым видом деревьев являются бинарные деревья. Бинарное дерево с вершинами типа T можно определить следующим образом:

• Это либо пустое дерево, не содержащее ни одной вершины;

• либо некоторая вершина типа T, соединенная ветвями с двумя бинарными деревьями с вершинами типа T (эти деревья называются левым и правым поддеревом).

  Пример бинарного дерева приведен на рис. 2; в нем вершина со значением 0 является корнем, все вершины со значением 1 являются левыми дочерними вершинами, а все вершины со значением 2 — правыми

.

33. Авл дерево: назначение, основные принципы.

АВЛ-дерево — сбалансированное по высоте двоичное дерево поиска.

Для каждой его вершины высота её двух поддеревьев различается не более чем на 1.

АВЛ — аббревиатура, образованная первыми буквами создателей (советских учёных) Адельсон-Вельского Г. Максимовича и Ландиса Е М. Записать

h = ln(n) + 1;

h - высота всего дерева;

n – число узлов.

Алгоритмы оптимизации АВЛ из тетрадки описать!

34. Кч дерево: назначение, основные принципы.

“Высота левого поддерева ЛЮБОГО узла отличается не более чем на +/-1 от высоты правого поддерева".

Свойства

Пример красно-чёрного дерева

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

Каждый узел-сосед старается иметь разный цвет. Каждый новый узел по-умолчанию изначально красного цвета, но при этом, цветами узлов оперируют следующие правила:

1. Узел либо красный, либо чёрный.

2. Корень — чёрный.

3. Все листья(NIL) — черные.

4. Оба потомка каждого красного узла — черные.

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

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

Изобретателем красно-чёрного дерева считают немца Рудольфа Байера. Название «красно-чёрное дерево» структура данных получила в статье Л. Гимпаса и Р. Седжвика (1978). В журнале были доступны две краски (красная и чёрная)[1] и дополнительный бит, «прикреплявшийся» к каждому из узлов, обозначался цветом.

h = ln(n) + 1;

h - высота всего дерева;

n – число узлов.

ОПЕРАЦИИ УПРОЩЕНИЯ КАК И У АВЛ-ДЕРЕВА !!!