Распространение дерева

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

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

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

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

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

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

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

Недостатки

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

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

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

Операции

Растягивание

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

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

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

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

Зигзагообразный шаг: этот шаг выполняется, когда 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 на два поддерева: S и T.
• Создайте новое дерево, в котором x — корень, S — его левое поддерево, а T — правое поддерево.

Удаление

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

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

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

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

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

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

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

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

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

#include <функционал> #ifndef SPLAY_TREE #define SPLAY_TREEшаблон < имя_типа T , имя_типа Comp = std :: less < T >> class splay_tree { private : Comp comp ; беззнаковый длинный p_size ; struct node { node * влево , * вправо ; узел * родительский ; клавиша Т ; узел ( const T & init = T ()) : левый ( nullptr ), правый ( nullptr ), родительский ( nullptr ), ключ ( init ) { } ~ node () {                                      } } * корень ; void left_rotate ( узел * x ) { узел * y = x -> right ; если ( y ) { Икс -> вправо = y -> влево ; if ( y -> left ) y -> left -> родительский = x ; y -> родительский = x -> родительский ; } if ( ! x -> родительский ) root = y ; else if ( x == x -> родительский -> left ) x -> родительский -> left = y ; иначе x -> родительский -> right = y ; если ( y ) y -> влево = x ; х -> родитель = y ; } void right_rotate ( узел * x ) { node * y = x -> left ; если ( y ) { Икс -> влево = y -> вправо ; if ( y -> вправо ) y -> вправо -> родительский = x ; y -> родительский = x -> родительский ; } if ( ! x -> родительский ) root = y ; else if ( x == x -> родительский -> left ) x -> родительский -> left = y ; иначе х ->                                                                                            родитель -> справа = y ; если ( y ) y -> вправо = x ; х -> родитель = y ; } void splay ( node * x ) { while ( x -> родительский ) { if ( !x -> родительский -> родительский ) { if ( x -> родительский -> left == x ) right_rotate ( x -> родительский ); иначе left_rotate ( x -> родительский ); } else if ( x -> родительский -> left == x && x -> родительский -> родительский -> left == x -> родительский ) { right_rotate ( x -> родительский -> родительский ); right_rotate ( x -> родительский ); } else if ( x -> родительский -> правый == x && x -> родительский -> родительский -> правый == x -> родительский ) { left_rotate ( x -> родительский -> родительский ); left_rotate ( x -> родительский ); } else if ( x -> родительский -> left == x && x -> родительский -> родительский -> right == x -> родительский ) { right_rotate ( x -> родительский ); left_rotate ( x -> родительский ); } еще {                                                                        left_rotate ( x -> родительский ); right_rotate ( x -> родительский ); } } } void replace ( node * u , node * v ) { if ( ! u -> родительский ) root = v ; иначе if ( u == u -> родительский -> left ) u -> родительский -> left = v ; иначе u -> родительский -> right = v ; если ( v ) v -> родитель = u -> родитель ; } node * subtree_minimum ( node * u ) { while ( u -> left ) u = u -> left ; вернуть тебя ; } node * subtree_maximum ( node * u ) { while ( u -> right ) u = u -> right ; вернуть тебя ; } Public : splay_tree () : root ( nullptr ), p_size ( 0 ) { } void Insert ( const T & key ) { node * z = root ; узел * p = nullptr ; в то время как ( z ) { п знак равно z ; если ( comp ( z -> ключ , ключ )) z = z -> вправо ; иначе z = z ->                                                                                                 левый ; } Z = новый узел ( ключ ); г -> родитель = п ; если ( ! p ) корень = z ; иначе if ( comp ( p -> key , z -> key )) p -> right = z ; иначе р -> влево = z ; разворот ( z ); p_размер ++ ; } node * find ( const T & key ) { node * z = root ; while ( z ) { if ( comp ( z -> ключ , ключ )) z знак равно z -> вправо ; иначе if ( comp ( key , z -> key )) z = z -> left ; иначе вернуть z ; } Вернуть нульптр ; } void Erase ( const T & key ) { node * z = find ( key ); если ( ! z ) возврат ; разворот ( z ); если ( ! z -> влево ) заменить ( z , z -> вправо ); иначе , если ( ! z -> вправо ) заменить ( z , z -> влево ); еще { узел * y = subtree_minimum ( z -> вправо ); если ( у ->                                                                                                родитель != z ) { replace ( y , y -> вправо ); y -> вправо = z -> вправо ; y -> вправо -> родительский = y ; } Заменить ( z , y ); y -> влево = z -> влево ; y -> слева -> родительский = y ; } Удалить г ; p_размер -- ; }                          /* //альтернативная реализация  void Erase(const T &key) {  node *z = find(key);  если (!z) возврат;  расширение (г);  узел *s = z->влево;  узел *t = z-> вправо;  удалить z;  узел *sMax = NULL;  если (s) {  s->parent = NULL;  sMax = subtree_maximum(s);  расширение (sMax);  корень = сМакс;  }  Если (т) {  если (ы)  sMax->right = t;  еще  корень = т;  т->родитель = sMax;  }  p_size--;  } */ const T & минимум () { return subtree_minimum ( корень ) -> ключ ; } const T & Maximum () { return subtree_maximum ( root ) -> key ; } bool пустой () const { return root == nullptr ; } unsigned long size () const { return p_size ; } };                                     #endif // SPLAY_TREE

Анализ

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

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

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

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

Зиг-шаг

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

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

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

При суммировании по всей операции расширения это число увеличивается до 1 + 3(rank(root)−rank( x )), что равно O(log n ), поскольку мы используем операцию Zig не более одного раза, а амортизированная стоимость zig равна большинство 1+3(ранг'( x ) − ранг( 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 за поворот. Пусть будет стоимость выполнения последовательности доступов. Тогда стоимость выполнения того же доступа к расширенному дереву составит . ${\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 дополняет дерево расширения счетчиками доступа на каждом узле и нечасто использует их для реструктуризации. Вариант CBTree, называемый LazyCBTree, выполняет не более одного поворота при каждом поиске. Это используется вместе с оптимистической схемой ручной проверки для создания параллельного самонастраивающегося дерева. ^[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. Тарьян 1985.
12. Элмасри 2004.
13. Петти 2008.
14. Сундар 1992.
15. Афек и др. 2014 год
16. Бендер и др. 2023.

Рекомендации

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

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

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