Нижняя граница чередования

В теории оптимальных бинарных деревьев поиска нижняя граница чередования — это нижняя граница количества операций, необходимых двоичному дереву поиска (BST) для выполнения заданной последовательности доступов.

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

Определение

Оценка основана на фиксированном идеальном BST. $P$, называемое деревом нижней границы, по ключам $\{1,2,...,n\}$. Например, для $n=7$, $P$ может быть представлен следующей структурой скобок:

[([1] 2 [3]) 4 ([5] 6 [7])]

Для каждого узла $y$ в $P$, определять:

• $Left(y)$ быть набором узлов в левом поддереве $y$, включая $y$.
• $Right(y)$ быть набором узлов в правом поддереве $y$.

Рассмотрим следующую последовательность доступа: $X=x_{1},x_{2},...,x_{m}$. Для фиксированного узла $y$, и для каждого доступа $x_{i}$, определите метку $x_{i}$ относительно $y$ как:

• « Л » — если $x_{i}$ находится в $Left(y)$.
• " Р " - если $x_{i}$ находится в $Right(y)$;
• Нуль – иначе.

Этикетка $y$ представляет собой объединение меток всех доступов. Например, если последовательность доступов следующая: $7,6,3$ затем метка корня $(4)$ это: «RRL», метка 6: «RL», а метка 2: «L».

Для каждого узла $y$, определите количество чередования через y как количество чередований между L и R в метке $y$. В приведенном выше примере чередование через $4$ и $6$ является $1$ и чередование через все остальные узлы $0$.

чередования Граница , ${\mathit {IB}}(X)$, представляет собой сумму чередования всех узлов дерева. Граница чередования приведенной выше последовательности равна $2$.

Утверждение о нижней границе и его доказательство.

Граница чередования резюмируется следующей теоремой.

Теорема — Пусть $X$ быть последовательностью доступа. Обозначим через $IB(X)$ граница чередования $X$, затем ${\mathit {IB}}(X)/2-n$ является нижней границей $OPT(X)$, стоимость оптимального автономного BST, который обслуживает $X$.

Следующее доказательство основано на.

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

Позволять $X=x_{1},x_{2},...,x_{m}$ быть последовательностью доступа. Обозначим через $T_{i}$ состояние произвольного BST в момент времени $i$ т.е. после выполнения последовательности $x_{1},x_{2},...,x_{i}$. Мы также фиксируем нижнюю границу BST $P$.

Для узла $y$ в $P$, определите точку перехода для $y$ во время $i$ быть узлом минимальной глубины $z$ в БСТ $T_{i}$ такой, что путь от корня $T_{i}$ к $z$ включает в себя как узел слева ( y ), так и узел справа ( y ). Интуитивно понятно, что любой алгоритм BST на $T_{i}$ который обращается к элементу справа ( y ), а затем элемент слева ( y ) (или наоборот) должен коснуться точки перехода $y$ хотя бы один раз. В следующей лемме мы покажем, что точка перехода определена корректно.

Лемма 1 — Точка перехода узла $y$ в $P$ за раз $i$ существует и он уникален.

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

Определять $\ell$ быть наименьшим общим предком всех узлов в $T_{i}$ которые находятся слева ( y ). Даны любые два узла $a<b$ в $T_{i}$, низший общий предок $a$ и $b$, обозначенный $lca(a,b)$, удовлетворяет следующим неравенствам. $a\leq lca(a,b)\leq b$. Следовательно, $\ell$ находится в Left(y) и $\ell$ — единственный узел минимальной глубины в $T_{i}$. Те же рассуждения можно применить и к $r$, самый низкий общий предок всех узлов в $T_{i}$ которые находятся в Right(y) . Кроме того, самый низкий общий предок для всех точек в Left(y) и right(y) также находится в одном из этих наборов. Следовательно, уникальный узел минимальной глубины должен находиться среди узлов Left(y) и right(y) . Точнее, это либо $\ell$ или $r$. Предположим, это $\ell$. Затем, $\ell$ является предком $r$. Следовательно, $r$ является точкой перехода, поскольку путь от корня к $r$ содержит $\ell$. Более того, любой путь в $T_{i}$ от корня до узла поддерева $y$ должен посетить $\ell$ потому что он является предком всех таких узлов и для любого пути к узлу нужно посетить нужный регион $r$ потому что это наименьший общий предок всех узлов в right(y) . В заключение, $r$ является уникальной точкой перехода для $y$ в $T_{i}$.

Вторая лемма, которую нам нужно доказать, гласит, что точка перехода устойчива. Оно не изменится, пока к нему не прикоснутся.

Лемма 2 — Дан узел $y$. Предполагать $z$ является точкой перехода $y$ за раз $j$. Если алгоритм доступа к BST не затрагивает $z$ в $T_{i}$ для $i\in [j,k]$, то точка перехода $y$ останется $z$ в $T_{i}$ для $i\in [j,k]$.

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

Рассмотрим то же определение для $\ell$ и $r$ как в лемме 1. Не ограничивая общности, предположим также, что $\ell$ является предком $r$ в BST в то время $j$, обозначенный $T_{j}$. Как результат, $r$ будет точкой перехода $y$. По гипотезе алгоритм BST не затрагивает точку перехода, в нашем случае $r$, на протяжении всего $[j,k]$. Следовательно, он не затрагивает ни один узел в Right(y) . Следовательно, $r$ остается наименьшим общим предком для любых двух узлов в Right(y) . Однако алгоритм доступа может коснуться узла в Left(y) . касаться наименьшего общего предка всех узлов в Left(y). Точнее, он может одновременно $i$, который мы будем обозначать $\ell _{i}$. Несмотря на это, $\ell _{i}$ останется предком $r$ по следующим причинам: Во-первых, обратите внимание, что любой узел Left(y), находящийся за пределами дерева с корнем в $r$ во время $j$ не могу войти в это дерево одновременно $i\in [j,k]$, с $r$ не затронут в этот период времени. Во-вторых, существует хотя бы один узел $\ell _{i}'$ в Left(y) за пределами дерева с корнем $r$, в любое время $i\in [j,k]$. Это с тех пор $\ell$ изначально был снаружи $r$поддерево, и никакие узлы вне дерева не могут войти в него в этот период времени. Теперь рассмотрим $a_{i}=lca(\ell _{i}',r)$. $a_{i}$ не может быть $r$ с $\ell _{i}'$ не находится в поддереве $r$. Так, $a_{i}$ должно быть в Left(y) , так как $\ell _{i}'\leq a_{i}\leq r$. Следовательно $\ell _{i}$ должен быть предком $a_{i}$ и, как следствие, предок $r$ во время $i$. Следовательно, всегда существует узел в Left(y) на пути от корня до $r$и как таковой $r$ остается точкой перехода.

Последняя лемма доказательства гласит, что каждый узел $y\in P$ имеет свою уникальную точку перехода.

Лемма 3. Учитывая BST во времени $i$, $T_{i}$, любой узел $y$ в $T_{i}$ может быть переходом не более чем для одного узла в $P$.

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

Учитывая два различных узла $y_{1},y_{2}\in P$. Позволять $r_{1},\ell _{1},r_{2},\ell _{2}$ быть низшим общим предком $Right(y_{1}),Left(y_{1}),Right(y_{2}),Left(y_{2})$ соответственно. Из леммы 1 мы знаем, что точка перехода $y_{i}$ либо $\ell _{i}$ или $r_{i}$ для $i\in \{1,2\}$. Теперь нам предстоит рассмотреть два основных случая.

Случай 1: между ними нет родственных связей. $y_{1}$ и $y_{2}$ в $P$. Следовательно, $Left(y_{1}),Left(y_{2}),Right(y_{1}),$ и $Right(y_{2})$ все непересекающиеся. Таким образом, $r_{1}\neq r_{2}\neq \ell _{1}\neq \ell _{2}$, и точки перехода разные.

Случай 2. Предположим без ограничения общности, что $y_{1}$ является предком $y_{2}$ в $P$.

Случай 2.1. Предположим, что точка перехода $y_{1}$ не находится в дереве с корнем $y_{2}$ в $P$. Таким образом, он отличается от $\ell _{2}$ и $r_{2}$, и, следовательно, точка перехода $y_{2}$.

Случай 2.2: Точка перехода $y_{1}$ находится на дереве с корнем $y_{2}$ в $P$. Точнее, это один из низших общих предков $Left(y_{2})$ и $right(y_{2})$. Другими словами, это либо $\ell _{2}$ или $r_{2}$.

Предполагать $a_{1}$ является низшим общим предком поддерева с корнем в $y_{1}$ и не содержит $y_{2}$. У нас есть $\ell _{2}$ и $r_{2}$ глубже, чем $a_{1}$ потому что один из них является точкой перехода. Предположим, что $\ell _{2}$ является точкой перехода. Затем, $\ell _{2}$ менее глубока, чем $r_{2}$. В этом случае, $\ell _{2}$ является точкой перехода $y_{1}$ и $r_{2}$ является точкой перехода $y_{2}$. Аналогичные рассуждения применимы, если $r_{2}$ менее глубока, чем $\ell _{2}$. В общем, точка перехода $y_{1}$ является менее глубоким из $\ell _{2}$ и $r_{2}$, и $y_{2}$ имеет более глубокую точку перехода.

В заключение отметим, что точки перехода во всех случаях разные.

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

По лемме 3 мы знаем, что в любой момент времени $i$, любой узел $y$ в $T_{i}$ может быть переходом не более чем для одного узла в $P$. Таким образом, достаточно посчитать количество касаний переходного узла $y$, сумма всех $y$.

Следовательно, для фиксированного узла $y\in P$, позволять $\ell$ и $r$ определить как в лемме 1. Точка перехода $y$ находится среди этих двух узлов. На самом деле, оно более глубокое. Позволять $x_{i_{1}},x_{i_{2}},...,x_{i_{p}}$ быть максимальной упорядоченной последовательностью доступа к узлам, которые чередуются между $Left(y)$ и $Right(y)$. Затем $p$ это количество чередования через узел $y$. Предположим, что четные индексированные доступы находятся в $Left(y)$, а нечетные находятся в $Right(y)$ то есть $x_{i_{2j}}\in Left(y)$ и $x_{i_{2j-1}}\in Right(y)$. По свойствам наименьшего общего предка мы знаем, что доступ к узлу в $Left(y)$, оно должно коснуться $\ell$. Аналогично, доступ к узлу в $Right(y)$ должен коснуться $r$. Рассмотрим каждый $j\in [1,\lfloor p/2\rfloor ]$. За два последовательных доступа $x_{i_{2j-1}}$ и $x_{i_{2j}}$, если они избегают прикасаться к точке доступа $y$, затем $\ell$ и $r$ должно меняться между ними. Однако по лемме 2 такое изменение требует касания точки перехода. Следовательно, алгоритм доступа BST затрагивает точку перехода $y$ хотя бы один раз за интервал $[i_{2j-1},i_{2j}]$. Подводя итог всему $j\in [1,\lfloor p/2\rfloor ]$, лучший алгоритм касается точки перехода $y$ по меньшей мере $\lfloor p/2\rfloor \geq p/2-1$. Подводя итог всему $y$,

      $\sum _{y\in P}p_{y}/2-1\geq IB(X)/2-n$

где $p_{y}$ это количество чередования через $y$. По определению, $p_{y}$это добавить до $IB(X)$. На этом доказательство завершается.

См. также

• Дерево танго
• Оптимальное двоичное дерево поиска
• Геометрия бинарных деревьев поиска