Изменения

Для того, чтобы доступ к недавно найденным данным был быстрее, надо, чтобы эти данные находились ближе к корню. Этого мы можем добиться, используяразличные эвристики:*"'''Move to Root" ''' {{---}} эвристика, совершающая совершает повороты вокруг ребра <tex>(x, p)</tex> (, где <tex>x</tex> - найденная вершина, <tex>p</tex> - ее предок), пока <tex>x</tex> не окажется корнем дерева. Эта эвристика не дает нам никакого улучшения времени работыОднако можно построить такую последовательность операций, что амортизированное время доступа к вершине будет <tex> O(n) </tex>.*"'''Splay" ''' {{---}} эвристикатакже совершает повороты, меняющая структуру дерева при перемещения <tex>x</tex> в корень такно чередует различные виды поворотов, чтобы следующие поиски происходили быстрееблагодаря чему достигается логарифмическая амортизированная оценка. Она будет подробно описана ниже и ее мы будем использовать.