Действительно ли "деревья поиска Brodal" были реализованы для практического использования?

Бродал и соавт. в своей статье ESA '06 продемонстрировали существование чисто функциональной структуры с логарифмическим поиском, обновлением и вставкой, а также слиянием в постоянное время. (Заметьте, я не говорю о кучах Бродала, которые представляют собой другую структуру данных, довольно широко используемую для реализации чисто функциональных очередей с приоритетами.) Это кажется очень прибыльным результатом и должно привести к эффективным чисто функциональным наборам и картам, но Я не вижу, чтобы они использовались нигде:

• Haskell containers использует деревья Адамса;
• Стандартная библиотека OCaml использует деревья AVL;
• Сортированные неизменные карты Scala реализованы с использованием красно-черных деревьев.

Если деревья Brodal действительно дают такие хорошие результаты, почему они не были адаптированы в стандартные библиотеки функциональных языков программирования? На самом деле, я даже не видел ни одной реализации бродальских деревьев!

В частности, это потому, что:

• их очень трудно (или практически невозможно) реализовать правильно;
• константы очень велики, а реальные выгоды кажутся маленькими;
• другие причины;
• или комбинация вышеупомянутого?

Ответы