170
правок
Изменения
→Вторая нижняя оценка Уилберра (Wilber)
Для ключа <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> уменьшаться.
Числом Уилберра <tex>ch(i)</tex> называется количество смен <tex>r</tex> на <tex>l</tex> и обратно.
<tex>OPT >= \sum\limits_{i \in [1, n]} 1 + ch(i)</tex>
[[Файл::DariaPicture10.png|200px]]
{{Теорема
Организуем их в полное двоичное сбалансированное дерево.
Будем в этом дереве искать наши ключи в том порядке, в котором их искали !!!тамв оптимальное дереве.
Для каждой вершины будем запоминать ребро, по которому мы последний раз проходили при поиске ключей в дереве(назовем его жирное ребро).
