Splay tree

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

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

Преимущества [ править ]

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

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

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

Недостатки [ править ]

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

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

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

Операции [ править ]

Играть [ править ]

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

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

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

Важно помнить, чтобы gg ( прародитель x) теперь указывал на x после любой операции расширения. Если gg имеет значение null, то очевидно, что x теперь является корневым и должен быть обновлен как таковой.

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

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

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

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

Присоединяйтесь [ редактировать ]

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

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

Разделить [ править ]

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

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

Вставка [ править ]

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

• Вставьте x, как в обычном двоичном дереве поиска .
• когда элемент вставлен, выполняется развертка.
• В результате вновь вставленный узел x становится корнем дерева.

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

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

Удаление [ править ]

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

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

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

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

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

Реализация и варианты [ править ]

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

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

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

#include  <функциональный>#ifndef SPLAY_TREE #define SPLAY_TREEtemplate < typename  T ,  typename  Comp  =  std :: less < T >> class  splay_tree  { private :  Comp  comp ;  беззнаковый  длинный  p_size ;  struct  node  {  узел  * слева ,  * справа ;  узел  * родительский ;  Ключ T  ; узел ( const T & init = T ()) : левый ( nullptr ), правый ( nullptr ), родительский ( nullptr ), ключ ( init ) { } ~ node () {               }  }  * корень ;  void  left_rotate ( узел  * х )  {  узел  * у  =  х -> право ;  if  ( y )  {  x -> right  =  y -> left ;  if  ( y -> left )  y -> left -> parent  =  x ;  у -> родитель  =  х -> родитель ;  }  если  ( ! x -> родительский )  root  =  y ;  иначе,  если  ( x  ==  x -> родительский -> левый )  x -> родительский -> left  =  y ;  иначе  x -> родительский -> right  =  y ;  if  ( y )  y -> left  =  x ;  х -> родительский  =  у ;  }  void  right_rotate ( узел  * х )  {  узел  * у  =  х -> влево ;  if  ( y )  {  x -> left  =  y -> right ;  if  ( y -> right )  y -> right -> parent  =  x ;  у -> родитель  =  х -> родитель ;  }  если  ( ! x-> родительский )  root  =  y ;  иначе,  если  ( x  ==  x -> родительский -> левый )  x -> родительский -> left  =  y ;  иначе  x -> родительский -> right  =  y ;  if  ( y )  y -> right  =  x ;  х -> родительский  =  у ;  }  void  splay ( node  * x )  {  while  ( x -> parent )  {  if  ( ! x -> parent -> parent )  {  if  ( x -> parent -> left  ==  x )  right_rotate ( x -> родительский );  иначе  left_rotate ( x -> родительский );  }  иначе,  если  ( x ->родительский -> левый  ==  х  &&  х -> родительский -> родительский -> левый  ==  х -> родительский )  {  right_rotate ( x -> родительский -> родительский );  right_rotate ( x -> родительский );  }  else  if  ( x -> parent -> right  ==  x  &&  x -> parent -> parent -> right  == х -> родитель )  {  left_rotate ( х -> родитель -> родитель );  left_rotate ( x -> родительский );  }  else  if  ( x -> parent -> left  ==  x  &&  x -> parent -> parent -> right  ==  x -> parent )  {  right_rotate ( x -> родительский );  left_rotate ( х-> родитель );  }  else  {  left_rotate ( x -> родительский );  right_rotate ( x -> родительский );  }  }  }  void  replace ( node  * u ,  node  * v )  {  если  ( ! u -> родительский )  root  =  v ;  иначе  если  ( u  ==  u -> родительский -> левый )  u -> родительский -> left  =  v ;  иначе  u -> родительский -> right  =  v ;  если  ( v )  v-> родитель  =  u -> родитель ;  }  node *  subtree_minimum ( node  * u )  {в  то время как  ( u -> left )  u  =  u -> left ;  вернуть  u ;  }  node *  subtree_maximum ( node  * u )  {в  то время как  ( u -> right )  u  =  u -> right ;  вернуть  u ;  } public :  splay_tree ()  :  root ( nullptr ),  p_size ( 0 )  {  }  пустая  вставка ( const  T  & ключ )  {  узел  * z  =  корень ;  узел  * p  =  nullptr ;  в то время как  ( z )  {  p  =  z ;  if  ( comp ( z -> key ,  key ))  z  =  z -> right ;  иначе  z  =  z -> left ;  }  z  =  новый  узел ( ключ );  z -> родительский  =  p ;  если  ( ! p )  root  =  z ;  иначе,  если  ( comp ( p -> key ,  z -> key ))  p -> right  =  z ;  иначе  p -> left  =  z ;  splay ( z );  p_size ++ ;  }  узел *  найти ( const  T  & ключ )  {  узел  * z  =  корень ;  while  ( z )  {  if  ( comp ( z -> key ,  key ))  z  =  z -> right ;  иначе,  если  ( comp ( key ,  z -> key ))  z  =  z -> left ;  иначе  вернуть  z;  }  return  nullptr ;  }  пустое  стирание ( const  T  & ключ )  {  узел  * z  =  найти ( ключ );  если  ( ! z )  возврат ;  splay ( z );  если  ( ! z -> left )  заменить ( z ,  z -> right );  иначе,  если  ( ! z -> right )  replace ( z ,  z -> left );  иначе  {  узел  * y  =  subtree_minimum ( z -> справа );  if  ( y -> parent  ! =  z )  {  replace ( y,  y -> вправо );  y -> right  =  z -> right ;  у -> вправо -> родительский  =  у ;  }  replace ( z ,  y );  y -> left  =  z -> left ;  у -> влево -> родитель  =  у ;  }  удалить  z ;  p_size - ;  }/ * // альтернативная реализация  void erase (const T & key) {  node * z = find (key);  если (! z) возврат;  splay (z);  узел * s = z-> left;  узел * t = z-> right;  удалить z;  узел * sMax = NULL;  если (s) {  s-> parent = NULL;  sMax = subtree_maximum (s);  splay (sMax);  корень = sMax;  }  if (t) {  if (s)  sMax-> right = t;  иначе  корень = t;  t-> parent = sMax;  }  p_size--;  }    * /  const  T &  minimum ()  {  return  subtree_minimum ( корень ) -> ключ ;  }  const  T &  maximum ()  {  return  subtree_maximum ( корень ) -> ключ ;  }  bool  empty ()  const  {  return  root  ==  nullptr ;  }  беззнаковый  длинный  размер ()  const  {  return  p_size ;  } };#endif // SPLAY_TREE

Анализ [ править ]

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

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

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

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

Шаг зиг [ править ]

ΔΦ	= ранг ′ ( p ) - ранг ( p ) + ранг ′ ( x ) - ранг ( x )	[поскольку только p и x меняют ранги]
	= ранг ′ ( p ) - ранг ( x )	[поскольку rank ′ ( x ) = rank ( p )]
	≤ ранг ′ ( x ) - ранг ( x )	[поскольку rank ′ ( p ) <rank ′ ( x )]

Зигзагообразный шаг [ править ]

ΔΦ	= ранг ′ ( g ) - ранг ( g ) + ранг ′ ( p ) - ранг ( p ) + ранг ′ ( x ) - ранг ( x )
	= ранг ′ ( g ) + ранг ′ ( p ) - ранг ( p ) - ранг ( x )	[поскольку rank ′ (x) = rank (g)]
	≤ ранг ′ ( g ) + ранг ′ ( x ) - 2 ранг ( x )	[поскольку rank ( x ) <rank ( p ) и rank ′ ( x )> rank ′ ( p )]
	≤ 3 (ранг ′ ( x ) −rank ( x )) - 2	[из-за вогнутости функции журнала]

Зигзагообразный шаг [ править ]

ΔΦ	= ранг ′ ( g ) - ранг ( g ) + ранг ′ ( p ) - ранг ( p ) + ранг ′ ( x ) - ранг ( x )
	≤ ранг ′ ( g ) + ранг ′ ( p ) - 2 ранг ( x )	[поскольку rank ′ ( x ) = rank ( g ) и rank ( x ) <rank ( p )]
	≤ 3 (ранг ′ ( x ) −rank ( x )) - 2	[из-за вогнутости функции журнала]

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

амортизированная стоимость	= стоимость + ΔΦ
	≤ 3 (ранг ′ ( x ) - ранг ( x ))

При суммировании по всей операции развертывания это телескопирование до 3 (ранг (корень) - ранг ( x )), что составляет O (log n ). Операция Zig добавляет амортизированную стоимость 1, но существует не более одной такой операции.

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

${\ Displaystyle Т _ {\ mathrm {амортизировано}} (т) = О (м \ журнал п)}$

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

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

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

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

${\ Displaystyle Т _ {\ mathrm {фактический}} (м) = О (м \ журнал п + п \ журнал п)}$

Взвешенный анализ [ править ]

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

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

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

${\ displaystyle \ mathrm {rank} (корень) - \ mathrm {rank} (x) = O (\ log {W} - \ log {w (x)}) = O \ left (\ log {\ frac {W } {w (x)}} \ right)}$

где 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}{\log {\frac {W}{w(x)}}}+\sum _{x\in tree}{\log {\frac {W}{w(x)}}}\right)}$

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

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

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

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

Гипотеза динамической оптимальности: ^[1] Пусть это будет любой алгоритм двоичного дерева поиска, который обращается к элементу , проходя путь от корня до по цене , и который между доступами может делать любые вращения в дереве по цене 1 за оборот. Позвольте быть стоимостью для выполнения последовательности доступов. Тогда стоимость того же доступа к расширяемому дереву составляет .${\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)}$

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

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

Варианты [ править ]

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

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

См. Также [ править ]

• Пальчиковое дерево
• Связать / вырезать дерево
• Козел отпущения
• Застежка-молния (структура данных)
• Деревья
• Вращение дерева
• Дерево AVL
• B-дерево
• Т-образное дерево
• Список структур данных
• Структура рабочего набора Иаконо
• Геометрия бинарных деревьев поиска
• Splaysort , алгоритм сортировки с использованием растянутых деревьев
• Treap

Заметки [ править ]

Ссылки [ править ]

• Альберс, Сюзанна; Карпинский, Марек (28 февраля 2002 г.). «Рандомизированные Splay Trees: теоретические и экспериментальные результаты» (PDF) . Письма об обработке информации . 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 .

• Бринкманн, Гуннар; Деграер, Ян; Де Луф, Карел (январь 2009 г.). «Реабилитация нелюбимого ребенка: полураскрытие» (PDF) . Программное обеспечение - практика и опыт . 39 (1): 33–45. CiteSeerX  10.1.1.84.790 . DOI : 10.1002 / spe.v39: 1 . ЛВП : 11382/102133 .Результаты показывают, что полурасширение, которое было представлено в той же статье, что и расширение, работает лучше, чем расширение, почти во всех возможных условиях. Это делает полурасширение хорошей альтернативой для всех приложений, где обычно применяется расширение. Причина, по которой растяжение стало настолько заметным, в то время как полурасширение относительно неизвестно и еще менее изучено, и трудно понять.

• Коул, Ричард; Мишра, Бад; Шмидт, Жанетт; Сигел, Алан (январь 2000 г.). «О гипотезе динамического пальца для Splay Trees. Часть I: Splay Sorting log n-Block Sequences». SIAM Journal on Computing . 30 (1): 1–43. CiteSeerX  10.1.1.36.4558 . DOI : 10.1137 / s0097539797326988 .

• Коул, Ричард (январь 2000 г.). «О гипотезе динамического пальца для Splay Trees. Часть II: Доказательство». SIAM Journal on Computing . 30 (1): 44–85. CiteSeerX  10.1.1.36.2713 . DOI : 10.1137 / S009753979732699X .

• Elmasry, Амр (апрель 2004), "О теореме последовательного доступа и Deque гипотезы для расширяющихся деревьев" , Теоретическая информатика , 314 (3): 459-466, DOI : 10.1016 / j.tcs.2004.01.019

• Гудрич, Майкл; Тамассия, Роберто; Голдвассер, Майкл (2014). Структуры данных и алгоритмы в Java (6-е изд.). Вайли. п. 506. ISBN. 978-1-118-77133-4.

• Кнут, Дональд (1997). Искусство программирования . 3: Сортировка и поиск (3-е изд.). Эддисон-Уэсли. п. 478. ISBN 0-201-89685-0.

• Лукас, Джоан М. (1991). «О конкурентоспособности Splay Trees: отношение к проблеме поиска союза». Онлайн Алгоритмы: Труды семинара DIMACS, 11-13 февраля, 1991 . Серия по дискретной математике и теоретической информатике. 7 . Центр дискретной математики и теоретической информатики . С. 95–124. ISBN 0-8218-7111-0.

• Петти, Сет (2008), «Деревья с разворотом, последовательности Давенпорта-Шинцеля и гипотеза Дека» (PDF) , Proc. 19-й симпозиум ACM-SIAM по дискретным алгоритмам , 0707 : 1115–1124, arXiv : 0707.2160 , Bibcode : 2007arXiv0707.2160P

• Слейтор, Дэниел Д .; Тарджан, Роберт Э. (1985). «Самонастраивающиеся деревья двоичного поиска» (PDF) . Журнал ACM . 32 (3): 652–686. DOI : 10.1145 / 3828.3835 . S2CID  1165848 .

• Сундар, Раджамани (1992). «О гипотезе Дека для алгоритма расширения». Combinatorica . 12 (1): 95–124. DOI : 10.1007 / BF01191208 . S2CID  27422556 .

• Тарджан, Роберт Э. (1985). «Последовательный доступ в растянутых деревьях занимает линейное время». Combinatorica . 5 (4): 367–378. DOI : 10.1007 / BF02579253 . S2CID  34757821 .

Внешние ссылки [ править ]

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