Деревья. Лекция 11, 12 - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Деревья. Лекция 11, 12. Доклад-сообщение содержит 36 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

Деревья Лекция 11, 12

Слайд 2

Описание слайда:

План лекции Дерево, поддерево и др. определения Обходы деревьев Представление деревьев Дерево двоичного поиска АВЛ деревья

Слайд 3

Описание слайда:

Дерево Ориентированным деревом Т называется ориентированный граф G = (А,R) со специальной вершиной r А, называемой корнем, у которого степень по входу вершины r равна 0, степень по входу всех остальных вершин равна 1, каждая вершина аА достижима из r. Базовые свойства деревьев Дерево не содержит циклов Каждая вершина дерева соединяется с его корнем единственным путём

Слайд 4

Описание слайда:

Подерево, лес Поддеревом дерева Т = (А, R) называется такое дерево T' =(А', R'), что А' непусто и содержится в A R' = (A'хA')R все потомки вершин из множества А' принадлежат множеству А‘ Ориентированный граф, состоящий из нескольких деревьев, называется лесом

Слайд 5

Описание слайда:

Высота дерева Пусть Т=(A, R) – дерево, (a, b) R, тогда a – отец b, а b – сын a. Глубина или уровень вершины – длина пути от корня до этой вершины. Высота вершины – длина максимального пути от этой вершины до листа. Высота дерева – длина максимального пути от корня до листа. Глубина корня = 0.

Слайд 6

Описание слайда:

Бинарное (двоичное) дерево Упорядоченное дерево – это дерево, в котором множество сыновей каждой вершины упорядочено Бинарное дерево – это упорядоченное дерево, в котором каждая вершина имеет не более двух сыновей

Слайд 7

Описание слайда:

Полное бинарное дерево Бинарное дерево называется полным, если существует некоторое целое k, такое что любая вершина глубины меньше k имеет как левого, так и правого сына, а если узел имеет глубину k, то он является листом

Слайд 8

Описание слайда:

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

Слайд 9

Описание слайда:

Обходы в глубину Пусть T – дерево, r - корень, v1, v2, …, vn – сыновья вершины r Прямой (префиксный) обход Пронумеровать (посетить) корень r Пронумеровать в прямом порядке поддеревья с корнями v1, v2,…, vn Обратный (постфиксный) обход Пронумеровать в обратном порядке поддеревья с корнями v1, v2,…, vn Пронумеровать корень r Внутренний ( инфиксный) обход для бинарных деревьев Пронумеровать во внутреннем порядке левое поддерево корня r (если существует) Пронумеровать корень r Пронумеровать во внутреннем порядке правое поддерево корня r (если существует)

Слайд 10

Описание слайда:

Примеры обходов дерева в глубину Прямой Обратный Внутренний

Слайд 11

Описание слайда:

Обходы в глубину дерева синтаксического разбора арифметического выражения Префиксный обход + * a – d e / + f g c Постфиксный обход (обратная польская запись) a d e – * f g + c / + Инфиксный обход (обычная скобочная запись) a * (d – e)+ (f + g) / c

Слайд 12

Описание слайда:

Обход деревьев в ширину Обход вершин дерева по уровням от корня слева направо (или справа налево) Алгоритм обхода дерева в ширину Шаг 0: Поместить в очередь корень дерева Шаг 1: Взять из очереди очередную вершину Поместить в очередь всех ее сыновей по порядку слева направо (справа налево) Шаг 2: Если очередь пуста, то конец обхода, иначе перейти на Шаг 1

Слайд 13

Описание слайда:

Пример обхода дерева в ширину

Слайд 14

Описание слайда:

Бинарное дерево -- операции T -- данные tree_t -- двоичное дерево с данными Т place_t -- ячейка дерева tree_t create (); place_t left (place_t t); void insert (tree_t *t, T val); place_t right (place_t t); void erase (tree_t *t, T val); T getval (place_t t); place_t find (tree_t t, T val); void setval (place_t t, T val); void destroy (tree_t *t); place_t end ();

Слайд 15

$Представление бинарных деревьев с помощью указателей struсt place_t { T data; // данные struct place_t *left; // левое п/дерево struct place_t *right; // правое п/дерево }; struct tree_t { struct place_t *root; }; typedef struct tree_t tree_t; typedef struct place_t * place_t;$

Описание слайда:

Представление бинарных деревьев с помощью указателей struсt place_t { T data; // данные struct place_t *left; // левое п/дерево struct place_t *right; // правое п/дерево }; struct tree_t { struct place_t *root; }; typedef struct tree_t tree_t; typedef struct place_t * place_t;

Слайд 16

Описание слайда:

Слайд 17

Описание слайда:

Пример представления с помощью массива

Слайд 18

Описание слайда:

Скобочное представление деревьев Левое и правое скобочные представления Lrep(Т) и Rrep(Т) дерева Т строятся по следующим рекурсивным правилам Если корнем дерева Т служит вершина а, не имеющая прямых потомков, то Lrep (Т) = Rrep(T) = а Если корнем дерева Т служит вершина а с поддеревьями T1, Т2, . . ., Тn, расположенными в этом порядке (их корни — прямые потомки вершины а), то Lrep(Т) = а(Lrep (T1), Lrep (Т2) , . . ., Lrep (Тn)) Rrep(Т) = (Rrep(Т1), Rrep(T2), . . ., Rrep (Тn))а

Слайд 19

Описание слайда:

Пример скобочного представления неориентированного дерева Lrep(T) = b ( h ( a, j ( d ) ), i ( k ( e, f, g ), l ) ) Rrep(T) = ( ( a, ( d ) j ) h, ( ( e, f, g ) k, l ) i ) b

Слайд 20

$Пример печати левого скобочного представления двоичного дерева void print_Lrep (tree_t t) { print_Lrep_body (t.root); } void print_Lrep_body (place_t t) { if (t == end()) return; printf ("%d(", getval(t)); print_Lrep_body (left(t)); print_Lrep_body (right(t)); printf (")"); }$

Описание слайда:

Пример печати левого скобочного представления двоичного дерева void print_Lrep (tree_t t) { print_Lrep_body (t.root); } void print_Lrep_body (place_t t) { if (t == end()) return; printf ("%d(", getval(t)); print_Lrep_body (left(t)); print_Lrep_body (right(t)); printf (")"); }

Слайд 21

Описание слайда:

Представление дерева списком прямых предков Вершины дерева нумеруются числами от 1 до n i-й элемент списка прямых предков равен 0, если вершина i – это корень номер отца вершины i, иначе

Слайд 22

Описание слайда:

Дерево двоичного поиска Деревом двоичного поиска для множества S называется помеченное двоичное дерево, каждый узел v которого помечен элементом l(v)S так, что l(u) < l(v) для каждого узла u из левого поддерева узла v, l(w) > l(v) для каждого узла w из правого поддерева узла v, для любого элемента a S существует единственный узел v , такой что l(v) = a.

Слайд 23

Описание слайда:

Примеры ДДП Примеры ДДП для множества S = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

Слайд 24

Описание слайда:

Поиск в дереве двоичного поиска Вход Дерево Д двоичного поиска для множества S, элемент a. Выход истина, если aS ложь иначе логическая функция ПОИСК (a, Lrep(Д)) { если Lrep(Д) == x, то вернуть I(x) == a; иначе Lrep(Д) = x(Л, П); если а == I(х), то вернуть истина; иначе если a < I(x), то вернуть ПОИСК(а, Л); иначе вернуть ПОИСК(а, П); всё; всё; }

Слайд 25

Описание слайда:

Сбалансированные деревья АВЛ Георгий Михайлович Адельсон-Вельский р. 1922 Евгений Михайлович Ландис 1921-1997 Один алгоритм организации информации // Доклады АН СССР. 1962. Т. 146, № 2. C. 263–266

Слайд 26

Описание слайда:

Сбалансированные деревья АВЛ Время вставки вершины в дерево двоичного поиска, содержащее n вершин O(log2n) в лучшем случае для полных деревьев O(n) в худшем случае для вырожденных деревьев, имеющих структуру списка Можно устранить вырождение дерева в список и сократить время вставки вершины с O(n) до O(log2n) даже в худшем случае Дерево двоичного поиска сбалансировано, если высоты поддеревьев каждой из его вершин отличаются не более, чем на единицу

Слайд 27

Описание слайда:

Вставка вершины в АВЛ дерево АВЛ дерево вставка(значение x, АВЛ дерево T) если Т == NULL, то вернуть x(NULL,NULL) иначе T имеет вид a(L, R); TТ = x < a ? a(вставка(x, L), R) : a(L, вставка(x, R)); восстановить сбалансированность в корне дерева ТТ вернуть ТТ

Слайд 28

Описание слайда:

Вставка вершины в АВЛ дерево Высота ТТ == высота T ==> ТТ сбалансировано Высота ТТ == высота T + 1 и х < a hL == hR ==> ТТ сбалансировано hL < hR ==> ТТ сбалансировано hL > hR ==> ТТ НЕ сбалансировано

Слайд 29

Описание слайда:

Разгрузка левой-левой ветки

Слайд 30

Описание слайда:

Разгрузка правой-левой ветки

Слайд 31

Описание слайда:

Оптимизация вставки в АВЛ-дерево Для балансировки достаточно хранить разность высот левого и правого поддеревьев -1: Высота левого поддерева на 1 больше высоты правого поддерева 0: Высоты поддеревьев одинаковы +1: Высота правого поддерева на 1 больше высоты левого поддерева

Слайд 32

Описание слайда:

Одинарный поворот

Слайд 33

Описание слайда:

Двойной поворот

Слайд 34

Описание слайда:

Пример поворота

Слайд 35

Описание слайда:

Пример построения АВЛ-дерева

Слайд 36

Описание слайда:

Заключение Дерево, поддерево и др. определения Основные свойства Обходы деревьев В ширину, в глубину Представление деревьев Указатели, массив, скобочная запись, список прямых предков Дерево двоичного поиска АВЛ деревья