Сбалансированное дерево поиска является фундаментом для многих современных алгоритмов. На страницах книг по Computer Science вы найдете описания красно-черных, AVL-, B- и многих других сбалансированных деревьев. Но является ли перманентная сбалансированность тем Святым Граалем, за которым следует гоняться?
Представим, что мы уже построили дерево на
![](https://habrastorage.org/getpro/habr/post_images/c7f/092/d48/c7f092d481acb49c8a0f96178ceb3119.gif)
ключах и теперь нам нужно отвечать на запросы, лежит ли заданный ключ в дереве. Может так оказаться, что пользователя интересует в основном один ключ, и остальные он запрашивает только время от времени. Если ключ лежит далеко от корня, то
![](https://tex.s2cms.ru/svg/m)
запросов могут отнять
![](https://habrastorage.org/getpro/habr/post_images/076/63d/c3c/07663dc3c790b8c5e111597f71b68abc.gif)
времени. Здравый смысл подсказывает, что оценку можно оптимизировать до
![](https://habrastorage.org/getpro/habr/post_images/7be/274/948/7be27494810106e7a26b615c21f37527.gif)
, надстроив над деревом кэш. Но этот подход имеет некоторый недостаток гибкости и элегантности.
Сегодня я расскажу о splay-деревьях. Эти деревья не являются перманентно сбалансированными и на отдельных запросах могут работать даже линейное время. Однако, после каждого запроса они меняют свою структуру, что позволяет очень эффективно обрабатывать часто повторяющиеся запросы. Более того, амортизационная стоимость обработки одного запроса у них
![](http://habrastorage.org/getpro/habr/post_images/84c/07b/cc9/84c07bcc99d5fc8ab9086ace521ed96a.gif)
, что делает splay-деревья хорошей альтернативой для перманентно сбалансированных собратьев.