На страницата Splay Trees в Уикипедия се казва (в Предимствата раздел):
Възможност за създаване на постоянна версия на структурата на данните на splay дървета — което позволява достъп до предишната и новата версия след актуализация. Това може да бъде полезно при функционално програмиране и изисква амортизирано 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) амортизирано, въпреки че преструктурираме дървото през цялото време, но забележете, че сега плащаме тази цена за пространство дори за търсения.
