На Splay Trees странице Википедии сказано (в преимуществах раздел):
Возможность создания версии постоянной структуры данных расширенных деревьев, которая обеспечивает доступ как к предыдущей, так и к новой версии после обновления. Это может быть полезно в функциональном программировании и требует амортизированного пространства O(log n) для каждого обновления.
Это почему? Как функциональное программирование использует постоянные Splay-деревья?
Одной из главных целей современного функционального программирования является лучшее управление состоянием, желательно с минимальным его использованием, поскольку программы с состоянием должны тщательно выполнять команды в правильной последовательности, чтобы избежать ошибок.
Постоянные структуры данных хороши именно тем, что они не используют изменяемое состояние, что позволяет использовать их в чистых и неизменяемых вычислениях.
//mutable tree
var t = new_tree();
add(t, 1);
add(t, 2);
//the tree has now changed so if anyone was depending on the old value
//we will now have a problem
//persistent tree
var t = new_tree();
var t2 = add(t, 1);
var t3 = add(t2, 2);
//t1 and t2 have not changed
Указанная вами цитата просто подчеркивает, что постоянные структуры данных обычно используются (и предпочтительнее) в чистом функциональном программировании. Ничего особенного в растопыренных деревьях в данном случае нет.
Ваш вопрос, кажется, исходит из постоянно досадной терминологической путаницы. Лучшей фразой могло бы быть чисто функциональное, то есть функциональное программирование без деструктивной мутации. Путаница, вероятно, возникает из-за того, что неизменяемые, постоянные структуры данных более распространены в функциональном программировании в целом по целому ряду причин.
Короче говоря, вы, вероятно, можете прочитать эту фразу как «создание постоянных расширенных деревьев может быть полезно при программировании только с неизменяемыми структурами данных», что граничит с тавтологией.
Я бы даже сказал обратное: с расширенными деревьями менее удобно работать в функциональном программировании, потому что вам нужно возвращать новое дерево даже после каждой операции поиска и отслеживать последнее дерево почти для всех операций. Кроме того, все деревья поиска, о которых я знаю, могут быть использованы напрямую функционально с O(log n) дополнительного пространства на операцию. Я полагаю, что единственный интересный факт в этом предложении состоит в том, что потребность в памяти для каждой операции остается амортизированной O(log n), даже несмотря на то, что мы все время реструктурируем дерево, но обратите внимание, что теперь мы платим эту космическую цену даже за поиски.
