170
правок
Изменения
м
Нет описания правки
Начинаем с поиска в жирном пути корня tango-дерева –- splay-дереве.
Если текущее вспомогательное дереве текущий жирный путь не содержит искомый элемент, поиск останавливается на родителе корня поддерева, содержащего нужное значение.
Пройдем по вспомогательной ссылке(красная стрелка) и осуществим поиск в новом жирном пути(splay-дереве).
Поиск в splay-дереве(синем) дереве = высота от количества вершин (количество вершин = длине жирного пути = <tex>log n</tex>) = <tex>log log n</tex>.
