Splay-деревья

Сбалансированное дерево поиска является фундаментом для многих современных алгоритмов. На страницах книг по Computer Science вы найдете описания красно-черных, AVL-, B- и многих других сбалансированных деревьев. Но является ли перманентная сбалансированность тем Святым Граалем, за которым следует гоняться? Представим, что мы уже построили дерево на c7f092d481acb49c8a0f96178ceb3119.gif ключах и теперь нам нужно отвечать на запросы, лежит ли заданный ключ в дереве. Может так оказаться, что пользователя интересует в основном один ключ, и остальные он запрашивает только время от времени. Если ключ лежит далеко от корня, то 6015f7e7e19971bf1372e01171eaadcb.gif запросов могут отнять 07663dc3c790b8c5e111597f71b68abc.gif времени. Здравый смысл подсказывает, что оценку можно оптимизировать до 7be27494810106e7a26b615c21f37527.gif, надстроив над деревом кэш. Но этот подход имеет некоторый недостаток гибкости и элегантности. Сегодня я расскажу о splay-деревьях. Эти деревья не являются перманентно сбалансированными и на отдельных запросах могут работать даже линейное время. Однако, после каждого запроса они меняют свою структуру, что позволяет очень эффективно обрабатывать часто повторяющиеся запросы. Более того, амортизационная стоимость обработки одного запроса у них 84c07bcc99d5fc8ab9086ace521ed96a.gif, что делает splay-деревья хорошей альтернативой для перманентно сбалансированных собратьев.Читать дальше…

© Habrahabr.ru