418
правок
Изменения
м
→Статическая оптимальность сплей-дерева
}}
== Статическая оптимальность сплей-дерева ==
{{Теорема
|statement=
Если к ключам <tex>1</tex>, ..., <tex>n</tex>, сложенным в сплей-дерево выполняется <tex>m</tex> запросов, к <tex>i</tex>-му ключу осуществляется <tex>k_i</tex> запросов, где <tex>k_i</tex> > 0, то суммарное время работы не превышает <tex>O(m * H(p_1, p_2, .., p_n))</tex>, где <tex>p_i = k_i / m</tex>, <tex>H</tex> - шенноновская энтропия
|proof=
}}
==Splay-деревья по неявному ключу==
