Красно-Черные Деревья


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

Я проверил типичные источники (Wikipedia, Google), и большинство описаний полезности и реализации (в частности) красно-черных деревьев оторвались как плотные и трудные для понимания. Я конечно, для кого-то с необходимым фоном это имеет смысл, но на данный момент он читает почти как иностранный язык.

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

13   52   2008-08-21 22:37:15

13 ответов:

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

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

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

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

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

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

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

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

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

ни один из ответов не упоминает, что именно BSTs хороши.

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

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

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

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

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

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

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

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

красные черные деревья и B-деревья используются во всех видах постоянного хранения; потому что деревья сбалансированы производительность ширины и глубины траверсы смягчаются.

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

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

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

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

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

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

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

не эквивалентно двоичному дереву (как задано в вашем вопросе).

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

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

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

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

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

4)оба потомка каждого красного узла-черные. => Этот потомки внутреннего узла в B-дереве всегда лежат на другом уровне.

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

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

много-много тепла, но мало света, так что давайте посмотрим, если мы можем обеспечить некоторые.

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

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

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

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

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

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

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

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

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

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

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

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

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

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