TREE
Бзаров Евгений Константинович
Студент группы ИУ-423
Новосибирск 2015
- Главная
- Разное
- Дизайн
- Бизнес и предпринимательство
- Аналитика
- Образование
- Развлечения
- Красота и здоровье
- Финансы
- Государство
- Путешествия
- Спорт
- Недвижимость
- Армия
- Графика
- Культурология
- Еда и кулинария
- Лингвистика
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Детские презентации
- Информатика
- История
- Литература
- Маркетинг
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Splay tree (Косое или Расширяющееся дерево) презентация
Содержание
- 1. Splay tree (Косое или Расширяющееся дерево)
- 2. Splay Tree Splay tree (Косое или Расширяющееся
- 3. Операции над деревом Добавление элемента х в
- 4. Операции над деревом Поиск элемента х в
- 5. Операции над деревом Удаление узла х из
- 6. Слияние двух splay tree: Находим узел с
- 7. Процедура Splay: Поднимает узел х в корень
- 8. Операции над деревом 2) Zig-Zig (один
- 9. Операции над деревом 3) Zig-Zag (один
- 10. Литература: 1) SleatorD., TarjanR.Self-Adjusting
Splay Tree Splay tree (Косое или Расширяющееся дерево) – это самобалансирующееся бинарное дерево поиска. При любом обращении дерево меняет свою структуру.
Слайд 1Сибирский государственный университет
телекоммуникаций и информатики
КУРСОВОЙ ПРОЕКТ
по дисциплине
“Структуры и алгоритмы обработки данных”
SPLAY
Слайд 2Splay Tree
Splay tree (Косое или Расширяющееся дерево) – это самобалансирующееся бинарное
дерево поиска.
При любом обращении дерево меняет свою структуру.
При любом обращении дерево меняет свою структуру.
Слайд 3Операции над деревом
Добавление элемента х в дерево Т:
Создать узел и добавить
его в дерево по правилам BST(Бинарное Дерево Поиска).
Запустить процедуру Splay для узла х для изменения структуры дерева, поднимая элемент х в корень дерева.
Запустить процедуру Splay для узла х для изменения структуры дерева, поднимая элемент х в корень дерева.
Слайд 4Операции над деревом
Поиск элемента х в дереве Т:
Поиск элемента х по
правилам BST.
К найденному узлу х применить процедуру Splay.
К найденному узлу х применить процедуру Splay.
Слайд 5Операции над деревом
Удаление узла х из дерева Т:
С помощью метода Find()
находим удаляемый узел.
Обрезаем два дочерних поддерева узла х.
При помощи метода merge() сливаем получившиеся деревья.
Обрезаем два дочерних поддерева узла х.
При помощи метода merge() сливаем получившиеся деревья.
Слайд 6Слияние двух splay tree:
Находим узел с максимальным ключом в дереве с
узлами имеющими меньшие ключи.
Применяем процедуру Splay к найденному узлу.
Найденному узлу правым дочерним узлом делаем корень второго дерева.
Применяем процедуру Splay к найденному узлу.
Найденному узлу правым дочерним узлом делаем корень второго дерева.
Операции над деревом
Слайд 7Процедура Splay:
Поднимает узел х в корень дерева с помощью поворотов.
Всего 6
случаев(3 основных и 3 им симметричных):
Zig (один поворот относительно родителя узла х)
Zig (один поворот относительно родителя узла х)
Операции над деревом
Слайд 8Операции над деревом
2) Zig-Zig (один поворот относительно деда узла х,
один поворот относительно родителя узла х)
Слайд 9Операции над деревом
3) Zig-Zag (один поворот относительно родителя узла х
влево, один поворот относительно родителя узла х вправо)
Слайд 10 Литература:
1) SleatorD., TarjanR.Self-Adjusting Binary Search Trees //Journal of the
ACM. 1985. Vol. 32 (3). P. 652–686
