11. Splay Неявное дерево

Splay-дерево (англ. Splay-tree) — это двоичное дерево поиска, которое позволяет быстрее находить те данные, которые использовались недавно. Было придумано Робертом Тарьяном и Даниелем Слейтером в 1983 году. Splay-дерево по неявному ключу аналогично декартову дереву по неявному ключу, только в нём не используется сам ключ. Искать в таком дереве можно любой по порядку элемент. Для этого в каждом узле записывается размер его поддерева. В качестве неявного ключа в splay-дереве по неявному ключу выступает количество элементов дерева, меньших данного