Похожие презентации:
Splay tree (Косое или Расширяющееся дерево)
1. Сибирский государственный университет телекоммуникаций и информатики КУРСОВОЙ ПРОЕКТ по дисциплине “Структуры и алгоритмы обработки да
Сибирский государственный университеттелекоммуникаций и информатики
КУРСОВОЙ ПРОЕКТ
по дисциплине
“Структуры и алгоритмы обработки данных”
2. Splay Tree
Splay tree (Косое или Расширяющееся дерево) –это самобалансирующееся бинарное дерево
поиска.
При любом обращении дерево меняет свою
структуру.
3. Операции над деревом
Добавление элемента х в дерево Т:1) Создать узел и добавить его в дерево по правилам BST(Бинарное
Дерево Поиска).
2) Запустить процедуру Splay для узла х для изменения структуры
дерева, поднимая элемент х в корень дерева.
4. Операции над деревом
Поиск элемента х в дереве Т:1) Поиск элемента х по правилам BST.
2) К найденному узлу х применить процедуру Splay.
5. Операции над деревом
Удаление узла х из дерева Т:1) С помощью метода Find() находим удаляемый узел.
2) Обрезаем два дочерних поддерева узла х.
3) При помощи метода merge() сливаем получившиеся деревья.
6.
Операции над деревомСлияние двух splay tree:
1) Находим узел с максимальным ключом в дереве с узлами имеющими
меньшие ключи.
2) Применяем процедуру Splay к найденному узлу.
3) Найденному узлу правым дочерним узлом делаем корень второго
дерева.
7.
Операции над деревомПроцедура Splay:
Поднимает узел х в корень дерева с помощью поворотов.
Всего 6 случаев(3 основных и 3 им симметричных):
1) 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