170
правок
Изменения
м
{{Определение
|definition='''Жирное ребро'''(англ. ''Prefered Path'') {{---}} ребро, соединяющее вершину с ее последним посещенным ребенком.
}}
Нет описания правки
[[Файл:DariaPicture11.png|300px]]
{{Определение
|definition='''Жирное ребро'''(англ. ''Prefered edge'') {{---}} ребро, соединяющее вершину с ее последним посещенным ребенком.
}}
{{Теорема
Будем в этом дереве искать наши ключи в том порядке, в котором их искали в оптимальное дереве.
Для каждой вершины будем запоминать ребро, по которому мы последний раз проходили при поиске ключей в дереве(назовем его жирное ребро).
Утверждается, что <tex>\sum\limits_{i \in [1, n]} ch(i) \geqslant \sum\limits_{i \in [1, n]} K</tex>, где <tex>K</tex> {{---}} число изменений жирных ребер.
===Построение===
Рассмотрим бинарное дерево поиска.
Разобьем наше дерево на жирные пути.
{{Определение
|definition='''Жирный путь'''(англ. ''Prefered path'') {{---}} путь, состоящий из жирный ребер.
}}
[[Файл:DariaPicture7.png|400px|
