Splay - дерево

    Splay-дерево является двоичным деревом поиска. Это дерево принадлежит классу «саморегулирующихся

ФПМИ БГУ

Splay-дерево было придумано Робертом Тарьяном и Даниелем Слейтером в 1983

ФПМИ БГУ

Splay-дерево позволяет находить быстрее те данные, которые использовались недавно. Для

ФПМИ БГУ

Move to Root

Cовершает повороты вокруг ребра (v, parent(v)), пока v

ФПМИ БГУ

Splay

Также совершает повороты, но чередует различные виды поворотов, благодаря чему

ФПМИ БГУ

При последовательном использовании операций "Move to Root" требуется 6 поворотов,

ФПМИ БГУ

Операции со Splay-деревом

ФПМИ БГУ

Splay

Делится на несколько случаев:

Zig (LL поворот, Правый разворот, Малое правое

ФПМИ БГУ

Zig (LL поворот, Правый разворот)

p

v

c

b

a

v

p

c

b

a

ФПМИ БГУ

Zag (RR поворот, Левый разворот)

v

p

c

b

a

p

v

c

b

a

ФПМИ БГУ

Zig-zig (Левый-левый случай, два разворота вправо)

p

v

c

b

a

v

p

b

a

g

d

p

v

b

a

g

d

c

g

d

c

ФПМИ БГУ

Zag-zag (Правый-правый случай, два разворота влево)

p

g

c

b

a

g

p

b

a

v

d

p

g

b

a

v

d

c

v

d

c

ФПМИ БГУ

Zig-zag (LR поворот, Большое правое вращение)

g

p

a

d

v

c

b

g

d

v

p

c

b

a

v

p

b

a

g

d

c

ФПМИ БГУ

Zag-zig (RL-поворот, Большое левое вращение)

v

g

b

a

p

d

c

g

p

v

d

c

b

a

g

v

b

a

p

d

c

ФПМИ БГУ

Данная операция занимает O(h) времени, где h — глубина вершины

ФПМИ БГУ

Search

Эта операция выполняется как для обычного бинарного дерева поиска, только

ФПМИ БГУ

Split

Процедура Split получает на вход ключ и делит дерево на

ФПМИ БГУ

Insert

Чтобы вставить очередной ключ, достаточно вызвать Split по нему, а

ФПМИ БГУ

Merge

У нас есть два дерева, причём подразумевается, что все элементы

ФПМИ БГУ

Remove

 Для того, чтобы удалить вершину, поднимем ее вверх, а потом

ФПМИ БГУ

Remove(продолжение)

 Для того, чтобы удалить вершину, поднимем ее вверх, а потом

ФПМИ БГУ

Чтобы Splay-дерево поддерживало повторяющиеся ключи, можно поступить двумя способами. Нужно

ФПМИ БГУ

Заметим, что процедуры удаления, вставки, слияния и разделения деревьев работают

ФПМИ БГУ

Амортизационный анализ Splay-дерева проводится с помощью метода потенциалов. Потенциалом рассматриваемого

ФПМИ БГУ

Доказательство

Рассмотрим идею доказательства. 
Если      , утверждение очевидно. В противном случае рассмотрим, как

ФПМИ БГУ

r

v

c

b

a

v'

r'

c

b

a

Zig(может выполняться только в конце)

Ранги меняются только у вершин v

ФПМИ БГУ

Zig-zig

Ранги меняются только у вершин v, p и g

Фактическое время

ФПМИ БГУ

Взглянув на диаграмму, заметим, что 

Тогда:

Что и требовалось доказать.

ФПМИ БГУ

Zig-zag

Ранги меняются только у вершин v, p и g

Фактическое время

ФПМИ БГУ

Таким образом мы разобрали все три случая и получили верхнюю

ФПМИ БГУ

Пусть —    число раз, которое был запрошен элемент . Тогда

ФПМИ БГУ

   Пусть —    это число запросов, которое мы уже совершили

ФПМИ БГУ

Исследование производительности и области применения Splay-деревьев оказалась темой для десятка

ФПМИ БГУ

Splay-деревья стали наиболее широко используемой базовой структурой данных, изобретенной за

ФПМИ БГУ

Главный недостаток заключается в том, что высота дерева всё-таки может

ФПМИ БГУ

  Код реализации Splay-дерева можно найти по ссылке:
https://github.com/magziim/DSA/blob/main/splay_tree.py