Здесь много и много тепла, но не так много света, поэтому давайте посмотрим, сможем ли мы его дать.
Сначала , дерево RB является ассоциативной структурой данных, в отличие, скажем, от массива, который не может взять ключ и вернуть ассоциированное значение, ну, если только это не целочисленный «ключ» в 0% разреженный индекс смежных целых чисел. Массив также не может увеличиваться в размере (да, я тоже знаю о realloc (), но под прикрытием, которое требует новый массив и затем memcpy ()), поэтому, если у вас есть какое-либо из этих требований, массив не подойдет , Эффективность памяти массива идеальна. Ноль отходов, но не очень умных или гибких - realloc () не выдерживает.
Секунда , в отличие от bsearch () для массива элементов, который является ассоциативной структурой данных, дерево RB может динамически увеличиваться (И уменьшаться) в своем размере. Bsearch () отлично работает для индексации структуры данных известного размера, который останется таким же. Поэтому, если вы заранее не знаете размер ваших данных, или необходимо добавить или удалить новые элементы, функция bsearch () будет недоступна. Bsearch () и qsort () хорошо поддерживаются в классическом C и имеют хорошую эффективность использования памяти, но недостаточно динамичны для многих приложений. Хотя они мои любимые, потому что они быстрые, простые и если вы не имеете дело с приложениями реального времени, довольно часто они достаточно гибки. Кроме того, в C / C ++ вы можете отсортировать массив указателей на записи данных, указав, например, на элемент struc {}, который вы хотите сравнить, а затем переставив указатель в массиве указателей так, чтобы указатели читались по порядку. в конце указателя сортировка возвращает ваши данные в отсортированном порядке. Использование этого с отображенными в память файлами данных чрезвычайно эффективно, быстро и довольно просто. Все, что вам нужно сделать, это добавить несколько "*" к вашим функциям сравнения.
Третий , в отличие от хеш-таблицы, которая также должна иметь фиксированный размер и не может быть увеличена после заполнения, дерево RB будет автоматически расти и балансироваться для поддержания своего O (log (n )) гарантия выполнения. Особенно, если ключ дерева RB является целым числом, он может быть быстрее, чем хеш, потому что, хотя сложность хеш-таблицы равна O (1), этот 1 может быть очень дорогим вычислением хеша. Множественное целочисленное одночасовое целое дерево часто сравнивает с вычислениями 100-часовых + хешей, не говоря уже о перефразировании, и malloc () пространстве для хэш-коллизий и перефразировок. Наконец, если вам нужен доступ ISAM, а также ключевой доступ к вашим данным, хеш исключается, так как отсутствует упорядочение данных, присущее хеш-таблице, в отличие от естественного упорядочения данных в любой реализации дерева. Классическое использование хеш-таблицы - обеспечение доступа к таблице зарезервированных слов для компилятора. Это эффективность памяти отлично.
Четвёртый , и очень низкий в любом списке, это связанный или двусвязный список, который, в отличие от массива, естественным образом поддерживает вставки и удаления элементов и, как следствие, изменение размера. Это самая медленная из всех структур данных, так как каждый элемент знает, как добраться до следующего элемента, поэтому вам нужно в среднем искать (element_knt / 2) ссылки, чтобы найти данные. Он в основном используется там, где вставки и удаления где-то в середине списка являются общими, и особенно, когда список является круглым и запитывает дорогостоящий процесс, что делает время для чтения ссылок относительно небольшим. Мой общий прием - использовать произвольно большой массив вместо связанного списка, если ваше единственное требование - увеличить его размер. Если вы исчерпали размер с массивом, вы можете realloc () больший массив. STL делает это для вас «под прикрытием», когда вы используете вектор. Грубо, но потенциально в тысячи раз быстрее, если вам не нужны вставки, удаления или поиск по ключу. Это плохая эффективность памяти, особенно для двусвязных списков. На самом деле, двусвязный список, требующий двух указателей, точно так же неэффективен в памяти, как красно-чёрное дерево, и при этом НИКОГО из его привлекательных быстрых упорядоченных характеристик поиска.
Пятое , деревья поддерживают много дополнительных операций над своими отсортированными данными, чем любая другая структура данных. Например, во многих запросах к базе данных используется тот факт, что диапазон значений листьев можно легко указать, указав их общего родителя, а затем сосредоточив последующую обработку на той части дерева, которой «принадлежит» родительский элемент. Потенциал многопоточности, предлагаемый этим подходом, должен быть очевиден, поскольку необходимо заблокировать только небольшую область дерева, а именно только узлы, которыми владеет родитель, и сам родитель.
Короче говоря, деревья - это Кадиллак структур данных. Вы платите высокую цену за использование используемой памяти, но получаете полностью самостоятельную структуру данных. Вот почему, как указывалось в других ответах, базы данных транзакций почти исключительно используют деревья.