Раскидистое дерево

Саморегулирующееся двоичное дерево поиска

Раскрывающееся дерево — это бинарное дерево поиска с дополнительным свойством, что недавно использованные элементы быстро доступны снова. Подобно самобалансирующимся бинарным деревьям поиска , раскрывающееся дерево выполняет основные операции, такие как вставка, поиск и удаление за O (log n ) амортизированного времени. Для шаблонов случайного доступа, взятых из неравномерного случайного распределения, их амортизированное время может быть быстрее логарифмического, пропорционального энтропии шаблона доступа. Для многих шаблонов неслучайных операций, также, раскрывающиеся деревья могут занимать лучшее, чем логарифмическое время, не требуя предварительного знания шаблона. Согласно недоказанной гипотезе динамической оптимальности, их производительность для всех шаблонов доступа находится в пределах постоянного множителя наилучшей возможной производительности, которая может быть достигнута любым другим самонастраивающимся бинарным деревом поиска, даже выбранным для соответствия этому шаблону. Раскрывающееся дерево было изобретено Дэниелом Слейтором и Робертом Тарьяном в 1985 году. ^[1]

Все обычные операции на бинарном дереве поиска объединены с одной базовой операцией, называемой splaying . Растягивание дерева для определенного элемента перестраивает дерево так, что элемент помещается в корень дерева. Один из способов сделать это с помощью базовой операции поиска — сначала выполнить стандартный поиск в бинарном дереве для нужного элемента, а затем использовать повороты дерева определенным образом, чтобы переместить элемент наверх. В качестве альтернативы, алгоритм сверху вниз может объединить поиск и реорганизацию дерева в одну фазу.

Преимущества

Хорошая производительность для раскидистого дерева зависит от того, что оно является самооптимизирующимся, в том смысле, что часто используемые узлы будут перемещаться ближе к корню, где к ним можно будет получить доступ быстрее. Худшая высота — хотя и маловероятная — составляет O( n ), а средняя — O(log n ). Наличие часто используемых узлов вблизи корня является преимуществом для многих практических приложений (см. также локальность ссылок ), и особенно полезно для реализации кэшей и алгоритмов сборки мусора .

Преимущества включают в себя:

• Сопоставимая производительность: в среднем производительность такая же эффективная, как и у других деревьев. ^[3]
• Малый объем памяти : разветвленные деревья не требуют хранения каких-либо бухгалтерских данных.

Недостатки

Самым существенным недостатком разветвленных деревьев является то, что высота разветвленного дерева может быть линейной. ^{[2] : 1} Например, это будет иметь место после доступа ко всем n элементам в неубывающем порядке. Поскольку высота дерева соответствует наихудшему времени доступа, это означает, что фактическая стоимость одной операции может быть высокой. Однако амортизированная стоимость доступа в этом наихудшем случае логарифмическая, O(log n ). Кроме того, ожидаемая стоимость доступа может быть снижена до O(log n ) с помощью рандомизированного варианта. ^[4]

Представление расширяющихся деревьев может меняться, даже если к ним осуществляется доступ «только для чтения» (т. е. с помощью операций поиска ). Это усложняет использование таких расширяющихся деревьев в многопоточной среде. В частности, требуется дополнительное управление, если нескольким потокам разрешено выполнять операции поиска одновременно. Это также делает их непригодными для общего использования в чисто функциональном программировании, хотя даже там их можно использовать ограниченными способами для реализации приоритетных очередей.

Наконец, когда модель доступа случайна , дополнительные накладные расходы на расширение добавляют значительный постоянный фактор к стоимости по сравнению с менее динамичными альтернативами.

Операции

Расползание

При доступе к узлу x выполняется операция splay для перемещения x в корень. Операция splay представляет собой последовательность шагов splay , каждый из которых перемещает x ближе к корню. Выполняя операцию splay на интересующем узле после каждого доступа, недавно использованные узлы сохраняются около корня, и дерево остается примерно сбалансированным, поэтому оно обеспечивает желаемые амортизированные временные границы.

Каждый конкретный шаг зависит от трех факторов:

• Является ли x левым или правым потомком своего родительского узла p ,
• является ли p корнем или нет, и если нет
• является ли p левым или правым потомком своего родителя g ( прародителем x ) .

Существует три типа ступеней расширения, каждый из которых имеет два симметричных варианта: левосторонний и правосторонний. Для краткости для каждого типа показан только один из этих двух вариантов. (На следующих диаграммах кружки обозначают интересующие узлы, а треугольники обозначают поддеревья произвольного размера.) Три типа ступеней расширения:

Шаг Zig: этот шаг выполняется, когда p является корнем. Дерево поворачивается на ребре между x и p . Шаги Zig существуют для решения проблемы четности, будут выполняться только как последний шаг в операции расширения и только когда x имеет нечетную глубину в начале операции.

Шаг зигзагообразный: этот шаг выполняется, когда p не является корнем, а x и p являются либо правыми потомками, либо левыми потомками. На рисунке ниже показан случай, когда x и p являются левыми потомками. Дерево поворачивается на ребре, соединяющем p с его родителем g , затем поворачивается на ребре, соединяющем x с p . Шаги зигзагообразный — единственное, что отличает расходящиеся деревья от метода поворота к корню, введенного Алленом и Манро ^[5] до введения расходящихся деревьев.

Шаг зигзага: этот шаг выполняется, когда p не является корнем, а x является правым потомком, а p является левым потомком или наоборот ( x является левым, p является правым). Дерево поворачивается на ребре между p и x , а затем поворачивается на результирующем ребре между x и g .

Присоединиться

Если даны два дерева S и T, такие, что все элементы S меньше элементов T, то для их объединения в одно дерево можно использовать следующие шаги:

• Расширить самый большой элемент в S. Теперь этот элемент находится в корне S и имеет нулевой правый потомок.
• Установите правого потомка нового корня на T.

Расколоть

Дано дерево и элемент x , вернуть два новых дерева: одно, содержащее все элементы, меньшие или равные x , и другое, содержащее все элементы, большие x . Это можно сделать следующим образом:

• Растянуть x . Теперь он находится в корне, поэтому дерево слева от него содержит все элементы, меньшие x , а дерево справа содержит все элементы, большие x .
• Отделите правое поддерево от остальной части дерева.

Вставка

Чтобы вставить значение x в расширяющееся дерево:

• Вставьте x как в обычном двоичном дереве поиска .
• Выполнить расширение по x .

В результате вновь вставленный узел x становится корнем дерева.

Альтернативно:

• Используйте операцию разделения, чтобы разбить дерево по значению x на два поддерева: S и T.
• Создайте новое дерево, в котором x — корень, S — его левое поддерево, а T — его правое поддерево.

Удаление

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

• Если у x двое детей:
  • Поменяйте его значение со значением либо самого правого узла его левого поддерева (его предшественника по порядку), либо самого левого узла его правого поддерева (его преемника по порядку).
  • Вместо этого удалите этот узел.

Таким образом, удаление сводится к проблеме удаления узла с 0 или 1 потомком. В отличие от бинарного дерева поиска, в расширяющемся дереве после удаления мы расширяем родительский узел удаленного узла на вершину дерева.

Альтернативно:

• Удаляемый узел сначала расширяется, т.е. переносится в корень дерева, а затем удаляется. В результате дерево остается с двумя поддеревьями.
• Затем два поддерева объединяются с помощью операции «соединения».

Реализация и варианты

Растягивание, как упоминалось выше, выполняется во время второго прохода снизу вверх по пути доступа узла. Можно записать путь доступа во время первого прохода для использования во время второго, но это требует дополнительного места во время операции доступа. Другой альтернативой является сохранение родительского указателя в каждом узле, что позволяет избежать необходимости в дополнительном месте во время операций доступа, но может снизить общую эффективность времени из-за необходимости обновления этих указателей. ^[1]

Другой метод, который можно использовать, основан на аргументе, что дерево может быть реструктурировано во время пути вниз по пути доступа вместо того, чтобы делать второй проход. Эта процедура расширения сверху вниз использует три набора узлов — левое дерево, правое дерево и среднее дерево. Первые два содержат все элементы исходного дерева, которые, как известно, меньше или больше текущего элемента соответственно. Среднее дерево состоит из поддерева с корнем в текущем узле. Эти три набора обновляются вниз по пути доступа, при этом операции расширения контролируются. Другой метод, полурасширение, изменяет случай зигзага, чтобы уменьшить количество реструктуризаций, выполняемых во всех операциях. ^{[1] [6]}

Ниже представлена ​​реализация расширяющихся деревьев на языке C++, которая использует указатели для представления каждого узла дерева. Эта реализация основана на версии расширяющегося снизу вверх и использует второй метод удаления в расширяющемся дереве. Также, в отличие от определения выше, эта версия C++ не расширяет дерево при поиске — она расширяет только при вставках и удалениях, и операция поиска, таким образом, имеет линейную временную сложность.

#include <функциональный> #ifndef SPLAY_TREE #define SPLAY_TREEtemplate < typename T , typename Comp = std :: less < T >> class splay_tree { private : Comp comp ; unsigned long p_size ; struct node { node * left , * right ; node * parent ; T key ; node ( const T & init = T ()) : left ( nullptr ), right ( nullptr ), parent ( nullptr ), key ( init ) { } ~ node () {                                      } } * root ; void left_rotate ( узел * x ) { узел * y = x -> вправо ; если ( y ) { x -> вправо = y -> влево ; если ( y -> влево ) y -> влево -> родитель = x ; y -> родитель = x -> родитель ; } если ( ! x -> родитель ) корень = y ; иначе если ( x == x -> родитель -> влево ) x -> родитель -> влево = y ; иначе x -> родитель -> вправо = y ; если ( y ) y -> влево = x ; x -> родитель = y ; } void right_rotate ( узел * x ) { узел * y = x -> влево ; если ( y ) { x -> влево = y -> вправо ; если ( y -> вправо ) y -> вправо -> родитель = x ; y -> родитель = x -> родитель ; } если ( ! x -> родитель ) корень = y ; иначе если ( x == x -> родитель -> левый ) x -> родитель -> левый = y ; иначе x ->                                                                                            родитель -> справа = y ; если ( y ) y -> справа = x ; x -> родитель = y ; } void splay ( узел * x ) { while ( x -> родитель ) { if ( !x -> родитель -> родитель ) { if ( x -> родитель -> влево == x ) поворот_вправо ( x -> родитель ); else поворот_влево ( x -> родитель ); } else if ( x -> родитель -> влево == x && x -> родитель -> родитель -> влево == x -> родитель ) { поворот_вправо ( x -> родитель -> родитель ); поворот_вправо ( x -> родитель ); } else if ( x -> родитель -> вправо == x && x -> родитель -> родитель -> вправо == x -> родитель ) { поворот_влево ( x -> родитель -> родитель ); поворот_влево ( x -> родитель ); } else if ( x -> родитель -> влево == x && x -> родитель -> родитель -> вправо == x -> родитель ) { поворот_вправо ( x -> родитель ); поворот_влево ( x -> родитель ); } else {                                                                        left_rotate ( x -> parent ); right_rotate ( x -> parent ); } } } void replace ( node * u , node * v ) { if ( ! u -> parent ) root = v ; else if ( u == u -> parent -> left ) u -> parent -> left = v ; else u -> parent -> right = v ; if ( v ) v -> parent = u -> parent ; } node * subtree_minimum ( node * u ) { while ( u -> left ) u = u -> left ; return u ; } node * subtree_maximum ( node * u ) { while ( u -> right ) u = u -> right ; return u ; } public : splay_tree () : root ( nullptr ), p_size ( 0 ) { } void insert ( const T & key ) { node * z = root ; узел * p = nullptr ; while ( z ) { p = z ; if ( comp ( z -> key , key )) z = z -> right ; else z = z ->                                                                                                 left ; } z = new node ( key ); z -> parent = p ; if ( ! p ) root = z ; else if ( comp ( p -> key , z -> key )) p -> right = z ; else p -> left = z ; splay ( z ); p_size ++ ; } node * find ( const T & key ) { node * z = root ; while ( z ) { if ( comp ( z -> key , key )) z = z -> right ; else if ( comp ( key , z -> key )) z = z -> left ; else return z ; } return nullptr ; } void erasure ( const T & key ) { node * z = find ( key ); if ( ! z ) return ; splay ( z ); if ( ! z -> left ) replace ( z , z -> right ); else if ( ! z -> right ) replace ( z , z -> left ); иначе { узел * y = subtree_minimum ( z -> right ); если ( y ->                                                                                                родитель != z ) { заменить ( y , y -> вправо ); y -> вправо = z -> вправо ; y -> вправо -> родитель = y ; } заменить ( z , y ); y -> влево = z -> влево ; y -> влево -> родитель = y ; } удалить z ; p_size -- ; }                          /* //альтернативная реализация  void erasure(const T &key) {  node *z = find(key);  if (!z) return;  splay(z);  node *s = z->left;  node *t = z->right;  delete z;  node *sMax = NULL;  if (s) {  s->parent = NULL;  sMax = subtree_maximum(s);  splay(sMax);  root = sMax;  }  if (t) {  if (s)  sMax->right = t;  else  root = t;  t->parent = sMax;  }  p_size--;  } */ const T & minimum () { return subtree_minimum ( root ) -> key ; } const T & maximum () { return subtree_maximum ( root ) -> key ; } bool empty () const { return root == nullptr ; } unsigned long size () const { return p_size ; } };                                     #endif // ДЕРЕВО_ВОСПРОИЗВЕДЕНИЯ

Анализ

Простой амортизационный анализ статических раскидистых деревьев можно выполнить с использованием метода потенциала . Определим:

• размер( r ) = количество узлов в поддереве с корнем в узле r (включая r ).
• ранг( r ) = log ₂ (размер( r )).
• Φ = сумма рангов всех узлов дерева.

Значение Φ будет, как правило, высоким для плохо сбалансированных деревьев и низким для хорошо сбалансированных деревьев.

Чтобы применить метод потенциала , мы сначала вычисляем ΔΦ: изменение потенциала, вызванное операцией расширения. Мы проверяем каждый случай отдельно. Обозначим через rank' функцию ранга после операции. x, p и g — узлы, затронутые операцией вращения (см. рисунки выше).

Зиг-шаг

Зиг-зиг шаг

Зигзагообразный шаг

Амортизированная стоимость любой операции равна ΔΦ плюс фактическая стоимость. Фактическая стоимость любой операции зигзаг или зигзаг равна 2, поскольку необходимо сделать два поворота. Следовательно:

При суммировании по всей операции расширения это сжимается до 1 + 3(rank(root)−rank( x )), что составляет O(log n ), поскольку мы используем операцию Zig не более одного раза, а амортизированная стоимость zig не превышает 1+3(rank'( x )−rank( x )).

Итак, теперь мы знаем, что общее амортизированное время для последовательности из m операций составляет:

${\displaystyle T_{\mathrm {amortized} }(m)=O(m\log n)}$

Чтобы перейти от амортизированного времени к фактическому времени, мы должны прибавить уменьшение потенциала от начального состояния до выполнения любой операции (Φ _i ) до конечного состояния после завершения всех операций (Φ _f ).

${\displaystyle \Phi _{i}-\Phi _{f}=\sum _{x}{\mathrm {rank} _{i}(x)-\mathrm {rank} _{f}(x)}=O(n\log n)}$

где обозначение O большое может быть оправдано тем фактом, что для каждого узла x минимальный ранг равен 0, а максимальный ранг равен log( n ).

Теперь мы наконец можем ограничить фактическое время:

${\displaystyle T_{\mathrm {actual} }(m)=O(m\log n+n\log n)}$

Взвешенный анализ

Приведенный выше анализ можно обобщить следующим образом.

• Назначим каждому узлу r вес w ( r ).
• Определим размер ( r ) = сумму весов узлов в поддереве с корнем в узле r (включая r ).
• Определим rank( r ) и Φ точно так же, как и выше.

Применяется тот же анализ, и амортизированная стоимость операции по распрямлению снова составляет:

${\displaystyle 1+3(\mathrm {rank} (root)-\mathrm {rank} (x))}$

где W — сумма всех весов.

Уменьшение от начального до конечного потенциала ограничено:

${\displaystyle \Phi _{i}-\Phi _{f}\leq \sum _{x\in tree}{\log {\frac {W}{w(x)}}}}$

поскольку максимальный размер любого отдельного узла равен W , а минимальный равен w(x) .

Следовательно, фактическое время ограничено:

${\displaystyle O\left(\sum _{x\in sequence}{\left(1+3\log {\frac {W}{w(x)}}\right)}+\sum _{x\in tree}{\log {\frac {W}{w(x)}}}\right)=O\left(m+\sum _{x\in sequence}{\log {\frac {W}{w(x)}}}+\sum _{x\in tree}{\log {\frac {W}{w(x)}}}\right)}$

Теоремы производительности

Существует несколько теорем и гипотез относительно наихудшего времени выполнения последовательности S из m обращений в развернутом дереве, содержащем n элементов.

Теорема баланса  —  стоимость выполнения последовательности S составляет . ${\displaystyle O\left[m\log n+n\log n\right]}$

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

Возьмем постоянный вес, например ⁠ ⁠ ${\displaystyle w(x)=1}$ для каждого узла x . Тогда ⁠ ⁠ ${\displaystyle W=n}$ .

Эта теорема подразумевает, что развернутые деревья работают так же хорошо, как статически сбалансированные двоичные деревья поиска на последовательностях из не менее n обращений. ^[1]

Теорема статической оптимальности  —  Пусть будет числом раз, которое элемент x доступен в S. Если каждый элемент доступен по крайней мере один раз, то стоимость выполнения S равна ${\displaystyle q_{x}}$ ${\displaystyle O\left[m+\sum _{x\in tree}q_{x}\log {\frac {m}{q_{x}}}\right]}$

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

Пусть . Тогда . ${\displaystyle w(x)=q_{x}}$ ${\displaystyle W=m}$

Эта теорема подразумевает, что разветвленные деревья работают так же хорошо, как и оптимальное статическое двоичное дерево поиска на последовательностях из не менее n обращений. ^[7] Они тратят меньше времени на более частые элементы. ^[1] Другой способ сформулировать тот же результат заключается в том, что на входных последовательностях, где элементы выбираются независимо случайным образом из неравномерного распределения вероятностей по n элементам, амортизированная ожидаемая ( средняя ) стоимость каждого доступа пропорциональна энтропии распределения. ^[8]

Теорема статического пальца  —  Предположим, что элементы пронумерованы от 1 до n в порядке возрастания. Пусть f — любой фиксированный элемент («палец»). Тогда стоимость выполнения S составляет . ${\displaystyle O\left[m+n\log n+\sum _{x\in sequence}\log(|x-f|+1)\right]}$

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

Пусть . Тогда ⁠ ⁠ . Чистое падение потенциала равно O ( n log n ), поскольку вес любого предмета составляет не менее ⁠ ⁠ . ^[1] ${\displaystyle w(x)=1/(|x-f|+1)^{2}}$ ${\displaystyle W=O(1)}$ ${\displaystyle 1/n^{2}}$

Теорема динамического пальца  —  Предположим, что «палец» для каждого шага, получающего доступ к элементу y, — это элемент, к которому обращались на предыдущем шаге, x . Стоимость выполнения S составляет . ^{[9] [10]} ${\displaystyle O\left[m+n+\sum _{x,y\in sequence}^{m}\log(|y-x|+1)\right]}$

Теорема рабочего множества  —  В любой момент последовательности пусть будет числом различных элементов, к которым был получен доступ до предыдущего времени доступа к элементу x. Стоимость выполнения S равна ${\displaystyle t(x)}$ ${\displaystyle O\left[m+n\log n+\sum _{x\in sequence}\log(t(x)+1)\right]}$

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

Пусть . Обратите внимание, что здесь веса изменяются в ходе последовательности. Однако последовательность весов по-прежнему является перестановкой ⁠ ⁠ . Так что, как и прежде ⁠ ⁠ . Чистое падение потенциала равно O ( n log n ). ${\displaystyle w(x)=1/(t(x)+1)^{2}}$ ${\displaystyle 1,{\tfrac {1}{4}},{\tfrac {1}{9}},\cdots ,{\tfrac {1}{n^{2}}}}$ ${\displaystyle W=O(1)}$

Эта теорема эквивалентна разветвленным деревьям, имеющим независимую от ключа оптимальность . ^[1]

Теорема сканирования  —  также известная как теорема последовательного доступа или теорема очереди . Доступ к n элементам расширяющегося дерева в симметричном порядке занимает O ( n ) времени, независимо от начальной структуры расширяющегося дерева. ^[11] Самая точная верхняя граница, доказанная на данный момент, — . ^[12] ${\displaystyle 4.5n}$

Гипотеза динамической оптимальности

Нерешенная проблема в информатике :

Являются ли алгоритмы расширенного дерева такими же эффективными, как и любые другие алгоритмы двоичного дерева поиска?

(еще нерешенные проблемы в информатике)

В дополнение к доказанным гарантиям производительности для раскидистых деревьев существует недоказанная гипотеза, представляющая большой интерес, из оригинальной статьи Слейтора и Тарьяна. Эта гипотеза известна как гипотеза динамической оптимальности , и она в основном утверждает, что раскидистые деревья работают так же хорошо, как и любой другой алгоритм бинарного дерева поиска с точностью до постоянного множителя.

Гипотеза динамической оптимальности: ^[1] Пусть будет любым алгоритмом бинарного дерева поиска, который получает доступ к элементу , проходя путь от корня до со стоимостью , и который между доступами может выполнять любые повороты в дереве со стоимостью 1 за поворот. Пусть будет стоимостью для выполнения последовательности доступов. Тогда стоимость для splay tree для выполнения тех же доступов будет . ${\displaystyle A}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle d(x)+1}$ ${\displaystyle A(S)}$ ${\displaystyle A}$ ${\displaystyle S}$ ${\displaystyle O[n+A(S)]}$

Существует несколько следствий гипотезы динамической оптимальности, которые остаются недоказанными:

Гипотеза обхода: ^[1] Пусть и будут двумя расправленными деревьями, содержащими одни и те же элементы. Пусть будет последовательностью, полученной путем посещения элементов в в прямом порядке (т.е. в порядке поиска в глубину). Общая стоимость выполнения последовательности доступов к составляет . ${\displaystyle T_{1}}$ ${\displaystyle T_{2}}$ ${\displaystyle S}$ ${\displaystyle T_{2}}$ ${\displaystyle S}$ ${\displaystyle T_{1}}$ ${\displaystyle O(n)}$

Гипотеза о деке: ^{[11] [13] [14]} Пусть — последовательность операций с двухсторонней очередью (push, pop, inject, eject). Тогда стоимость выполнения на развернутом дереве равна . ${\displaystyle S}$ ${\displaystyle m}$ ${\displaystyle S}$ ${\displaystyle O(m+n)}$

Гипотеза о расщеплении: ^[6] Пусть — любая перестановка элементов разветвленного дерева. Тогда стоимость удаления элементов в порядке равна . ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle O(n)}$

Варианты

Чтобы сократить количество операций реструктуризации, можно заменить расширение полурасширением , при котором элемент расширяется только наполовину по направлению к корню. ^{[1] [2]}

Другой способ уменьшить реструктуризацию — выполнить полное расширение, но только в некоторых операциях доступа — только когда путь доступа длиннее порогового значения или только в первых m операциях доступа. ^[1]

CBTree дополняет splay tree счетчиками доступа в каждом узле и использует их для нечастой реструктуризации. Вариант CBTree, называемый LazyCBTree, делает максимум один оборот при каждом поиске. Это используется вместе с оптимистической схемой проверки hand-over-hand для создания параллельного самонастраивающегося дерева. ^[15]

Используя методы сжатия указателей ^[16], можно построить краткое расширяющееся дерево.

Смотрите также

• Дерево АВЛ
• B-дерево
• Дерево пальцев
• Геометрия двоичных деревьев поиска
• Структура рабочего набора Иаконо
• Ссылка/вырезка дерева
• Список структур данных
• Дерево козла отпущения
• Splaysort — алгоритм сортировки с использованием расширяющихся деревьев.
• Т-дерево
• Треп
• Ротация деревьев
• Деревья
• Молния (структура данных)

Примечания

1. Слеатор и Тарьян 1985.
2. Бринкманн, Деграер и Де Луф 2009.
3. Гудрич, Тамассиа и Голдвассер 2014.
4. Альберс и Карпински 2002.
5. Аллен и Манро 1978.
6. Лукас 1991.
7. Кнут 1997, стр. 478
8. Гринберг и др. (1995).
9. Коул и др. 2000.
10. Коул 2000.
11. Tarjan 1985.
12. Элмасри 2004.
13. Петти 2008.
14. Сундар 1992.
15. Афек и др. 2014
16. Бендер и др. 2023.

Ссылки

• Афек, Йехуда; Каплан, Хаим; Коренфельд, Борис; Моррисон, Адам; Тарьян, Роберт Э. (2014). «Дерево CB: практическое параллельное самонастраивающееся дерево поиска». Распределенные вычисления . 27 (6): 393–417. doi :10.1007/s00446-014-0229-0.
• Альберс, Сюзанна; Карпински, Марек (28 февраля 2002 г.). «Рандомизированные расходящиеся деревья: теоретические и экспериментальные результаты» (PDF) . Information Processing Letters . 81 (4): 213–221. doi :10.1016/s0020-0190(01)00230-7.
• Аллен, Брайан; Манро, Ян (октябрь 1978 г.). «Самоорганизующиеся бинарные деревья поиска». Журнал ACM . 25 (4): 526–535. doi : 10.1145/322092.322094 . S2CID  15967344.
• Brinkmann, Gunnar; Degraer, Jan; De Loof, Karel (январь 2009 г.). "Реабилитация нелюбимого ребенка: полураспластывание" (PDF) . Software: Practice and Experience . 39 (1): 33–45. CiteSeerX  10.1.1.84.790 . doi :10.1002/spe.v39:1. hdl :11382/102133. Результаты показывают, что полураспластывание, которое было введено в той же статье, что и распластывание, работает лучше, чем распластывание практически при всех возможных условиях. Это делает полураспластывание хорошей альтернативой для всех приложений, где обычно применяется распластывание. Причина, по которой распластывание стало настолько заметным, в то время как полураспластывание относительно неизвестно и изучено гораздо меньше, трудно понять.
• Коул, Ричард; Мишра, Бад; Шмидт, Жанетт; Сигел, Алан (январь 2000 г.). «О динамической гипотезе пальца для разветвленных деревьев. Часть I: разветвленная сортировка последовательностей log n-Block». SIAM Journal on Computing . 30 (1): 1–43. CiteSeerX  10.1.1.36.4558 . doi :10.1137/s0097539797326988.
• Коул, Ричард (январь 2000 г.). «О гипотезе динамического пальца для распластанных деревьев. Часть II: Доказательство». SIAM Journal on Computing . 30 (1): 44–85. CiteSeerX  10.1.1.36.2713 . doi :10.1137/S009753979732699X.
• Элмасри, Амр (апрель 2004 г.). «О теореме последовательного доступа и гипотезе Дека для распластанных деревьев». Теоретическая информатика . 314 (3): 459–466. doi :10.1016/j.tcs.2004.01.019.
• Гудрич, Майкл; Тамассиа, Роберто; Голдвассер, Майкл (2014). Структуры данных и алгоритмы в Java (6-е изд.). Wiley. стр. 506. ISBN 978-1-118-77133-4.
• Гринберг, Деннис; Раджагопалан, Сиварамакришнан; Венкатесан, Рамаратнам; Вэй, Виктор К. (1995). «Расширенные деревья для сжатия данных». В Кларксоне, Кеннете Л. (ред.). Труды шестого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам, 22–24 января 1995 г. Сан-Франциско, Калифорния, США . ACM/SIAM. стр. 522–530. Средняя глубина доступа в расширённом дереве пропорциональна энтропии.
• Кнут, Дональд (1997). Искусство программирования . Том 3: Сортировка и поиск (3-е изд.). Эддисон-Уэсли. стр. 478. ISBN 0-201-89685-0. Известно, что время, необходимое для доступа к данным в расширяющемся дереве, составляет максимум небольшое постоянное кратное времени доступа статически оптимального дерева, если его амортизировать за любую серию операций.
• Лукас, Джоан М. (1991). «О конкурентоспособности разветвленных деревьев: связь с задачей поиска объединения». Онлайновые алгоритмы: Труды семинара DIMACS, 11–13 февраля 1991 г. Серия по дискретной математике и теоретической информатике. Том 7. Центр дискретной математики и теоретической информатике . С. 95–124. ISBN 0-8218-7111-0.
• Pettie, Seth (2008). Splay Trees, Davenport-Schinzel Sequences, and the Deque Conjecture (PDF) . Proc. 19th ACM-SIAM Symposium on Discrete Algorithms . Vol. 0707. pp. 1115–1124. arXiv : 0707.2160 . Bibcode : 2007arXiv0707.2160P.
• Слейтор, Дэниел Д .; Тарьян, Роберт Э. (1985). «Саморегулирующиеся двоичные деревья поиска» (PDF) . Журнал ACM . 32 (3): 652–686. doi :10.1145/3828.3835. S2CID  1165848.
• Сундар, Раджамани (1992). «О гипотезе Дека для алгоритма splay». Combinatorica . 12 (1): 95–124. doi :10.1007/BF01191208. S2CID  27422556.
• Тарьян, Роберт Э. (1985). «Последовательный доступ в расширяющихся деревьях занимает линейное время». Combinatorica . 5 (4): 367–378. doi :10.1007/BF02579253. S2CID  34757821.
• Бендер, Майкл А.; Конвей, Алекс; Фарах-Колтон, Мартин; Кушмаул, Уильям; Тальявини, Гвидо (2023). «Tiny Pointers». Труды ежегодного симпозиума ACM-SIAM по дискретным алгоритмам (SODA) 2023 года : 477–508. doi : 10.1137/1.9781611977554.ch21. ISBN 978-1-61197-755-4. S2CID  244709005.

Внешние ссылки

• Словарь алгоритмов и структур данных NIST: Splay Tree
• Реализации на языках C и Java (Дэниел Слейтор)
• Указатели на визуализацию развернутого дерева
• Быстрая и эффективная реализация Splay-деревьев
• Реализация Java-решения Top-Down Splay Tree
• Деревья-молнии