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

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

Красные черные деревья решают эту проблему, заставляя ваше дерево быть сбалансированным всякий раз, когда вы вставляете или удаляете. Это достигается с помощью серии вращений между узлами-предками и дочерними узлами. Алгоритм на самом деле довольно прост, хотя и немного длинноват. Я бы предложил взять учебник CLRS (Кормен, Лизерсон, Ривест и Штейн), "Introduction to Algorithms" и читать на деревьях RB.

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

Хотя BSTs может и не использоваться явно - один пример использования деревьев вообще есть практически в каждом современном RDBMS. Аналогично, ваша файловая система почти наверняка представлена в виде какой-то древовидной структуры, и файлы также индексируются таким образом. Деревья питают Google. Деревья питают практически каждый сайт в интернете.

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

Это большая тема, с которой многие люди не согласны. Некоторые говорят, что алгоритмы, преподаваемые в степени CS, такие как бинарные деревья поиска и направленные графы, не используются в программировании day-to-day и поэтому не имеют отношения к делу. Другие не соглашаются, говоря, что эти алгоритмы и структуры данных являются основой для всего нашего программирования, и важно понимать их, даже если вам никогда не придется писать их для себя. Это фильтруется в разговоры о хороших методах собеседования и найма. Например, у Стива Йегге есть статья об интервью в 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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Кроме того, здесь есть более простая реализация 'non-standard' Роберта Седжвика : (он является автором книги Algorithms along with Wayne)

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

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

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

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

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

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

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

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

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

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

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

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

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

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