170
правок
Изменения
Нет описания правки
Множество точек определяет, что происходило с деревом.
{{Определение
|definition=Множество точек называется '''древесным''' (англ. ''aboral''), если выполняется следующее свойство:
На сторонах любого невырожденного(площадь прямоугольника больше нуля) прямоугольника, построенного на двух точках, есть еще хотя бы одна точка.
}}
3) Запрос 4 : вершина 3 – вершина 4
]]
{{Определение
|definition=Фазовая диаграмма (диаграмма состояния) работы с деревом — графическое отображение состояния дерева, при котором координата точки <tex>(x_{i}, i)</tex> означает обращение к элементу <tex>x_{i}</tex> в момент времени<tex>i</tex>.
}}
{{Теорема
То есть <tex>OPT(x) = \Omega(M + 1/2* MP)</tex>
==Вторая нижняя оценка Уилбера (англ. ''Wilber'') ==
Для каждого запроса <tex>x</tex> вычислим число Уилбера.
Для ключа <tex>x_[j]</tex> рассмотрим ключи <tex>x_{i} : x_{I} = x_{j}, i = 0..j - 1</tex>
Пусть <tex>a_{i} < x_{j} < b_{i}</tex>, где <tex>a_{i}</tex> и <tex>b_{i}</tex> {{-- -}} левая и правая границы на момент i.
Будем передвигать левую границу каждый раз, когда встречаем число <tex>x_{i} : x_{i} > a, x_{i} < x </tex>. Аналогично правую.
В каждый момент времени позиция <tex>a_{i}</tex> может увеличиваться, <tex>b_{i}</tex> уменьшаться.
{{Определение
|definition='''Жирное ребро'''(англ. ''Prefered Path'') {{---}} ребро, соединяющее вершину с ее последним посещенным ребенком.
}}
