История изменений
Исправление intelfx, (текущая версия) :
Ну да.
Собственно, trie в реальном мире куда более часто встречающееся явление, чем treap — оно и понятно почему. Префиксное дерево улучшает асимптотику с n² до n.
А у Декартова дерева гораздо меньше область применимости, это ведь просто дерево поиска, которое не нужно балансировать (и ещё пара очень специфических операций, типа разрезать дерево на два / склеить обратно за логарифм). А зачем, если чёрно-красные деревья уже давно написаны?
Исправление intelfx, :
Ну да.
Собственно, trie в реальном мире куда более часто встречающееся явление, чем treap — оно и понятно почему. Префиксное дерево улучшает асимптотику с n² до n.
А у Декартова дерева гораздо меньше область применимости, это ведь просто дерево поиска, которое не нужно балансировать (и ещё пара очень специфических операций, типа разделить дерево на два за логарифм). А зачем, если чёрно-красные деревья уже давно написаны?
Исходная версия intelfx, :
Ну да.
Собственно, trie в реальном мире куда более часто встречающееся явление, чем treap — оно и понятно почему. Префиксное дерево улучшает асимптотику с n² до n.
А у Декартова дерева гораздо меньше область применимости, это ведь просто дерево поиска, которое не нужно балансировать. А зачем, если чёрно-красные деревья уже давно написаны?