Двоичная куча против двоичного дерева С++

Поиск минимума и максимума за постоянное время достигается за счет сохранения ссылок на крайний левый и крайний правый узлы RB-дерева в структуре заголовка карты. Вот комментарий fиз исходного кода RB- tree, шаблон, из которого берутся реализации std::set, std::map и std::multimap:

ячейка заголовка поддерживается ссылками не только на корень, но и на самый левый узел дерева, чтобы обеспечить постоянное время begin(), и на самый правый узел дерева, чтобы обеспечить линейное время работы при использовании с алгоритмами универсального набора ( set_union и др.)

Компромисс здесь заключается в том, что эти указатели необходимо поддерживать, поэтому операции вставки и удаления будут иметь другую «служебную операцию». Однако вставки и удаления уже выполняются за логарифмическое время, поэтому дополнительные асимптотические затраты на поддержку этих указателей отсутствуют.

По крайней мере, в типичной реализации std::set (и std::map) будут реализованы как многопоточное двоичное дерево¹. Другими словами, каждый узел содержит не только указатель на его (до) двух дочерних узлов, но также на предыдущий и следующий по порядку узел. Тогда сам класс set имеет указатели не только на корень дерева, но также на начало и конец многопоточного списка узлов.

Для поиска узла по ключу используются обычные бинарные указатели. Для обхода дерева по порядку используются указатели потоков.

Это имеет ряд недостатков по сравнению с двоичной кучей. Наиболее очевидным является то, что он хранит четыре указателя для каждого элемента данных, тогда как двоичная куча может хранить только данные без указателей (отношения между узлами неявно определяются позициями данных). В крайнем случае (например, std::set<char>) это может привести к тому, что для хранения указателей потребуется намного больше места, чем для данных, которые вам действительно нужны (например, в 64-разрядной системе вы можете получить 4 указателя по 64 бита каждый для хранения каждого 8-битного символа). Это может привести к плохому использованию кеша, что (в свою очередь) снижает скорость.

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

Таким образом, даже несмотря на то, что дерево с нитями может найти минимум или максимум или перейти к следующему или предыдущему узлу за O (1) и найти любой заданный элемент за O (log N), константы могут быть значительно выше, чем при выполнении то же самое с кучей. В зависимости от размера хранимых элементов, общее используемое хранилище также может быть значительно больше, чем с кучей (наихудший случай, очевидно, когда в каждом узле хранится только небольшое количество данных).

_{1. С применением некоторого алгоритма балансировки — чаще всего красно-черного, но иногда AVL-деревьев или B-деревьев. Можно использовать любое количество других сбалансированных деревьев (например, альфа-сбалансированные деревья, деревья k-соседей, бинарные b-деревья, общие сбалансированные деревья).}

Я не эксперт по картам, но возврат первого элемента карты будет считаться своего рода «корнем». всегда есть указатель на него, поэтому время поиска будет мгновенным. То же самое можно сказать и о BSTree, поскольку у него явно есть корневой узел, затем 2 узла от него и так далее (что, кстати, я бы рассмотрел с помощью дерева AVL, поскольку время поиска для наихудшего сценария намного лучше, чем BSTree ).

O(log(N)) обычно используется только для оценки наихудшего сценария. Итак, если у вас есть полностью несбалансированное BSTree, у вас фактически будет O (N), поэтому, если вы ищете последний узел, вам нужно выполнить сравнение с каждым узлом.

Я не слишком уверен в вашем последнем утверждении, хотя карта отличается от самобалансирующегося дерева, они называются деревьями AVL (или этому меня учили). Карта использует «ключи» для организации объектов определенным образом. Ключ находится путем сериализации данных в число, и число по большей части помещается в список.