Красно-черные деревья

Ответ 1

Красные Черные деревья хороши для создания хорошо сбалансированных деревьев. Основная проблема с бинарными деревьями поиска заключается в том, что вы можете сделать их несбалансированными очень легко. Представьте, что ваш первый номер равен 15. Тогда все числа после этого становятся все меньше и меньше 15. У вас будет дерево, очень тяжелое с левой стороны и не имеющее ничего с правой стороны.

Красные Черные деревья решают это, заставляя ваше дерево быть сбалансированным всякий раз, когда вы вставляете или удаляете. Это достигается путем серии вращений между узлами предка и дочерними узлами. Алгоритм на самом деле довольно простой, хотя он немного длинный. Я бы предложил собрать учебник CLRS (Cormen, Lieserson, Rivest and Stein), "Введение в алгоритмы" и чтение на деревьях RB.

Реализация также не так уж коротка, поэтому, вероятно, не стоит включать ее сюда. Тем не менее деревья широко используются для высокопроизводительных приложений, которым необходим доступ к большому количеству данных. Они обеспечивают очень эффективный способ поиска узлов с относительно небольшими накладными расходами на вставку/удаление. Опять же, я бы предложил посмотреть CLRS, чтобы узнать, как они используются.

В то время как BST не могут использоваться явно - один пример использования деревьев в целом - почти во всех современных СУБД. Аналогично, ваша файловая система почти наверняка представлена ​​как некоторая древовидная структура, и файлы также индексируются таким образом. Деревья власти Google. Деревья действуют практически на каждом сайте в Интернете.

Ответ 2

Я бы хотел затронуть только вопрос "Итак, что делает бинарные деревья полезными в некоторых общих задачах, которые вы делаете во время программирования?"

Это большая тема, с которой многие люди не согласны. Некоторые говорят, что алгоритмы, преподаваемые в степени CS, такие как деревья двоичного поиска и направленные графы, не используются в повседневном программировании и поэтому не имеют отношения к делу. Другие не согласны с тем, что эти алгоритмы и структуры данных являются основой для всех наших программ, и важно понять их, даже если вам никогда не придется писать один для себя. Это фильтрует разговоры о хорошем собеседовании и методах найма. Например, Steve Yegge содержит статью о интервью в Google который решает этот вопрос. Помните эти дебаты; опытные люди не согласны.

В типичном бизнес-программировании вам может не понадобиться создавать бинарные деревья или даже деревья очень часто. Тем не менее, вы будете использовать много классов, которые внутренне работают с деревьями. Многие из основных классов организации на каждом языке используют деревья и хеши для хранения и доступа к данным.

Если вы участвуете в более высокоэффективных начинаниях или ситуациях, которые несколько выходят за рамки бизнес-программирования, вы увидите, что деревья станут непосредственным другом. Как сказал еще один плакат, деревья - это основные структуры данных для баз данных и индексов всех видов. Они полезны для интеллектуального анализа данных и визуализации, расширенной графики (2d и 3d) и множества других вычислительных задач.

Я использовал двоичные деревья в виде BSP (разбиение двоичного пространства) деревьев в 3d-графике. В настоящее время я просматриваю деревья, чтобы сортировать большие объемы геокодированных данных и другие данные для визуализации информации в приложениях Flash/Flex. Всякий раз, когда вы нажимаете границу аппаратного обеспечения или хотите работать на более низких спецификациях оборудования, понимание и выбор наилучшего алгоритма может сделать разницу между неудачей и успехом.

Ответ 3

Ни один из ответов не говорит о том, для чего хорош BST.

Если то, что вы хотите сделать, это просто поиск по значениям, тогда хэш-таблица выполняется намного быстрее, O (1) вставка и поиск (лучше всего подходит для амортизации).

A BST будет искать O (log N), где N - количество узлов в дереве, вставки также O (log N).

Деревья RB и AVL важны, как и другой ответ, упомянутый из-за этого свойства, если простой BST создается со значениями в порядке, то дерево будет таким же высоким, как и количество вставленных значений, это плохо для производительности поиска.

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

Почему вы готовы платить за стоимость дерева за хеш-таблицу? ЗАКАЗ! Хэш-таблицы не имеют порядка, BST, с другой стороны, всегда упорядочены естественным образом в силу их структуры. Поэтому, если вы обнаружите, что выбрасываете кучу данных в массиве или другом контейнере, а затем сортируете его позже, BST может быть лучшим решением.

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

Красные черные деревья используются внутри почти в каждом упорядоченном контейнере языковых библиотек, С++ Set и Map,.NET SortedDictionary, Java TreeSet и т.д.

Таким образом, деревья очень полезны, и вы можете использовать их довольно часто, даже не зная об этом. Вам, скорее всего, никогда не понадобится написать его самостоятельно, хотя я бы очень рекомендовал его как интересное упражнение по программированию.

Ответ 4

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

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

Ответ 5

BST заставляют мир вращаться, как сказал Микель. Если вы ищете хорошее дерево для реализации, посмотрите деревья AVL (Википедия). У них есть условие балансировки, поэтому они гарантированно будут O (logn). Такая эффективность поиска позволяет логично вносить какие-либо процессы индексирования. Единственная вещь, которая была бы более эффективной, была бы хэширующей функцией, но они становятся уродливыми быстро, быстро и торопятся. Кроме того, вы столкнулись с Парадокс дня рождения (также известный как проблема с дыркой).

Какой учебник вы используете? Мы использовали Структуры данных и анализ в Java Марк Аллен Вайс. Я действительно открываю его на коленях, когда я набираю это. Он имеет отличный раздел о деревьях Красно-Черных и даже содержит код, необходимый для реализации всех деревьев, о которых он говорит.

Ответ 6

Лучшее описание красно-черных деревьев, которые я видел, является тем, что было в Кормене, Лейссерне и Ривесте "Введение в алгоритмы". Я мог даже понять это достаточно, чтобы частично реализовать один (только вставка). Существует также немало апплетов, таких как This One на различных веб-страницах, которые оживляют процесс и позволяют вам смотреть и просматривать графическое представление алгоритма построения древовидной структуры.

Ответ 7

Красно-черные деревья остаются сбалансированными, поэтому вам не нужно проходить глубоко, чтобы получить предметы. Сэкономленное время создает деревья RB O (log() n)) в случае WORST, в то время как неудачные двоичные деревья могут попасть в конфигурацию с односторонним расположением и вызывать ошибки в O (n) в плохом случае. Это происходит на практике или на случайных данных. Поэтому, если вам нужен критический код времени (извлечение базы данных, сетевой сервер и т.д.), Вы используете деревья RB для поддержки упорядоченных или неупорядоченных списков/наборов.

Но RBTrees для noobs! Если вы выполняете ИИ, и вам нужно выполнить поиск, вы обнаружите, что вы разблокируете информацию о состоянии. Вы можете использовать постоянное красно-черное для создания новых состояний в O (log (n)). Постоянное красное черное дерево хранит копию дерева до и после морфологической операции (вставка/удаление), но без копирования всего дерева (обычно и O (log (n))). У меня открыто исходное красно-черное дерево для java

http://edinburghhacklab.com/2011/07/a-java-implementation-of-persistent-red-black-trees-open-sourced/

Ответ 8

Здесь много и много тепла, но не так много света, поэтому давайте посмотрим, можем ли мы предоставить некоторые из них.

Первый, дерево RB - это ассоциативная структура данных, в отличие от, скажем, массива, который не может взять ключ и вернуть связанное значение, ну, если только целочисленный "ключ" в 0 % разреженного индекса смежных целых чисел. Массив не может увеличиваться по размеру (да, я знаю и о realloc(), но под обложками, для которых требуется новый массив, а затем memcpy()), поэтому, если у вас есть одно из этих требований, массив не будет делать, Эффективность памяти массива идеальна. Нулевые отходы, но не очень умные или гибкие - realloc() не выдерживают.

Второй, в отличие от bsearch() для массива элементов, который является ассоциативной структурой данных, дерево RB может расти (и сокращаться) по размеру динамически. Функция bsearch() отлично работает для индексирования структуры данных с известным размером, который останется таким размером. Поэтому, если вы заранее не знаете размер ваших данных или новые элементы должны быть добавлены или удалены, bsearch() отсутствует. Bsearch() и qsort() хорошо поддерживаются в классическом C и имеют хорошую эффективность памяти, но недостаточно динамичны для многих приложений. Это мой личный фаворит, потому что они быстрые, легкие, и если вы не имеете дело с приложениями реального времени, довольно часто достаточно гибкие. Кроме того, в C/С++ вы можете отсортировать массив указателей на записи данных, указав на элемент struc {}, например, вы хотите сравнить, а затем переставить указатель в массиве указателей, чтобы считывание указателей в порядке в конце сортировки указателя выведите свои данные в отсортированном порядке. Использование этого с файлами данных с отображением памяти чрезвычайно экономично, быстро и легко. Все, что вам нужно сделать, это добавить несколько "*" к вашей функции /s сравнения.

Третий, в отличие от хеш-таблицы, которая также должна быть фиксированным размером и не может быть увеличена после заполнения, дерево RB автоматически вырастет и сбалансируется для поддержания своего O (log ( n)) гарантия работы. Особенно, если ключ дерева RB является int, он может быть быстрее, чем хэш, потому что, хотя сложность хэш-таблицы является O (1), это 1 может быть очень дорогостоящим вычислением хэша. Многократное однократное целое число с деревом часто превосходит 100-часовые + хэш-вычисления, не говоря уже об повторном использовании, и malloc() пространство для хэш-коллизий и повторений. Наконец, если вы хотите доступ к ISAM, а также ключ доступа к вашим данным, исключается хеш, поскольку упорядочение данных, присущих хэш-таблице, не выполняется, в отличие от естественного упорядочения данных в любой реализации дерева. Классическое использование хэш-таблицы состоит в том, чтобы предоставить доступ к таблице зарезервированных слов для компилятора. Эффективность памяти отличная.

Четвертый и очень низкий в любом списке, является связанным или дважды связанным списком, который, в отличие от массива, естественно поддерживает вставки и удаления элементов, и, как это следует, изменение размера, Это самая медленная из всех структур данных, так как каждый элемент знает, как перейти к следующему элементу, поэтому вам нужно искать в среднем ссылки (element_knt/2) для поиска вашей базы данных. В основном он используется там, где вставки и удаления где-то в середине списка являются общими, и особенно, когда список является круглым и загружает дорогостоящий процесс, который заставляет время читать ссылки относительно небольшими. Мой общий RX должен использовать произвольно большой массив вместо связанного списка, если ваше единственное требование - увеличить его размер. Если вы закончите размер с массивом, вы можете realloc() увеличить массив. STL делает это для вас "под обложками", когда вы используете вектор. Грубый, но потенциально в 1000 раз быстрее, если вам не нужны вставки, удаления или ключевые поисковые запросы. Плохое качество памяти, особенно для двусвязных списков. Фактически, двусвязный список, требующий двух указателей, точно такой же, как память, неэффективна, как красно-черное дерево, имея НЕТ своих привлекательных быстрых, упорядоченных характеристик поиска.

Пятый, деревья поддерживают множество дополнительных операций над их отсортированными данными, чем любая другая структура данных. Например, многие запросы к базе данных используют тот факт, что диапазон значений листьев можно легко указать, указав их общий родительский элемент, а затем сосредоточив последующую обработку на части дерева, которое родительский "владеет". Потенциал многопоточности, предлагаемый таким подходом, должен быть очевиден, так как нужно блокировать только небольшую область дерева, а именно, только узлы, которыми владеет родитель, и сам родитель.

Короче говоря, деревья - это Cadillac структур данных. Вы платите высокую цену с точки зрения используемой памяти, но вы получаете полностью самосохраняющую структуру данных. Вот почему, как указано в других ответах, базы данных транзакций используют деревья почти исключительно.

Ответ 9

Поскольку вы спрашиваете, какое дерево используют люди, вам нужно знать, что дерево Red Black в основном представляет собой 2-3-4 B-дерево (например, B-дерево порядка 4). B-дерево не эквивалентно бинарному дереву (как задано в вашем вопросе).

Здесь отличный ресурс, описывающий начальную абстракцию, известную как симметричное двоичное B-дерево, которое позже превратилось в RBTree. Вам понадобится хорошее понимание на B-деревьях, прежде чем это будет иметь смысл. Подводя итог: "красная" ссылка на дереве Red Black - это способ представления узлов, которые являются частью B-дерева node (значения в пределах диапазона ключей), тогда как "черные" ссылки - это узлы, которые связаны вертикально в B-дерево.

Итак, вот что вы получаете, когда вы переводите правила дерева красных черных с точки зрения B-дерева (я использую формат Red Black tree rule = > B Tree эквивалент):

1) A node либо красный, либо черный. = > A node в b-дереве может быть либо частью node, либо как node на новом уровне.

2) Корень черный. (Это правило иногда опускается, так как оно не влияет на анализ) = > Корень node можно рассматривать как часть внутреннего корня node как ребенка воображаемого родителя node.

3) Все листья (NIL) являются черными. (Все листы имеют тот же цвет, что и корень.) = > Поскольку один из способов представления дерева RB - опустить листья, мы можем это исключить.

4) Оба ребенка из каждого красного node являются черными. = > Дети внутреннего node в B-дереве всегда лежат на другом уровне.

5) Каждый простой путь от данного node к любому из его потомков оставляет одно и то же число черных узлов. = > B-дерево поддерживается сбалансированным, так как требует, чтобы все листовые узлы находились на одной и той же глубине (поэтому высота B-дерева node представлена ​​числом черных звеньев от корня до листа красной Черное дерево)

Кроме того, существует более простая "нестандартная" реализация Роберта Седжуика здесь: (Он автор книги "Алгоритмы вместе с Уэйн" )

Ответ 10

Если вы хотите увидеть, как дерево Red-Black должно выглядеть графически, я закодировал реализацию дерева Red-Black, которое вы можете скачать здесь

Ответ 11

IME, почти никто не понимает алгоритм дерева RB. Люди могут повторить правила вам, но они не понимают, почему эти правила и откуда они происходят. Я не исключение: -)

По этой причине я предпочитаю алгоритм AVL, потому что его легко понять. Как только вы это понимаете, вы можете закодировать его с нуля, потому что это имеет смысл для вас.

Ответ 12

Деревья могут быть быстрыми. Если у вас есть миллион узлов в сбалансированном двоичном дереве, для поиска одного элемента требуется в среднем двадцать сравнений. Если у вас есть миллион узлов в связанном списке, для поиска одного и того же элемента требуется в среднем пятьсот тысяч сравнений.

Если дерево не сбалансировано, оно может быть столь же медленным, как и список, а также хранить больше памяти для хранения. Представьте дерево, в котором большинство узлов имеют правильный ребенок, но не оставляют ребенка; это список, но вам все равно нужно сохранить пространство памяти, чтобы поместить его влево node, если он появится.

В любом случае, AVL tree был первым сбалансированным алгоритмом двоичного дерева, и статья Википедии на нем довольно ясна. Честно говоря, статья в Википедии о красно-черных деревьях ясна, как грязь.

Помимо двоичных деревьев, B-деревья - это деревья, где каждый node может иметь много значений. B-Tree - это не двоичное дерево, просто это имя. Они действительно полезны для эффективного использования памяти; каждый node дерева может быть рассчитан так, чтобы он входил в один блок памяти, так что вы не медленно (и медленно) и находите в памяти много разных вещей, которые были выгружены на диск. Вот феноменальный пример B-Tree.

Ответ 13

Если вы хотите взглянуть на мою реализацию Red Black Tree. http://code.google.com/p/cstl/source/browse/src/c_rb.c