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