Чередовать нижнюю границу - Interleave lower bound

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

Доказано несколько вариантов этой нижней оценки.[1][2][3] Эта статья основана на одном из вариантов.[4]

Определения

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

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

Для каждого узла у в P определите:

  • Оставили(у) = у сам и его левое поддерево;
  • Правильно(у) = правое поддерево у.

Существует последовательность обращений к элементам дерева: Икс = (Икс1, Икс2, ..., Иксм).

Для каждого доступа Икс и узел у, определите метку Икс за у в качестве:

  • "L" - если Икс в Оставили(у);
  • "р" - если Икс в Правильно(у);
  • null - иначе.

Этикетка у это объединение меток от всех обращений.

Например, если последовательность обращений: 7,6,3, тогда метка корня (4) будет: «RRL», метка 6 будет: «RL», а метка 2 будет: «L ".

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

В граница чередования, , - сумма перемежений по всем узлам дерева. Граница чередования указанной выше последовательности равна 2.

Граница

В лемма о чередовании границ Говорит, что каждый BST, который должен получить доступ к элементам в последовательности Икс, должен сделать как минимум действия.

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

Пусть Ti будет состоянием произвольного BST в момент времени i.

Для каждого узла у ∈ {1,...,п}, определите точка перехода, Транс(у, Ti), как узел минимальной глубины z в BST Ti так, чтобы путь от корня Ti до z включает как узел из Оставили(у) и узел из Правильно(у). Интуитивно понятно, что любой алгоритм BST на Ti, который обращается к элементу из Правильно(у), а затем элемент из Оставили(у) (или наоборот) должен касаться Транс(у, Ti) Хотя бы один раз. Можно доказать следующие свойства точки перехода:[4]

  1. Точка перехода четко определена. То есть для любого узла у и время я, существует уникальная точка перехода для у в Ti.
  2. Точка перехода является «стабильной» и не меняется до тех пор, пока не будет достигнута. Т.е., если z=Транс(y, Tj) и

алгоритм доступа BST не трогает z в Ti для всех я в интервале [j,k], тогда z=Транс(y, Tk).

  1. У каждого узла своя точка перехода, т. Е. Отображение у → Транс (у, Ti) взаимно однозначно, т.е. нет узла в Ti является точкой перехода для нескольких узлов.

Эти свойства используются для доказательства оценки.

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

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

  1. ^ Уилбер, Р. (1989). «Нижние границы для доступа к деревьям двоичного поиска с поворотами». SIAM Журнал по вычислениям. 18: 56–67. Дои:10.1137/0218004.
  2. ^ Hampapuram, H .; Фредман, М. Л. (1998). «Оптимальные двумерные двоичные деревья и сложность ведения частичных сумм». SIAM Журнал по вычислениям. 28: 1–9. Дои:10.1137 / S0097539795291598.
  3. ^ Patrascu, M .; Демейн, Э. Д. (2006). «Логарифмические нижние границы в модели ячейки-зонда» (PDF). SIAM Журнал по вычислениям. 35 (4): 932. arXiv:cs / 0502041. Дои:10.1137 / S0097539705447256.
  4. ^ а б Demaine, E.D .; Harmon, D .; Iacono, J .; Патраску, М. (2007). «Динамическая оптимальность - почти» (PDF). SIAM Журнал по вычислениям. 37: 240–251. Дои:10.1137 / S0097539705447347.