Можно ли использовать красно-черное дерево для алгоритма наилучшего соответствия?

Question

Я знаю, что наиболее подходящий алгоритм должен перебирать весь список, чтобы найти лучший блок памяти, который занимает O (n), поэтому я думаю об использовании красно-черного дерева, чтобы улучшить время выполнения до O (logN). Будут ли случаи, когда красно-черное дерево не подойдет лучше всего? Если да, может ли кто-нибудь привести мне пример? Спасибо.

Answer 1

Красно-черное дерево работает нормально, но это не совсем хороший выбор.

Поскольку для эффективного использования O (размер) байтов требуется O (размер) времени, лучше использовать палец какое-то дерево поиска, которое ускоряет поиск небольших блоков за счет того, что на поиск больших блоков требуется больше времени: https://en.wikipedia.org/wiki/Finger_search_tree

Кроме того, вы, вероятно, просто захотите иметь отдельные бесплатные списки для одни из самых маленьких возможных размеров. Вы можете ожидать попадания в несколько строк кэша при поиске и обновлении дерева поиска. Каждая строка кэша имеет размер 64 байта на x86, поэтому одной строки кэша достаточно для хранения указателей заголовка для 8 свободных списков. Если вы поместите указатели заголовка для свободных списков для 8 наименьших размеров в одну строку кэша, то выделение блоков этих размеров будет намного быстрее.

Это также позволяет вам выделять блоки, которые меньше красно-черного узел дерева.

Answer 2

Если вы хотите построить красно-черное дерево, чтобы сделать то, что вы описываете, есть лучшие варианты.

Учитывая n элементов, время построения красно-черного дерева занимает O (n log n ). Это то же самое время от простой сортировки массива и использования двоичного поиска, что намного проще и очень производительно.

Очевидно, что дерево было бы лучше, если бы элементы постоянно добавлялись в массив.