Содержание
- 2. Абстрактные структуры данных. Деревья. Дерево – связный граф, не содержащий циклов. Деревья: корневые и некорневые. Свойства
- 3. Абстрактные структуры данных. Деревья. Мат. модель корневого дерева – множество записей со следующими свойствами: 1. существует
- 4. Абстрактные структуры данных. Деревья. Позиционные деревья. Позиционное дерево – это либо пустое множество, либо дерево, которое
- 5. Абстрактные структуры данных. Деревья. Способы представления деревьев. Корневые деревья Общий случай: реализация с помощью списков. Вершина
- 6. Абстрактные структуры данных. Деревья. Способы представления деревьев. 4) Специальный способ организации позиционного дерева – с помощью
- 7. Абстрактные структуры данных. Деревья. Способы представления деревьев. Некорневые деревья Общий случай: с помощью списков смежности. Есть
- 8. Абстрактные структуры данных. Деревья. Способы представления деревьев. Некорневые деревья 2) Код Прюффера. Пусть вершины дерева пронумерованы
- 9. Абстрактные структуры данных. Деревья. Способы представления деревьев. Некорневые деревья 2) Восстановление дерева из кода Прюффера. Заводим
- 10. Абстрактные структуры данных. Деревья. Двоичные деревья поиска. Двоичное дерево поиска (ДДП) – это бинарное дерево такое,
- 11. Абстрактные структуры данных. Деревья. Двоичные деревья поиска. Операции в двоичном дереве поиска Поиск ключа FindKey(key) Найти
- 12. Абстрактные структуры данных. Операции в ДДП. Высотой дерева называется максимальная длина пути от корня дерева к
- 13. Абстрактные структуры данных. Операции в ДДП. FindNext(key)/ FindPrev(key) Выполняется операция FindKey(key). Пусть вершина А – результат
- 14. Абстрактные структуры данных. Операции в ДДП. Min()/Max() Ищется самый левый/правый лист в дереве. Модификация операции: FindMin(key)/FindMax(key)
- 15. Delete(key) Выполняется операция FindKey(key). Пусть вершина А – результат выполнения этой операции. Рассмотрим 3 случая: а.
- 16. Delete(key) в. А имеет 2 поддерева. осуществляем поиск FindNext(A); пусть это вершина В; вершина В не
- 17. Абстрактные структуры данных. Операции в ДДП. Выводы: Все интерфейсные операции имеют сложность O(h). Операции вставки и
- 18. Абстрактные структуры данных. Красно-черные деревья. Красно-черное дерево – это дерево двоичного поиска, у которого выполняются следующие
- 19. Абстрактные структуры данных. Красно-черные деревья. Примеры КЧ-деревьев Свойства сбалансированности КЧ-деревьев: для каждого узла высота левого и
- 20. Абстрактные структуры данных. Красно-черные деревья. Операция вращения ДДП Операция вращения выполняется за константное время и позволяет
- 21. Абстрактные структуры данных. Красно-черные деревья. Операция вставки в красно-черное дерево. Вставка элемента X как в обычное
- 22. Абстрактные структуры данных. Красно-черные деревья. Операция вставки в красно-черное дерево. а. красный «предок», красный «дядя» Перекрашиваем
- 24. Скачать презентацию