Splay-дерево. Поиск

[kovserg]

1. Не понятно как достигается сбалансированность например если мы хоти взять минимальный и максимальный элемент в дереве или постоянно ищем около этих узлов.
2. Что мешает использовать например 2 сбалансированных дерева для горячих 20% и остальных холодных 80%. И просто регулировать долю и управлять переносом из одного дерева в другое плюс деревья гарантировано сбалансированы.
3. А где собственно тесты производительности?

[wataru]

Самого интересного-то тут и нет! Доказательство или хотя бы интуиция о том, почему такое дерево работает за логарифм в среднем очень бы пригодилось.

Заодно станет понятно, а почему тут разбираются случаи с дедом вершины. Ведь, чтобы поднять искомый x в корень, не надо выполнять пары вращений отец-дед и рассматривать 6 случаев. Достаточно только крутить x влево или вправо, меняя его с отцом. Т.е. всегда действовать как если бы пра-отца у вершины не было.