3622
правки
Изменения
→Поиск
Если текущий жирный путь не содержит искомый элемент, то сделаем переход по вспомогательной ссылке (красная стрелка в tango-дереве) и осуществим поиск в новом жирном пути (splay-дереве).
Поиск в splay-дереве (синее дерево в splay-дереве) работает за высоту от количества вершин (количество вершин {{---}}} длина жирного пути (<tex>\log n</tex>)) {{---}} то есть за <tex>\log \log n</tex>.
Поиск во всем дереве соответствует <tex>(\log \log n) \cdot </tex> число проходов по нежирному ребру.
