Расширяющее (косое) дерево - Splay Tree

Основная идея Splay Tree состоит в том, чтобы перенести элемент, к которому недавно осуществлен поиск(или доступ) в корень дерева. Тем самым дать возможность достучаться к нему повторно за O(1).

Представьте себе ситуацию, когда у нас есть миллионы ключей, и лишь некоторые из них используются чаще других, что кстати говоря весьма вероятно во многих приложениях.

Все операции с Splay Tree выполняются в среднем за O(log N) времени, где N - количество записей в дереве.

В ближайшие дни рассмотрим основные операции над данным деревом.

Data Science: Алгоритмы и Структуры данных | Чат 💬