Презентация Деревья. Лекция 11, 12 онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему Деревья. Лекция 11, 12 абсолютно бесплатно. Урок-презентация на эту тему содержит всего 36 слайдов. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Оцените презентацию от 1 до 5 баллов!
- Тип файла:ppt / pptx (powerpoint)
- Всего слайдов:36 слайдов
- Для класса:1,2,3,4,5,6,7,8,9,10,11
- Размер файла:340.27 kB
- Просмотров:70
- Скачиваний:0
- Автор:неизвестен
Слайды и текст к этой презентации:
№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;
№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 (")");
}
№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.
Выход
истина, если aS
ложь иначе
логическая функция ПОИСК (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 слайд
Содержание слайда: Заключение
Дерево, поддерево и др. определения
Основные свойства
Обходы деревьев
В ширину, в глубину
Представление деревьев
Указатели, массив, скобочная запись, список прямых предков
Дерево двоичного поиска
АВЛ деревья
Скачать все slide презентации Деревья. Лекция 11, 12 одним архивом:
