170
правок
Изменения
м
→Вторая нижняя оценка Уилбера (Wilber)
Организуем их в полное двоичное [[Дерево поиска, наивная реализация | сбалансированное дерево]].
Если <tex>n</tex>{{---} не степень двойки, то на последний уровень будет заполнен не до конца.
Будем в этом дереве искать наши ключи в том порядке, в котором их искали в оптимальное дереве.
Утверждается, что <tex>\sum\limits_{i \in [1, n]} ch(i) \geqslant \sum\limits_{i \in [1, n]} K</tex>, где <tex>K</tex> {{---}} число изменений жирных ребер.
То есть если мы улучшили правую границу (мы искали что-то справа), а потом улучшили левую (искали слеваот нас), значит где-то по пути мы прошли туда-обратно и сменили жирное ребро.
}}
