Splay-дерево

Сплей-дерево (англ. Splay-tree) — это двоичное дерево поиска. Оно позволяет находить быстрее те данные, которые использовались недавно. Относится к разряду сливаемых деревьев. Сплей-дерево было придумано Робертом Тарьяном и Даниелем Слейтером в $1983$ году.

Эвристики

Для того, чтобы доступ к недавно найденным данным был быстрее, надо, чтобы эти данные находились ближе к корню. Этого мы можем добиться, используя различные эвристики:

• Move to Root — совершает повороты вокруг ребра $(x, p)$, где $x$ — найденная вершина, $p$ — ее предок, пока $x$ не окажется корнем дерева. Однако можно построить такую последовательность операций, что амортизированное время доступа к вершине будет $\Omega(n)$.
• Splay — также совершает повороты, но чередует различные виды поворотов, благодаря чему достигается логарифмическая амортизированная оценка. Она будет подробно описана ниже.

Пример: При последовательном использовании операций "move to root" для вершин $A$ и $B$ требуется по $6$ поворотов, в то время как при использовании операции "splay" для вершины $B$ достаточно $3$ поворотов.

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

splay(tree, x)

"splay" делится на $3$ случая:

zig

Если $p$ — корень дерева с сыном $x$, то совершаем один поворот вокруг ребра $(x, p)$, делая $x$ корнем дерева. Данный случай является крайним и выполняется только один раз в конце, если изначальная глубина $x$ была нечетной.

zig-zig

Если $p$ — не корень дерева, а $x$ и $p$ — оба левые или оба правые дети, то делаем поворот ребра $(p, g)$, где $g$ отец $p$, а затем поворот ребра $(x, p)$.

zig-zag

Если $p$ — не корень дерева и $x$ — левый ребенок, а $p$ — правый, или наоборот, то делаем поворот вокруг ребра $(x, p)$, а затем поворот нового ребра $(x, g)$, где $g$ — бывший родитель $p$.

Данная операция занимает $O(d)$ времени, где $d$ — длина пути от $x$ до корня.

find(tree, x)

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

merge(tree1, tree2)

У нас есть два дерева $\mathtt{tree1}$ и $\mathtt{tree2}$, причём подразумевается, что все элементы первого дерева меньше элементов второго. Запускаем splay от самого большого элемента в дереве $\mathtt{tree1}$ (пусть это элемент $i$). После этого корень $\mathtt{tree1}$ содержит элемент $i$, при этом у него нет правого ребёнка. Делаем $\mathtt{tree2}$ правым поддеревом $i$ и возвращаем полученное дерево.

split(tree, x)

Запускаем splay от элемента $x$ и возвращаем два дерева, полученные отсечением правого или левого поддерева от корня, в зависимости от того, содержит корень элемент больше или не больше, чем $x$.

add(tree, x)

Запускаем split(tree, x), который нам возвращает деревья $\mathtt{tree1}$ и $\mathtt{tree2}$, их подвешиваем к $x$ как левое и правое поддеревья соответственно.

remove(tree, x)

Запускаем splay от $x$ элемента и возвращаем Merge от его детей.

Анализ операции splay

Амортизационный анализ сплей-дерева проводится с помощью метода потенциалов. Потенциалом рассматриваемого дерева назовём сумму рангов его вершин. Ранг вершины $x$ — это величина, обозначаемая $r(x)$ и равная $\log_2 C(x)$, где $C(x)$ — количество вершин в поддереве с корнем в $x$.

Лемма:

Амортизированное время операции splay вершины $x$ в дереве с корнем $t$ не превосходит $3r(t) - 3r(x) + 1$

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

$\triangleright$

Проанализируем каждый шаг операции splay. Пусть $r'$ и $r$ — ранги вершин после шага и до него соответственно, $p$ — предок вершины $x$, а $g$ — предок $p$ (если есть). Разберём случаи в зависимости от типа шага: zig. Поскольку выполнен один поворот, то амортизированное время выполнения шага $T = 1 + r'(x) + r'(p) - r(x) - r(p)$ (поскольку только у вершин $x$ и $p$ меняется ранг). Ранг вершины $p$ уменьшился, поэтому $T \leqslant 1 + r'(x) - r(x)$. Ранг вершины $x$ увеличился, поэтому $r'(x) - r(x) \geqslant 0$. Следовательно, $T \leqslant 1 + 3r'(x) - 3r(x)$. zig-zig. Выполнено два поворота, амортизированное время выполнения шага $T = 2 + r'(x) + r'(p) + r'(g) - r(p) - r(x) - r(g)$. Поскольку после поворотов поддерево с корнем в $x$ будет содержать все вершины, которые были в поддереве с корнем в $g$ (и только их), поэтому $r'(x) = r(g)$. Используя это равенство, получаем: $T = 2 + r'(p) + r'(g) - r(x) - r(p) \leqslant 2 + r'(p) + r'(g) - 2r(x)$, поскольку $r(x) \leqslant r(p)$. Далее, так как $r'(p) \leqslant r'(x)$, получаем, что $T \leqslant 2 + r'(x) + r'(g) - 2r(x)$. Мы утверждаем, что эта сумма не превосходит $3(r'(x) - r(x))$, то есть, что $r(x) + r'(g) - 2r'(x) \leqslant -2$. Преобразуем полученное выражение следующим образом: $(r(x) - r'(x)) + (r'(g) - r'(x)) = \log_2 \dfrac {C(x)}{C'(x)} + \log_2 \dfrac {C'(g)}{C'(x)}$. Из рисунка видно, что $C'(g) + C(x) \leqslant C'(x)$, значит, сумма выражений под логарифмами не превосходит единицы. Далее, рассмотрим сумму логарифмов $\log_2 a + \log_2 b = \log_2 ab$. При $a + b \leqslant 1$ произведение $ab$ по неравенству между средними не превышает $\dfrac{1}{4}$. А поскольку логарифм — функция возрастающая, то $\log_2 ab \leqslant -2$, что и является требуемым неравенством. zig-zag. Выполнено два поворота, амортизированное время выполнения шага $T = 2 + r'(x) + r'(p) + r'(g) - r(x) - r(p) - r(g)$. Поскольку $r'(x) = r(g)$, то $T = 2 + r'(p) + r'(g) - r(x) - r(p)$. Далее, так как $r(x) \leqslant r(p)$, то $T \leqslant 2 + r'(p) + r'(g) - 2r(x)$. Мы утверждаем, что эта сумма не превосходит $2(r'(x) - r(x))$, то есть, что $r'(p) + r'(g) - 2r'(x) \leqslant -2$. Но, поскольку $r'(p) + r'(g) - 2r'(x) = \log_2 \dfrac {C'(p)}{C'(x)} + \log_2 \dfrac {C'(g)}{C'(x)} \leqslant -2$ - аналогично доказанному ранее, что и требовалось доказать. Итого, получаем, что амортизированное время шага zig-zag не превосходит $2(r'(x) - r(x)) \leqslant 3(r'(x) - r(x))$. Поскольку за время выполнения операции splay выполняется не более одного шага типа zig, то суммарное время не будет превосходить $3r(t) - 3r(x) + 1$, поскольку утроенные ранги промежуточных вершин сокращаются (входят в сумму как с плюсом, так и с минусом). Тогда суммарное время работы splay $T_{splay} \leqslant 3\log_2 N - 3\log_2 C(x) + 1 = O(\log_2 N)$, где $N$ — число элементов в дереве.

$\triangleleft$

Статическая оптимальность сплей-дерева

Теорема:

Если к ключам $1 \ldots n$, сложенным в сплей-дерево выполняется $m$ запросов, к $i$-му ключу осуществляется $k_i$ запросов, где $k_i \gt 0$, то суммарное время работы не превышает $O(m \cdot H(p_1, p_2, \ldots , p_n))$, где $p_i = k_i / m$, $H$ — шенноновская энтропия

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

$\triangleright$

Известно, что $H(p_1, p_2, \ldots , p_n) = -c \cdot \displaystyle \sum_{i=1}^n (p_i \cdot \log_{2}p_i)$ — шенноновская энтропия. Пусть $s(x) = \displaystyle \sum_{y} w(y)$ — количество вершин в поддереве с корнем в $x$. А $r(x) = \log_{2} s(x)$ — ранг вершины. Обозначим за $r$ корень $splay$-дерева. Из предыдущей теоремы известно, что $a_{splay} \leqslant 1+3(r(r)-r(x))$ Пусть $w(x_i) = p_i =$ ${k_i \over m}$, тогда $k_i = p_i \cdot m$. $m+3mr(r)-3 \displaystyle \sum_{i=1}^n k_ir(x_i) \leqslant m+3mr(r)-3 \displaystyle \sum_{i+1}^n k_i\log_{2}w(x_i) =$ $m+3mr(r)-3 \displaystyle \sum_{i=1}^n (p_i\cdot m\cdot \log_{2}p_i) = m(1+3r(r)-3 \displaystyle \sum_{i=1}^n p_i\log_{2}p_i) = (*)$ Так как вершина $r$ — корень $splay$-дерева, то очевидно, что $s = \displaystyle \sum_{y} w(y) = 1$, следовательно $r(r) = \log_{2}s(r)=0$. Поэтому $(*) = m(1+H(p_1,\ldots ,p_n)) = O(mH(p_1,\ldots ,p_n))$, ч.т.д.

$\triangleleft$

Теорема о близких запросах в сплей-дереве

Теорема (о близких запросах в сплей-дереве):

Пусть в сплей-дерево сложены ключи $1, \dotsc, n$. Зафиксируем один из ключей $f$. Пусть выполняется $m$ запросов к ключам. Тогда суммарное время на запросы есть $\displaystyle O(n \log_{2} n + m + \sum_{i=1}^{m} \log_2 ( \lvert q_{i} - f \rvert + 1))$, где $q_{i}$ — значение в вершине, к которой обращаются в $i$-ый запрос.

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

$\triangleright$

Для доказательства теоремы воспользуемся методом потенциалов: $a_{i} = t_{i} + \Phi_{i} - \Phi_{i-1}$. По условию выполняется $m$ запросов, следовательно $T = \displaystyle \sum_{i=1}^{m} t_{i} = \sum_{i=1}^{m} \left (a_{i} + \Phi_{i-1} - \Phi_{i} \right) = \sum_{i=1}^{m} a_{i} + \sum_{i=1}^{m} \left ( \Phi_{i-1} - \Phi_{i} \right)$ $(\ast)$. Введем следующие обозначения: Весом узла с ключом $q$ будем называть величину $w(q) =\displaystyle \dfrac {1}{\left (\lvert q - f \rvert + 1 \right )^{2}}$. Размером узла, содержащего ключ $q$, будем называть величину $s(q) = \displaystyle \sum_{y} w(y)$, где $y$ — узлы поддерева с корнем в $q$. $r(q) = \log_{2}s(q)$ — ранг узла. Потенциал дерева после $i$-го запроса обозначим как $\Phi_{i} = \displaystyle \sum_{q=1}^{n} r(q) = \displaystyle \sum_{q=1}^{n} \log_{2}s(q)$. Пусть $W$ — вес дерева. Тогда $W = \displaystyle \sum_{q=1}^{n} w(q) = \sum_{q=1}^{n} \dfrac {1}{\left (\lvert q - f \rvert + 1 \right)^{2}} \leqslant 2 \cdot \sum_{q=1}^{+\infty} \dfrac {1}{ \left ( \lvert q - f \rvert + 1 \right)^{2}} = O(1)$. Последнее верно, так как при фиксированном $f$, начиная с некоторого места, а именно $q = f$, ряд сходится. Из определения размера узла следует, что $w(q) \leqslant s(q) \leqslant W$. Также заметим, что для любого $q$ от $1$ до $n$ верно, что $w(q) \geqslant \displaystyle \dfrac {1}{n^{2}}$, так как максимальное значение знаменателя в определении $w(q)$ достигается при $q = n$ и $f = 1$ или наоборот. Тогда, воспользовавшись полученными оценками, найдем изменение потенциала сплей-дерева после $m$ запросов: $\displaystyle \sum_{i=1}^{m} \left ( \Phi_{i-1} - \Phi_{i} \right) = \Phi_{0} - \Phi_{m} \leqslant \sum_{q=1}^{n} \log_{2} W - \sum_{q=1}^{n} \log_{2}w(q) = \sum_{q=1}^{n} \log_{2} \dfrac {W}{w(q)}$ $\displaystyle = O \Biggl(\sum_{q=1}^{n} \log_{2} n^{2}\Biggr) =$ $\displaystyle O\Biggl(2 \cdot\sum_{q=1}^{n} \log_{2} n\Biggr) = O\left (n \log_{2}n\right)$. Первое неравенство верно, так как максимальное значение потенциала достигается при $s(q) = W$, а минимальное при $s(q) = w(q)$, а значит изменение потенциала не превышает разности этих величин. Обозначим за $t$ корень сплей-дерева. Тогда, воспользовавшись вышеуказанной леммой (можно показать, что она верна для любого фиксированного определения веса узла) получаем, что $\displaystyle a_{i} = 3 \cdot \left ( r(t) - r(q_{i}) \right) + 1 = O\left (\log_{2} \dfrac {s(t)}{s\left (q_{i}\right)}\right) + 1 = O\left (\log_{2} \dfrac {W}{w(q_{i})}\right) + 1 =$ $O\left (\log_{2} \left (W \cdot \left (\lvert q_{i} - f \rvert + 1 \right)^{2} \right ) \right ) + 1 = O\left (\log_{2} \left (\lvert q_{i} - f \rvert + 1 \right) \right ) + 1$. Докажем, что данное определение потенциала удовлетворяет условию теоремы о методе потенциалов. Для любого $i$ верно, что $a_{i} = O(\log_{2}(n))$, так как $\lvert q_{i} - f \rvert + 1 \leqslant n$, и $\Phi_{i} = O(n\log_{2}(n))$, как было показано выше. Так как количество операций на запрос $k = O(n)$, то $a_{i} = O(f(k,n))$ и $\Phi_{i} = O(kf(k,n))$, где $f(k,n)$ — функция из теоремы о методе потенциалов, равная в данном случае $\log_{2}n$. Следовательно, потенциал удовлетворяет условию теоремы. Тогда, подставляя найденные значения в формулу $(\ast)$, получаем, что $T=\displaystyle \sum_{i=1}^{m} \left ( O \left ( \log_{2} \left ( \lvert q_{i} - f \rvert + 1 \right) \right) + 1 \right ) + O\left ( n \log_{2} n \right) =$ $\displaystyle O \left (n \log_{2} n + m + \displaystyle \sum_{i=1}^{m} \log_{2} \left ( \lvert q_{i} - f \rvert + 1 \right) \right)$.

$\triangleleft$

Данная теорема показывает, что сплей-деревья поддерживают достаточно эффективный доступ к ключам, которые находятся близко к какому-то фиксированному ключу.

Splay-деревья по неявному ключу

Splay-дерево по неявному ключу полностью аналогично декартову дереву по неявному ключу, неявным ключом также будет количество элементов дерева, меньших данного. Аналогично, будем хранить вспомогательную величину $C(x)$ — количество вершин в поддереве. К операциям, которые уже были представлены в декартовом дереве, добавляется splay, но пересчет $C(x)$ в ней тривиален, так как мы точно знаем, куда перемещаются изменяемые поддеревья.

См. также

• 2-3 дерево
• B-дерево
• B+-дерево
• АВЛ-дерево
• Красно-черное дерево

Источники информации

• Википедия — Splay tree
• Sleator, Daniel D.; Tarjan, Robert E."Self-Adjusting Binary Search Trees"