Какие преимущества и недостатки имеет декартово дерево поиска по сравнению с другими структурами данных?

Преимущества декартового дерева поиска по сравнению с другими структурами данных:

• Проще реализуется по сравнению с настоящими самобалансирующимися деревьями вроде красно-чёрного. ru.wikipedia.org ipc.susu.ru
• Хорошо ведёт себя «в среднем», если ключи раздать случайно. ru.wikipedia.org
• Типичная для сортирующего дерева операция «разделить по ключу x на „меньше x0“ и „не меньше x0“» работает за O(h), где h — высота дерева. ru.wikipedia.org

Недостатки декартового дерева:

• Большие накладные расходы на хранение: вместе с каждым элементом хранятся два-три указателя и случайный ключ y. ru.wikipedia.org
• Скорость доступа O(n) в худшем, хотя и маловероятном, случае. ru.wikipedia.org Поэтому декартово дерево недопустимо, например, в ядрах ОС. ru.wikipedia.org